07 · 图算法（Graph Algorithms）

📅 预计 90 分钟　|　⭐ 本章主题：把「关系」画成点和线，学会在网络上遍历、分层、排序

---

7.0 从社交网络说起

把微信好友关系画出来：每个人是一个顶点（vertex），两人是好友就画一条边（edge）。你会得到一张巨大的网——这就是图（graph）。地图导航、社交推荐、课程安排、网络路由，背后全是图。

图的两个最基本操作，就是你在地铁上做的事：深度优先像是「一条线走到头再换线」，广度优先像是「一层层往外扩散」。这两个遍历是几乎所有图算法（连通分量、拓扑排序、最短路径、最小生成树）的地基。本章先把地基打牢。

---

7.1 图的基本概念

术语	含义	生活例子
顶点 vertex	图里的点	好友、城市、地铁站
边 edge	连接两个点的线	好友关系、道路
无向图 undirected	边没有方向，A-B 和 B-A 一样	好友（对称关系）
有向图 directed	边有方向，A→B 不等于 B→A	关注、单向道路
有权图 weighted	边上带数值（距离、成本）	地图上的里程
度 degree	连到某点的边数	你的微信好友数
入度 / 出度	有向图中指向 / 指出的边数	被关注数 / 关注数
路径 path	沿着边从一点走到另一点	一条出行路线
环 cycle	起点等于终点的路径	环形路
连通 connected	任意两点之间都有路径	全城地铁互通
连通分量 connected component	一块互相连通的极大子图	一群互加好友的圈子

需要区分两类图：无向图的边像握手（彼此对称），有向图的边像箭头（单向）。判断一个图有没有环、有几个连通分量，是后续拓扑排序和最短路径的前提。

7.2 图的存储

邻接矩阵：一张方桌

用 n×n 的二维数组存图，matrix[i][j] = 1（或权重）表示 i→j 有边。优点：判断两点是否相邻是 O(1)；缺点：无论边多稀少都要占 O(n²) 空间。

# 邻接矩阵：4 个顶点，用 0/1 表示是否有边
n = 4
matrix = [[0] * n for _ in range(n)]
edges = [(0, 1), (0, 2), (1, 2), (2, 3)]
for u, v in edges:
    matrix[u][v] = 1
    matrix[v][u] = 1        # 无向图对称；有向图去掉这行

for row in matrix:
    print(row)
# 输出:
# [0, 1, 1, 0]
# [1, 0, 1, 0]
# [1, 1, 0, 1]
# [0, 0, 1, 0]

邻接表：每人的通讯录

为每个顶点存一个邻居列表。优点：空间 O(V+E)，遍历一个点的所有邻居很快，是工程和竞赛里的主流；缺点：判断两点是否相邻要遍历列表。

# 邻接表：每个顶点 -> 邻居列表
graph = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A"],
    "D": ["B"],
}

# 带权重的写法：邻居列表里存 (顶点, 权重)
graph_w = {
    "A": [("B", 2), ("C", 5)],
    "B": [("A", 2), ("D", 3)],
    "C": [("A", 5)],
    "D": [("B", 3)],
}

怎么选：稠密图（边多）用矩阵，稀疏图（边少）用邻接表。绝大多数实际问题都是稀疏的，所以邻接表出场率远高于矩阵。考试里「建图」通常指建邻接表。

⚠️ 常见错误

1. 无向图只加了一条边：无向图必须 matrix[u][v] 和 matrix[v][u] 都加，否则遍历会漏边。
2. 顶点编号从 1 开始：很多题顶点编号是 1..n，但数组下标 0..n-1。建表时要么 graph[u - 1]，要么开 n+1 个桶。
3. [[0]*n]*n 的坑：这样建矩阵每一行是同一个列表，改一行全变。要写 [[0] * n for _ in range(n)]。
4. 邻接表忘记初始化：直接 graph[u].append(v) 但 graph 里还没有 u 这个键，会 KeyError；用 defaultdict(list) 或先建好所有空列表。

---

7.3 深度优先搜索 DFS ⭐

一条路走到黑，再回头

深度优先搜索（DFS）的思想：从一个顶点出发，沿着一条边走到底，走不动了退回来，再试下一条没走过的边。实现分递归和显式栈两种。

graph = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "E"],
    "D": ["B"],
    "E": ["C"],
}

def dfs_recursive(node, visited):
    visited.add(node)
    print(node, end=" ")
    for nxt in graph[node]:
        if nxt not in visited:
            dfs_recursive(nxt, visited)

dfs_recursive("A", set())
# 输出: A B D C E    （从 A 出发，先沿 B 走到头，再回头走 C）

显式栈版本（避免递归深度过大的问题，同时访问顺序和递归略有差异）：

