图算法实战：最短路径与最小生成树

引言

图论是计算机科学中最重要的分支之一，广泛应用于社交网络分析、路由算法、推荐系统等领域。本文将深入讲解两类核心图算法：最短路径算法和最小生成树算法，并提供实际代码示例。

一、最短路径算法

1.1 Dijkstra算法

Dijkstra算法是解决单源最短路径问题的经典算法，适用于非负权重的图。

算法原理：

1. 初始化：起点距离为0，其他节点距离为∞
2. 选择未访问节点中距离最小的节点
3. 更新该节点邻居的距离
4. 重复步骤2-3直到所有节点都被访问

代码实现：

import heapq

def dijkstra(graph, start):
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0
    pq = [(0, start)]
    
    while pq:
        current_distance, current_node = heapq.heappop(pq)
        
        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(pq, (distance, neighbor))
    
    return distances

# 示例使用
graph = {
    'A': {'B': 4, 'C': 2},
    'B': {'C': 1, 'D': 5},
    'C': {'D': 8, 'E': 10},
    'D': {'E': 2},
    'E': {}
}
print(dijkstra(graph, 'A'))
​

时间复杂度： O((V + E) log V)，使用优先队列优化

1.2 Bellman-Ford算法

适用于含负权边的图，可以检测负权环。

def bellman_ford(graph, start):
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0
    
    for _ in range(len(graph) - 1):
        for node in graph:
            for neighbor, weight in graph[node].items():
                if distances[node] + weight < distances[neighbor]:
                    distances[neighbor] = distances[node] + weight
    
    # 检测负权环
    for node in graph:
        for neighbor, weight in graph[node].items():
            if distances[node] + weight < distances[neighbor]:
                raise ValueError("图中存在负权环")
    
    return distances
​

二、最小生成树算法

2.1 Prim算法

从任意节点开始，逐步添加边直到覆盖所有节点。

def prim(graph):
    mst = []
    visited = set()
    start_node = list(graph.keys())[0]
    edges = [(0, start_node, None)]
    
    while edges and len(visited) < len(graph):
        weight, node, parent = heapq.heappop(edges)
        
        if node in visited:
            continue
            
        visited.add(node)
        if parent is not None:
            mst.append((parent, node, weight))
        
        for neighbor, edge_weight in graph[node].items():
            if neighbor not in visited:
                heapq.heappush(edges, (edge_weight, neighbor, node))
    
    return mst
​

2.2 Kruskal算法

按边的权重排序，使用并查集避免环。

class UnionFind:
    def __init__(self, nodes):
        self.parent = {node: node for node in nodes}
        self.rank = {node: 0 for node in nodes}
    
    def find(self, node):
        if self.parent[node] != node:
            self.parent[node] = self.find(self.parent[node])
        return self.parent[node]
    
    def union(self, node1, node2):
        root1 = self.find(node1)
        root2 = self.find(node2)
        
        if root1 != root2:
            if self.rank[root1] < self.rank[root2]:
                self.parent[root1] = root2
            elif self.rank[root1] > self.rank[root2]:
                self.parent[root2] = root1
            else:
                self.parent[root2] = root1
                self.rank[root1] += 1
            return True
        return False

def kruskal(graph):
    edges = []
    for node in graph:
        for neighbor, weight in graph[node].items():
            edges.append((weight, node, neighbor))
    
    edges.sort()
    uf = UnionFind(graph.keys())
    mst = []
    
    for weight, node1, node2 in edges:
        if uf.union(node1, node2):
            mst.append((node1, node2, weight))
    
    return mst
​

三、实际应用场景

1. 网络路由：OSPF协议使用Dijkstra算法
2. 地图导航：Google Maps使用A*算法（Dijkstra的改进）
3. 社交网络：使用最小生成树发现社区结构
4. 物流配送：最短路径优化配送路线

四、性能优化技巧

1. 邻接表 vs 邻接矩阵：稀疏图使用邻接表
2. 优先队列优化：使用斐波那契堆可达到O(E + V log V)
3. 双向搜索：同时从起点和终点搜索
4. A*启发式：使用启发函数加速搜索

总结

掌握图算法对解决实际工程问题至关重要。选择合适的算法取决于图的特性（权重、密度）和问题需求。通过本文的学习，你应该能够在实际项目中应用这些算法解决复杂问题。

扩展阅读

• A*算法及其在游戏开发中的应用
• 最大流最小割算法
• 强连通分量算法
• 拓扑排序与关键路径分析