图论算法

图论算法:

图论是研究图（graph）结构及其性质的一门数学分支。在计算机科学中，图常用于建模网络、路径、关系等问题。以下是几种常见的图论算法及其 Python 实现示例和原理。

1. 深度优先搜索（DFS）

原理：

深度优先搜索是一种遍历或搜索图的算法，从起始节点开始，沿着一条路径深入到尽可能深的节点，然后回溯，继续探索其他路径。

Python 示例：

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start, end=" ")  # 访问节点
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)
​
# 示例图（邻接表表示）
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}
dfs(graph, 'A')

2. 广度优先搜索（BFS）

原理：

广度优先搜索按层次遍历节点，从起始节点开始逐层扩展访问其邻接节点。

Python 示例：

from collections import deque
​
def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    while queue:
        vertex = queue.popleft()
        print(vertex, end=" ")  # 访问节点
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
​
# 示例图（邻接表表示）
bfs(graph, 'A')

3. Dijkstra 最短路径算法

原理：

Dijkstra 算法用于求解单源最短路径问题，适用于权值非负的图。算法通过不断扩展最短路径集合，直到到达目标节点或遍历所有节点。

Python 示例：

import heapq
​
def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    priority_queue = [(0, start)]  # (距离, 节点)
​
    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)
        if current_distance > distances[current_node]:
            continue
​
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))
​
    return distances
​
# 示例图（加权邻接表表示）
weighted_graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'D': 2, 'E': 7},
    'C': {'A': 4, 'F': 3},
    'D': {'B': 2},
    'E': {'B': 7, 'F': 1},
    'F': {'C': 3, 'E': 1}
}
print(dijkstra(weighted_graph, 'A'))

4. Floyd-Warshall 算法

原理：

Floyd-Warshall 是一种动态规划算法，用于计算加权图中所有节点对的最短路径。

Python 示例：

def floyd_warshall(graph):
    nodes = list(graph.keys())
    distance = {node: {neighbor: float('inf') for neighbor in nodes} for node in nodes}
    for node in nodes:
        distance[node][node] = 0
​
    for u in graph:
        for v, w in graph[u].items():
            distance[u][v] = w
​
    for k in nodes:
        for i in nodes:
            for j in nodes:
                distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])
    return distance
​
# 示例图（加权邻接表表示）
all_pairs_graph = {
    'A': {'B': 3, 'C': 8},
    'B': {'C': 1, 'D': 1},
    'C': {'D': 1},
    'D': {}
}
print(floyd_warshall(all_pairs_graph))

5. Kruskal 最小生成树算法

原理：

Kruskal 算法用于找到连接所有节点的最小生成树（MST）。算法基于贪心思想，通过排序边并依次选择不形成环的最小权边构建 MST。

Python 示例：

def kruskal(nodes, edges):
    parent = {node: node for node in nodes}
    rank = {node: 0 for node in nodes}
​
    def find(node):
        if parent[node] != node:
            parent[node] = find(parent[node])
        return parent[node]
​
    def union(node1, node2):
        root1 = find(node1)
        root2 = find(node2)
        if root1 != root2:
            if rank[root1] > rank[root2]:
                parent[root2] = root1
            elif rank[root1] < rank[root2]:
                parent[root1] = root2
            else:
                parent[root2] = root1
                rank[root1] += 1
​
    mst = []
    edges.sort(key=lambda x: x[2])  # 按权值排序
    for u, v, weight in edges:
        if find(u) != find(v):
            mst.append((u, v, weight))
            union(u, v)
​
    return mst
​
# 示例图（节点和边列表表示）
nodes = ['A', 'B', 'C', 'D', 'E']
edges = [
    ('A', 'B', 1),
    ('A', 'C', 4),
    ('B', 'C', 2),
    ('B', 'D', 6),
    ('C', 'D', 3),
    ('C', 'E', 5),
    ('D', 'E', 1)
]
print(kruskal(nodes, edges))

总结

上述算法涵盖了图论中的基本问题：

• 遍历：DFS、BFS

• 单源最短路径：Dijkstra

• 多源最短路径：Floyd-Warshall

• 最小生成树：Kruskal

每种算法的选择取决于问题场景及图的性质（有向/无向、加权/非加权、稠密/稀疏等）。