def dfs_iterative(start):
    visited = set()
    stack = [start]
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        print(node, end=" ")
        for nxt in graph[node]:
            if nxt not in visited:
                stack.append(nxt)      # 栈是后进先出，最后压入的先访问

dfs_iterative("A")
# 输出: A C E B D

递归版好懂、好写，是首选；但图的链非常深（比如 n=10⁵ 的链）时，Python 递归可能超限（默认上限约 1000），此时用显式栈。

DFS 的应用：求连通分量、检测环、拓扑排序（后序）、走迷宫找路径。

⚠️ 常见错误

1. visited 忘记在递归前标记：如果先进递归再标记，会重复访问，甚至死循环（环形图）。
2. 用列表当栈却 popleft：显式栈要用 pop()（后进先出）；用 pop(0) 或 popleft() 会退化成 BFS 且效率 O(n)。
3. 递归无出口：处理大图时递归深度超限，报 RecursionError；考虑改用显式栈。

---

7.4 广度优先搜索 BFS ⭐

一圈一圈往外扩散

广度优先搜索（BFS）像往水里扔石子：先访问起点，再访问它的所有邻居（第 1 层），再访问邻居的邻居（第 2 层）……核心数据结构是队列（先进先出）。

from collections import deque

def bfs(start):
    visited = set([start])
    q = deque([start])
    while q:
        node = q.popleft()
        print(node, end=" ")
        for nxt in graph[node]:
            if nxt not in visited:
                visited.add(nxt)
                q.append(nxt)

bfs("A")
# 输出: A B C D E    （一层层展开：A → B,C → D,E）

BFS 最经典的性质：首次访问到某顶点的层数 = 从起点到它的最短步数（无权图）。所以「无权图最短路径」「最少步数」类问题，第一反应就是 BFS。用 dist 字典记录每个点第一次被访问时的层数即可。

def bfs_distance(start):
    dist = {start: 0}
    q = deque([start])
    while q:
        node = q.popleft()
        for nxt in graph[node]:
            if nxt not in dist:
                dist[nxt] = dist[node] + 1
                q.append(nxt)
    return dist

print(bfs_distance("A"))
# 输出: {'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 2}

⚠️ 常见错误

1. 忘了在入队时标记 visited：如果出队时才标记，同一个点可能被重复入队多次。
2. 用 stack.pop() 当 BFS：那成了 DFS；BFS 必须从队头取（popleft）。
3. dist 记录时机错误：要在「第一次发现」时记录层数，不是在出队时覆盖（可能覆盖成更远的值）。
4. 图不连通时漏点：一次 BFS 只能访问起点所在的连通分量，别以为走遍全图。

---

7.5 DFS vs BFS 对比

维度	DFS	BFS
数据结构	栈（或递归）	队列
方向	一路到底再回头	一层层往外扩
最短路径（无权图）	不保证	首次访问即最短
空间占用	栈深（链状图 O(V)）	队宽（最宽层 O(V)）
典型应用	连通分量、环检测、拓扑排序	无权最短路、分层

两者遍历一遍图都是 O(V+E)（每个顶点入栈/入队一次，每条边被看一次），空间 O(V)。记住：要最短步数用 BFS，要深入探索用 DFS。

⚠️ 常见错误

1. 拿 DFS 求无权最短路径：DFS 找到的第一条路径不一定是短的。
2. 以为 BFS 能处理带权图：BFS 只对边权相等（或无权）的图保证最短；带权最短路径要用 Dijkstra（见下一章）。
3. 忽略非连通图：一次 DFS/BFS 只走一个连通分量；要求全图信息（如所有连通分量）就要对每个未访问顶点分别启动。

---

7.6 连通分量

把图拆成「互不相通」的几块

连通分量（connected component）就是「互相能走到」的极大点集。判断一个图有几个连通分量：对每个还没访问的顶点启动一次 DFS/BFS，启动几次就有几个分量。

def connected_components(graph):
    visited = set()
    comps = []
    for node in graph:
        if node not in visited:
            stack, comp = [node], []
            visited.add(node)
            while stack:
                cur = stack.pop()
                comp.append(cur)
                for nxt in graph[cur]:
                    if nxt not in visited:
                        visited.add(nxt)
                        stack.append(nxt)
            comps.append(comp)
    return comps

graph = {"A": ["B"], "B": ["A"], "C": ["D"], "D": ["C"], "E": []}
print(connected_components(graph))
# 输出: [['A', 'B'], ['C', 'D'], ['E']]    三个连通分量

无向图用 visited 集合即可；有向图的连通性更复杂，分成强连通分量（SCC，两两互相可达）问题，需要 Tarjan 或 Kosaraju 算法，本章不展开。判断无向图是否连通：连通分量个数等于 1 就连通。

⚠️ 常见错误

