图算法

图算法用于处理图结构数据，包括最短路径、最小生成树、拓扑排序等问题。

最短路径

Dijkstra 算法

Dijkstra 算法用于计算从一个节点到其他所有节点的最短路径，适用于非负权边的图。

实现

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

# 示例图（带权）
graph = {
    'A': {'B': 4, 'C': 2},
    'B': {'A': 4, 'C': 1, 'D': 5},
    'C': {'A': 2, 'B': 1, 'D': 8, 'E': 10},
    'D': {'B': 5, 'C': 8, 'E': 2, 'F': 6},
    'E': {'C': 10, 'D': 2, 'F': 3},
    'F': {'D': 6, 'E': 3}
}

distances = dijkstra(graph, 'A')
print("Dijkstra 最短路径:")
for node, distance in distances.items():
    print(f"从 A 到 {node}: {distance}")

Floyd-Warshall 算法

Floyd-Warshall 算法用于计算图中所有节点对之间的最短路径。

实现

def floyd_warshall(graph):
    nodes = list(graph.keys())
    n = len(nodes)
    
    # 初始化距离矩阵
    dist = [[float('inf')] * n for _ in range(n)]
    
    # 设置对角线为 0
    for i in range(n):
        dist[i][i] = 0
    
    # 设置已知边
    for i, node in enumerate(nodes):
        for neighbor, weight in graph[node].items():
            j = nodes.index(neighbor)
            dist[i][j] = weight
    
    # 动态规划计算最短路径
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    
    return dist, nodes

# 示例
dist, nodes = floyd_warshall(graph)
print("\nFloyd-Warshall 所有节点对最短路径:")
for i, start in enumerate(nodes):
    for j, end in enumerate(nodes):
        print(f"从 {start} 到 {end}: {dist[i][j]}")

---

最小生成树

Prim 算法

Prim 算法从一个节点开始，逐步添加边来构建最小生成树。

实现

def prim(graph, start):
    mst = []
    visited = {start}
    edges = []
    
    # 添加起始节点的所有边
    for neighbor, weight in graph[start].items():
        heapq.heappush(edges, (weight, start, neighbor))
    
    while edges and len(visited) < len(graph):
        weight, u, v = heapq.heappop(edges)
        
        if v not in visited:
            visited.add(v)
            mst.append((u, v, weight))
            
            for neighbor, w in graph[v].items():
                if neighbor not in visited:
                    heapq.heappush(edges, (w, v, neighbor))
    
    return mst

# 示例
mst = prim(graph, 'A')
print("\nPrim 最小生成树:")
for u, v, weight in mst:
    print(f"{u} - {v}: {weight}")

---

拓扑排序

Kahn 算法

Kahn 算法使用入度和队列来进行拓扑排序。

实现

from collections import deque

def topological_sort(graph):
    # 计算入度
    in_degree = {node: 0 for node in graph}
    for node in graph:
        for neighbor in graph[node]:
            in_degree[neighbor] += 1
    
    # 初始化队列
    queue = deque([node for node in in_degree if in_degree[node] == 0])
    result = []
    
    while queue:
        node = queue.popleft()
        result.append(node)
        
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    # 检查是否有环
    if len(result) != len(graph):
        raise ValueError("图中存在环")
    
    return result

# 有向无环图
dag = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['E'],
    'D': ['F'],
    'E': ['F'],
    'F': []
}

top_order = topological_sort(dag)
print("\n拓扑排序结果:")
print(" -> ".join(top_order))  # A -> B -> C -> D -> E -> F