1. 图论基础与表示方法
图（Graph）是由顶点（Vertex）和边（Edge）组成的非线性数据结构，用于描述对象之间的「关系」或「连接」。在社交网络中，顶点代表用户，边代表好友关系；在地图导航中，顶点代表地点，边代表道路距离；在编译器中，顶点代表变量，边代表数据依赖。
图分为两种基本类型：
- 无向图：边没有方向，A-B 表示 A 和 B 相互连接（如社交网络的好友关系）
- 有向图：边有方向，A→B 表示从 A 指向 B（如任务依赖关系、网页链接）
图的存储方式直接决定算法的效率，选择合适的表示方法是图算法的第一步。
1.1 邻接矩阵
适合稠密图（边数接近 n²），支持 O(1) 判边。
# n 个节点的图
n = 5
# 有权图：matrix[i][j] = 边权，无边 = inf
inf = float('inf')
adj_matrix = [[inf] * n for _ in range(n)]
for i in range(n):
adj_matrix[i][i] = 0
# 添加边
adj_matrix[0][1] = 4
adj_matrix[1][2] = 1
1.2 邻接表
适合稀疏图（边数远小于 n²），空间 O(V + E)。
from collections import defaultdict
class Graph:
def __init__(self):
self.adj = defaultdict(list) # 节点 -> [(邻居, 权重)]
def add_edge(self, u, v, w=1, directed=False):
self.adj[u].append((v, w))
if not directed:
self.adj[v].append((u, w))
2. 图的遍历
2.1 DFS（深度优先搜索）
def dfs(graph, start):
visited = set()
result = []
def _dfs(node):
visited.add(node)
result.append(node)
for neighbor, _ in graph.adj[node]:
if neighbor not in visited:
_dfs(neighbor)
_dfs(start)
return result
# 非递归 DFS（栈模拟）
def dfs_iterative(graph, start):
visited = set()
stack = [start]
result = []
while stack:
node = stack.pop()
if node in visited:
continue
visited.add(node)
result.append(node)
for neighbor, _ in reversed(graph.adj[node]):
if neighbor not in visited:
stack.append(neighbor)
return result
2.2 BFS（广度优先搜索）
from collections import deque
def bfs(graph, start):
visited = {start}
queue = deque([start])
result = []
while queue:
node = queue.popleft()
result.append(node)
for neighbor, _ in graph.adj[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return result
BFS 的层级特性：第一次访问到某个节点时，路径长度最短（无权图）。
3. 最短路径算法
3.1 Dijkstra 算法（单源，非负权）
贪心策略，每次确定距离源点最近的节点。
import heapq
def dijkstra(graph, start, n):
"""O(E log V)"""
dist = {i: float('inf') for i in range(n)}
dist[start] = 0
pq = [(0, start)] # (距离, 节点)
parent = {start: None}
while pq:
d, u = heapq.heappop(pq)
if d > dist[u]:
continue # 旧条目，跳过
for v, w in graph.adj[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
parent[v] = u
heapq.heappush(pq, (dist[v], v))
return dist, parent
# 重构路径
def reconstruct_path(parent, target):
path = []
while target is not None:
path.append(target)
target = parent.get(target)
return path[::-1]
3.2 Bellman-Ford 算法（可处理负权边）
def bellman_ford(edges, n, start):
"""
edges: [(u, v, w), ...]
可检测负权环
"""
dist = [float('inf')] * n
dist[start] = 0
# 松弛 n-1 次
for _ in range(n - 1):
updated = False
for u, v, w in edges:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
updated = True
if not updated:
break
# 检测负权环
for u, v, w in edges:
if dist[u] + w < dist[v]:
raise ValueError("图中存在负权环")
return dist
3.3 Floyd-Warshall（全源最短路径）
def floyd_warshall(n, adj):
"""O(n³)，动态规划"""
dist = [[float('inf')] * n for _ in range(n)]
for i in range(n):
dist[i][i] = 0
for u, v, w in adj:
dist[u][v] = 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
3.4 算法选择指南
| 算法 | 时间 | 适用场景 | 能否处理负权 |
|---|---|---|---|
| Dijkstra | O(E log V) | 单源、非负权 | ❌ |
| Bellman-Ford | O(VE) | 单源、含负权 | ✅ |
| Floyd-Warshall | O(V³) | 全源 | ✅（无负权环） |
| SPFA | O(E) 平均 | Bellman-Ford 优化 | ✅ |
4. 最小生成树（MST）
4.1 Kruskal 算法（边贪心）
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]) # 路径压缩
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
return True
def kruskal(edges, n):
"""
edges: [(u, v, w), ...]
返回 MST 的总权重和边列表
"""
edges.sort(key=lambda x: x[2]) # 按权重排序
uf = UnionFind(n)
mst_weight = 0
mst_edges = []
for u, v, w in edges:
if uf.union(u, v):
mst_weight += w
mst_edges.append((u, v, w))
if len(mst_edges) == n - 1:
break
return mst_weight, mst_edges
4.2 Prim 算法（点贪心）
import heapq
def prim(graph, n, start=0):
"""O(E log V)，类似 Dijkstra"""
visited = [False] * n
min_heap = [(0, start, -1)] # (权重, 当前节点, 父节点)
mst_weight = 0
mst_edges = []
while min_heap and len(mst_edges) < n - 1:
w, u, p = heapq.heappop(min_heap)
if visited[u]:
continue
visited[u] = True
mst_weight += w
if p != -1:
mst_edges.append((p, u, w))
for v, w2 in graph.adj[u]:
if not visited[v]:
heapq.heappush(min_heap, (w2, v, u))
return mst_weight, mst_edges
5. 拓扑排序
适用：有向无环图（DAG），如任务调度、依赖解析。
5.1 Kahn 算法（BFS）
def topo_sort(graph, n):
in_degree = [0] * n
for u in range(n):
for v, _ in graph.adj[u]:
in_degree[v] += 1
queue = deque([i for i in range(n) if in_degree[i] == 0])
result = []
while queue:
u = queue.popleft()
result.append(u)
for v, _ in graph.adj[u]:
in_degree[v] -= 1
if in_degree[v] == 0:
queue.append(v)
if len(result) != n:
raise ValueError("图中存在环，无法拓扑排序")
return result
5.2 DFS 版本
def topo_sort_dfs(graph, n):
visited = [0] * n # 0=未访问, 1=访问中, 2=已完成
result = []
def dfs(u):
visited[u] = 1
for v, _ in graph.adj[u]:
if visited[v] == 1:
raise ValueError("图中存在环")
if visited[v] == 0:
dfs(v)
visited[u] = 2
result.append(u)
for i in range(n):
if visited[i] == 0:
dfs(i)
return result[::-1] # 逆序输出
6. 其他经典问题
6.1 二分图检测
def is_bipartite(graph, n):
color = [-1] * n # -1=未染色, 0/1=两种颜色
for start in range(n):
if color[start] != -1:
continue
queue = deque([start])
color[start] = 0
while queue:
u = queue.popleft()
for v, _ in graph.adj[u]:
if color[v] == -1:
color[v] = 1 - color[u]
queue.append(v)
elif color[v] == color[u]:
return False
return True
6.2 强连通分量（Kosaraju 算法）
def kosaraju(graph, n):
"""两次 DFS，O(V + E)"""
# 第一次：记录完成顺序
visited = [False] * n
order = []
def dfs1(u):
visited[u] = True
for v, _ in graph.adj[u]:
if not visited[v]:
dfs1(v)
order.append(u)
for i in range(n):
if not visited[i]:
dfs1(i)
# 构建转置图
rev_graph = Graph()
for u in range(n):
for v, w in graph.adj[u]:
rev_graph.add_edge(v, u, w, directed=True)
# 第二次：按逆序遍历转置图
visited = [False] * n
sccs = []
def dfs2(u, component):
visited[u] = True
component.append(u)
for v, _ in rev_graph.adj[u]:
if not visited[v]:
dfs2(v, component)
for u in reversed(order):
if not visited[u]:
component = []
dfs2(u, component)
sccs.append(component)
return sccs
7. 算法选择速查表
| 问题 | 推荐算法 | 时间复杂度 |
|---|---|---|
| 无权图最短路径 | BFS | O(V + E) |
| 非负权图单源最短 | Dijkstra + 堆 | O(E log V) |
| 含负权图单源 | Bellman-Ford / SPFA | O(VE) / O(E) |
| 全源最短路径 | Floyd-Warshall | O(V³) |
| 最小生成树 | Kruskal / Prim | O(E log E) / O(E log V) |
| 拓扑排序 | Kahn / DFS | O(V + E) |
| 连通分量 | DFS / Union-Find | O(V + E) |
| 强连通分量 | Kosaraju / Tarjan | O(V + E) |
8. 实际应用场景
图算法在工程中的落地远比面试题丰富：
社交网络分析：Facebook 的好友推荐基于共同邻居数（Jaccard 相似度），大厂的关系链分析使用图数据库 Neo4j 存储数十亿节点。PageRank 算法曾是 Google 搜索排名的核心，本质上是基于随机游走的图节点重要性评分。
网络路由：OSPF 协议使用 Dijkstra 计算最短路径；BGP 协议处理 AS（自治系统）之间的路由，本质上是在有向图中寻找最优路径。
依赖管理：npm/yarn 的包依赖解析需要拓扑排序检测循环依赖；Docker 镜像构建层也使用 DAG（有向无环图）优化缓存。
地图导航：高德/百度地图使用改进的 Dijkstra（A* 启发式搜索），结合实时路况权重动态调整路径。
编译器优化：寄存器分配是图着色问题；死代码消除基于数据流分析的图遍历。
推荐系统：知识图谱将实体关系建模为图，通过图神经网络（GNN）进行嵌入学习，实现更精准的推荐效果。
参考文章
- 上一篇：树与二叉树 — 二叉搜索树、AVL树、红黑树
- 下一篇：排序算法 — 快速排序、归并排序、堆排序与实战分析
- 数组与链表 — 线性结构基础
- 搜索与哈希 — 二分搜索、哈希表原理
- 动态规划 — 记忆化搜索与状态转移
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。