1. 只从一个点启动遍历：以为一次 DFS 能覆盖全图，忽略不连通部分。
2. 有向图用无向图思路：有向图的「弱连通」和「强连通」是两回事，别混。
3. 每次 DFS 重新清空 visited：visited 必须跨多次启动共享，否则每次都在原地打转，数出错误的分量数。

---

7.7 拓扑排序 ⭐

给有依赖关系的任务排顺序

拓扑排序（topological sort）：对有向无环图（DAG），把顶点排成一条线，使每条边 u→v 都满足 u 排在 v 前面。典型场景：选课（先修课约束）、构建系统（依赖编译）。

前提：图必须是有向无环图（DAG）。有环就不可能有合法顺序（A 依赖 B、B 又依赖 A）。

Kahn 算法（贪心 + BFS）：不断找出「入度为 0」的顶点（没有前置依赖的任务），拿出来放进结果，删掉它，更新邻居的入度，重复直到没有入度为 0 的顶点。如果最后结果不足 n 个，说明图里有环。

from collections import deque

def topo_sort(n, edges):
    # edges: [(u, v)] 表示 u 必须在 v 之前
    graph = [[] for _ in range(n)]
    indegree = [0] * n
    for u, v in edges:
        graph[u].append(v)
        indegree[v] += 1

    q = deque([i for i in range(n) if indegree[i] == 0])
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in graph[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                q.append(v)
    return order if len(order) == n else None    # None 表示有环，无拓扑序

edges = [(0, 1), (0, 2), (1, 3), (2, 3)]
print(topo_sort(4, edges))
# 输出: [0, 1, 2, 3]    也可能是 [0, 2, 1, 3]，都是合法拓扑序

另一种方式：DFS 后序（先把依赖的后代全部访问完，再把自己放进结果），最后把结果倒序。两种方法都是 O(V+E)。

拓扑序不一定唯一——只要满足所有依赖关系，就是合法答案。所以问「输出拓扑序」时，任何合法序都应算对。

⚠️ 常见错误

1. 忘记判断有环：若图有环，Kahn 会提前结束，必须检查 len(order) == n。
2. 入度更新遗漏：删掉 u 后要遍历 u 的所有出边更新入度，漏一条就出错。
3. 把拓扑排序当成按编号排序：拓扑序是依赖序，不是字典序或编号序。
4. 用 DFS 后序时忘记倒序：DFS 后序得到的顺序要 reverse 才是拓扑序。

---

7.8 本章串讲：从遍历到一切

把本章的图景连起来：建图（存储）→ 遍历（DFS/BFS）→ 在遍历结果上加工。连通分量是「DFS 分组」，拓扑排序是「按入度分层」，无权最短路径是「BFS 分层」——本质都是遍历框架套不同外壳。下一章的最短路径与最小生成树，是在遍历基础上加上「权重」这个维度。

---

🧠 记忆口诀

• 存储二选一：边多用矩阵，边少用邻接表。
• DFS 用栈（后进先出），BFS 用队（先进先出）；求最短步数就 BFS。
• 遍历一遍 O(V+E)：每个点进一次，每条边看一次。
• 拓扑排序记两条件：入度为 0 的先进队，队空数不够就是有环。
• 连通分量：换一个没访问过的点，就多一块。

⭐ 考点清单

1. 图的术语：顶点、边、无向/有向、权、度、路径、环、连通
2. 邻接矩阵 vs 邻接表：空间、判断相邻、遍历效率、建表代码
3. DFS 递归与迭代两种写法、visited 时机
4. BFS 队列写法、dist 记录最短步数（无权图）
5. DFS 与 BFS 对比表、各自适用场景
6. 连通分量：多次启动遍历、有向图强连通的概念区分
7. 拓扑排序：Kahn 算法、有环判定、结果不唯一
8. 复杂度 O(V+E)、空间 O(V) 的推导

📌 中英术语表

中文	English	说明
图	graph	顶点与边的集合
顶点	vertex	图中的点
边	edge	连接两点的线
无向图	undirected graph	边没有方向
有向图	directed graph	边有方向
有权图	weighted graph	边上带权重
度	degree	与某点相连的边数
入度 / 出度	in-degree / out-degree	有向图的入 / 出边数
邻接矩阵	adjacency matrix	n×n 数组存边
邻接表	adjacency list	每点存邻居列表
路径	path	依次经过的点序列
环	cycle	首尾相接的路径
连通	connected	任意两点可达
连通分量	connected component	极大的连通子图
强连通分量	strongly connected component	有向图中两两互达的极大子图
深度优先搜索	depth-first search (DFS)	栈，走到底再回头
广度优先搜索	breadth-first search (BFS)	队列，层层扩散
拓扑排序	topological sort	DAG 上满足依赖的线性序
有向无环图	directed acyclic graph (DAG)	无环的有向图
队列 / 栈	queue / stack	BFS / DFS 的核心结构