图论算法：拓扑排序、最短路径与最小生成树
图是面试中承上启下的知识点——既能考查基础遍历，又能延伸到高级算法。
图的表示法
邻接矩阵
# 适合：稠密图、需要快速判断两点之间是否有边
# 空间：O(V^2)
# 0 1 2 3
# 0 [0, 1, 0, 1]
# 1 [0, 0, 1, 0]
# 2 [0, 0, 0, 1]
# 3 [0, 0, 0, 0]
graph = [
[0, 1, 0, 1],
[0, 0, 1, 0],
[0, 0, 0, 1],
[0, 0, 0, 0]
]
# 判断 0 -> 1 是否有边：O(1)
has_edge = graph[0][1] == 1
邻接表（推荐）
# 适合：稀疏图、遍历邻居
# 空间：O(V + E)
from collections import defaultdict
graph = defaultdict(list)
edges = [(0, 1), (0, 3), (1, 2), (2, 3)]
for u, v in edges:
graph[u].append(v)
# 遍历 0 的所有邻居
for neighbor in graph[0]:
print(neighbor) # 1, 3
加权图的表示
# 邻接表（带权重）
graph = defaultdict(list)
weighted_edges = [(0, 1, 5), (0, 3, 2), (1, 2, 3), (2, 3, 1)]
# (u, v, weight)
for u, v, w in weighted_edges:
graph[u].append((v, w))
# 遍历 0 的所有邻居及权重
for neighbor, weight in graph[0]:
print(f"{0} -> {neighbor}: {weight}") # 0 -> 1: 5, 0 -> 3: 2
拓扑排序（Topological Sort）
拓扑排序针对有向无环图（DAG），将节点排成线性序列，使得每条有向边的起点在终点之前。
应用场景
- 课程选修计划（先修课关系）
- 编译依赖解析（Makefile）
- 任务调度（有依赖顺序的工作流）
算法一：Kahn 算法（BFS）
核心思想： repeatedly remove nodes with in-degree 0.
from collections import deque, defaultdict
def topological_sort_kahn(num_nodes, edges):
# 构建图和入度数组
graph = defaultdict(list)
in_degree = [0] * num_nodes
for u, v in edges:
graph[u].append(v)
in_degree[v] += 1
# 将所有入度为 0 的节点入队
queue = deque([i for i in range(num_nodes) if in_degree[i] == 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) != num_nodes:
return [] # 图中有环，无法拓扑排序
return result
复杂度：$O(V + E)$ 时间，$O(V + E)$ 空间
算法二：DFS 后序遍历
核心思想： DFS 完成后，节点按「完成时间」逆序即为拓扑序。
def topological_sort_dfs(num_nodes, edges):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
# 0=未访问, 1=访问中, 2=已访问
visited = [0] * num_nodes
result = []
has_cycle = [False]
def dfs(node):
if has_cycle[0]:
return
if visited[node] == 1: # 遇到访问中的节点，有环
has_cycle[0] = True
return
if visited[node] == 2:
return
visited[node] = 1
for neighbor in graph[node]:
dfs(neighbor)
visited[node] = 2
result.append(node)
for i in range(num_nodes):
if visited[i] == 0:
dfs(i)
if has_cycle[0]:
return []
return result[::-1] # 逆序
经典题目
LeetCode 207. Course Schedule（判断是否有环）
def canFinish(numCourses, prerequisites):
graph = defaultdict(list)
in_degree = [0] * numCourses
for course, prereq in prerequisites:
graph[prereq].append(course)
in_degree[course] += 1
queue = deque([i for i in range(numCourses) if in_degree[i] == 0])
processed = 0
while queue:
node = queue.popleft()
processed += 1
for neighbor in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
return processed == numCourses
LeetCode 210. Course Schedule II（返回拓扑序）
在上面的代码基础上，记录队列弹出的顺序即可。
最短路径算法
单源最短路径：Dijkstra（无负权边）
核心思想：贪心，每次选择距离源点最近的未确定节点，更新其邻居的距离。
import heapq
from collections import defaultdict
def dijkstra(graph, start, n):
"""
graph: dict[node] = list of (neighbor, weight)
return: dict[node] = shortest_distance_from_start
"""
dist = {i: float('inf') for i in range(n)}
dist[start] = 0
visited = set()
heap = [(0, start)] # (distance, node)
while heap:
d, node = heapq.heappop(heap)
if node in visited:
continue
visited.add(node)
for neighbor, weight in graph[node]:
if neighbor not in visited:
new_dist = d + weight
if new_dist < dist[neighbor]:
dist[neighbor] = new_dist
heapq.heappush(heap, (new_dist, neighbor))
return dist
复杂度：$O((V + E) \log V)$（使用最小堆）
限制：不能处理负权边。如果有负权边，需要用 Bellman-Ford。
单源最短路径：Bellman-Ford（可处理负权边）
核心思想： relax all edges V-1 times.
def bellman_ford(edges, n, start):
"""
edges: list of (u, v, weight)
return: dist array, or None if negative cycle exists
"""
dist = [float('inf')] * n
dist[start] = 0
# Relax V-1 times
for _ in range(n - 1):
updated = False
for u, v, w in edges:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
updated = True
if not updated:
break
# Check for negative cycle
for u, v, w in edges:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
return None # Negative cycle detected
return dist
复杂度：$O(V \times E)$
应用场景：
- 有负权边的图
- 检测负权环（如汇率套利检测）
多源最短路径：Floyd-Warshall
def floyd_warshall(graph, n):
"""
graph: adjacency matrix
return: distance matrix
"""
dist = [[float('inf')] * n for _ in range(n)]
for i in range(n):
dist[i][i] = 0
for j, w in graph[i]:
dist[i][j] = w
for k in range(n):
for i in range(n):
for j in range(n):
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
return dist
复杂度：$O(V^3)$，适合节点数较少（< 500）的 Dense Graph。
最小生成树（MST）
最小生成树：连接图中所有节点的树，边权和最小。
Kruskal 算法（基于 Union-Find）
核心思想：按边权从小到大排序，每次选择不会形成环的最小边。
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # Path compression
return self.parent[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py:
return False
# Union by rank
if self.rank[px] < self.rank[py]:
px, py = py, px
self.parent[py] = px
if self.rank[px] == self.rank[py]:
self.rank[px] += 1
return True
def kruskal(edges, n):
"""
edges: list of (u, v, weight)
return: list of edges in MST, total weight
"""
edges.sort(key=lambda x: x[2])
uf = UnionFind(n)
mst = []
total_weight = 0
for u, v, w in edges:
if uf.union(u, v):
mst.append((u, v, w))
total_weight += w
if len(mst) == n - 1:
break
return mst, total_weight
复杂度：$O(E \log E)$（排序主导）
Prim 算法（基于优先队列）
核心思想：从一个节点出发，每次选择连接已选集合和未选集合的最小边。
def prim(graph, n, start=0):
"""
graph: adjacency list with weights
return: list of edges in MST, total weight
"""
visited = [False] * n
visited[start] = True
heap = []
# 加入起点的所有边
for neighbor, weight in graph[start]:
heapq.heappush(heap, (weight, start, neighbor))
mst = []
total_weight = 0
while heap and len(mst) < n - 1:
w, u, v = heapq.heappop(heap)
if visited[v]:
continue
visited[v] = True
mst.append((u, v, w))
total_weight += w
for neighbor, weight in graph[v]:
if not visited[neighbor]:
heapq.heappush(heap, (weight, v, neighbor))
return mst, total_weight
复杂度：$O((V + E) \log V)$
Kruskal vs Prim 选型
| 场景 | 推荐算法 |
|---|---|
| 稀疏图（E ≈ V） | Kruskal |
| 稠密图（E ≈ V^2） | Prim（邻接矩阵版 O(V^2)） |
| 边已排序或动态加边 | Kruskal |
| 只需要部分 MST | Prim（可随时停止） |
并查集（Union-Find）
并查集是解决「连通性」问题的利器，也是 Kruskal 算法的核心。
优化技巧
- 路径压缩（Path Compression）：find 时将节点直接挂到根节点
- 按秩合并（Union by Rank）：将矮树挂到高树上
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
self.count = n # 连通分量数
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py:
return False
if self.rank[px] < self.rank[py]:
px, py = py, px
self.parent[py] = px
if self.rank[px] == self.rank[py]:
self.rank[px] += 1
self.count -= 1
return True
def connected(self, x, y):
return self.find(x) == self.find(y)
均摊复杂度：$O(\alpha(N))$，其中 $\alpha$ 是阿克曼函数的反函数，增长极慢，可视为常数。
经典题目
LeetCode 200. Number of Islands
def numIslands(grid):
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
uf = UnionFind(rows * cols + 1) # 额外一个虚拟节点表示水域
water_dummy = rows * cols
def get_index(r, c):
return r * cols + c
for r in range(rows):
for c in range(cols):
if grid[r][c] == '0':
uf.union(get_index(r, c), water_dummy)
else:
for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == '1':
uf.union(get_index(r, c), get_index(nr, nc))
return uf.count - 1 # 减去水域虚拟节点
面试答题框架
被问到图相关算法时：
- 确认图的类型：有向/无向、加权/无权、稀疏/稠密
- 选择合适的表示法：稀疏图用邻接表，稠密图用邻接矩阵
- 明确问题类型：
- 是否有环 / 拓扑排序 → Kahn / DFS
- 最短路径（无负权）→ Dijkstra
- 最短路径（有负权）→ Bellman-Ford
- 全源最短路径 → Floyd-Warshall
- 最小生成树 → Kruskal（稀疏）/ Prim（稠密）
- 连通性 → Union-Find
常见面试题速查
| 题目 | 算法 | 难度 |
|---|---|---|
| Course Schedule (207) | 拓扑排序 | Medium |
| Course Schedule II (210) | 拓扑排序 | Medium |
| Number of Islands (200) | DFS / BFS / Union-Find | Medium |
| Network Delay Time (743) | Dijkstra | Medium |
| Cheapest Flights Within K Stops (787) | Bellman-Ford | Medium |
| Min Cost to Connect All Points (1584) | MST (Prim/Kruskal) | Medium |
| Find the City With the Smallest Number of Neighbors (1334) | Floyd-Warshall | Medium |
| Redundant Connection (684) | Union-Find | Medium |
| Graph Valid Tree (261) | Union-Find / DFS | Medium |
| Alien Dictionary (269) | 拓扑排序 | Hard |
| Sequence Reconstruction (444) | 拓扑排序 | Medium |
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。