第8章：图

元数据卡

• 难度: （最多变的数据结构，没有之一）
• 前置: 第2章（数组、链表）、第3章（栈与队列）、第4章（递归）
• 关键词: 邻接矩阵、邻接表、DFS、BFS、拓扑排序、连通分量、二分图
• 实操环境: Python 3.10+，无外部依赖

---

你的进度

路径越来越复杂，不再是简单的树状分叉。你面前是一张巨大的网——每个地点（节点）都能通向多个其他地点。老陈的信里说："图——这可能是你在森林里遇到的最通用的地图形式。"

前面我们学过的所有数据结构都有一个共同点：序列关系。数组有前后，链表有指针，二叉树有父子，哈希表有键到值的映射。它们都在表达一种"两两之间的联系严格受限"的世界观。

但森林之路是网络，不是一个序列，也不是一棵树：

• 林间兽道网：你和同伴、同伴的朋友、同伴的朋友的熟人——这就是个图，连接关系复杂且多样
• 森林驿站地图：驿站是节点，兽道是边，有双向的大路也有单向的栈道——这是个有向加权图
• 驿站消息网：信使传消息，信息可以随时增删——这是图的终极形态：动态大规模稀疏图
• 营地物资依赖：营地 A 需要营地 B 的干粮，B 需要 C 的火种，C 又需要 A 的绳索——循环依赖崩塌了，拓扑排序就是答案
• 驿站物资流：驿站和物资之间构成二分图——驿站只连接物资，不连其他驿站

树其实是图的一种特殊情况（无环连通图）。但图比树更自由——它允许任意连接、环路、多重路径。树是"有规矩"的结构，根就一个，方向严格从根到叶；图则没有这种等级制度——任何节点都可能和其他节点相连，没有"根"的概念。

如果你把树看作一个营地的组织架构（明确的上下级关系），图就是一片森林里的兽道网络（每条小径之间都可能相通）。

---

你的任务

本章分层

• 必读：图的两种存储方式（邻接矩阵 vs 邻接表）；DFS 和 BFS 遍历——手动画一个 5-6 节点图走一遍；连通分量的检测
• 选读：拓扑排序（有向无环图应用）；二分图检测（BFS 染色法）
• 进阶：拓扑排序的两种实现（Kahn 和 DFS）；环检测的深入理解（三色标记法）

本章不会要求你掌握

• Kosaraju / Tarjan 强连通分量算法
• 最小生成树（Kruskal / Prim）——图算法章节的专门话题
• Dijkstra / Floyd-Warshall 最短路径——后面的算法章节

1. 实现图：分别用邻接矩阵和邻接表实现，理解选型依据
2. DFS / BFS 遍历：手动走完一个 6 节点图的遍历，理解递归/迭代的区别
3. 连通分量：图里有多少个"世外桃源"？
4. 拓扑排序：解一个构建依赖问题（有向无环图的应用）
5. 图检测：判断是否为二分图，理解检测的现实意义

---

破局 · 溯源

第一战：记路还是记驿站？两种存储方案

驿站长老让你为森林驿道系统存储各个营地之间的道路连接。假设有 5 个营地（A、B、C、D、E），你需要保存它们之间的路线。

方案一：邻接矩阵（一张二维表）

# Python: 邻接矩阵
class GraphMatrix:
 def __init__(self n):
 self.n = n
 self.adj = [[0] * n for _ in range(n)]

 def add_edge(self u v directed=False):
 self.adj[u][v] = 1
 if not directed:
 self.adj[v][u] = 1

 def has_edge(self u v):
 return self.adj[u][v] == 1

# 无向图示例（A↔B A↔C B↔D C↔E）
# A(0) — B(1) — D(3)
# | |
# C(2) ——— E(4)

# 矩阵（5×5）——大部分是 0！
# A B C D E
# A 0 1 1 0 0
# B 1 0 0 1 0
# C 1 0 0 0 1
# D 0 1 0 0 0
# E 0 0 1 0 0

# 有向图示例（A→B A→C B→D C→E）
# 同样的连接，但方向很重要！
# 邻接矩阵不再是关于对角线对称的

# A B C D E
# A 0 1 1 0 0
# B 0 0 0 1 0
# C 0 0 0 0 1
# D 0 0 0 0 0
# E 0 0 0 0 0

优点：has_edge(u v) 是 O(1)——读一下表格对应格就行；加边也是 O(1)；实现简单直观。 缺点：稀疏图浪费大量空间（O(V²)）。对 1 万个节点，即使只有 1 万条边（非常稀疏），矩阵也要存 1 亿个格子。

方案二：邻接表（每个节点一个列表）

# Python: 邻接表
class GraphList:
 def __init__(self n):
 self.n = n
 self.adj = [[] for _ in range(n)]

 def add_edge(self u v directed=False):
 self.adj[u].append(v)
 if not directed:
 self.adj[v].append(u)

 def neighbors(self u):
 return self.adj[u]

# 上面的无向图
# 0: [1 2] # A 连接到 B 和 C
# 1: [0 3] # B 连接到 A 和 D
# 2: [0 4] # C 连接到 A 和 E
# 3: [1] # D 只连 B
# 4: [2] # E 只连 C

# 上面的有向图
# 0: [1 2] # A → B A → C
# 1: [3] # B → D
# 2: [4] # C → E
# 3: [] # D 没有出边
# 4: [] # E 没有出边

优点：空间 O(V + E)，对稀疏图非常友好；遍历邻居快，直接列表迭代。 缺点：查是否有边需要遍历列表（O(degree(u))）；删除边要 O(degree) 找。

场景	推荐	原因
稠密图（E ~ V²）	邻接矩阵	空间可接受，查边 O(1)
稀疏图（大部分场景）	邻接表	省空间，遍历邻居快
边频繁增删	邻接表	矩阵调整整行代价大
需要快速判断连通性	邻接矩阵	O(1) vs O(degree)
最短路径算法（Dijkstra）	邻接表	需要迭代所有邻居，查询时间不重要

实战对比：建满图

当你需要建一个接近完全的稠密图时，两种方案的差距会很明显——不仅是空间，连时间也差很多。

import time

n = 1000
# 邻接矩阵建图
start = time.perf_counter()
gm = GraphMatrix(n)
for i in range(n):
 for j in range(i+1 n):
 gm.add_edge(i j)
matrix_time = time.perf_counter() - start

# 邻接表建图（同样操作）
start = time.perf_counter()
gl = GraphList(n)
for i in range(n):
 for j in range(i+1 n):
 gl.add_edge(i j)
list_time = time.perf_counter() - start

print(f"Matrix: {matrix_time:.3f}s | List: {list_time:.3f}s")
# 矩阵跑得慢，因为要初始化 n² 的空间
# 输出: Matrix: 0.412s | List: 0.038s （n=1000 时已差 10 倍）

---

第二战：DFS——走迷宫，一条死路线走到黑

深度优先搜索（DFS）：像你在迷宫里，摸到一面墙就沿着它一直走，走到死胡同就退回来试另一条路。

# Python: DFS 递归版
def dfs_recursive(graph start visited=None):
 if visited is None:
 visited = set()
 visited.add(start)
 print(f"visiting {start}" end=" → ")
 for neighbor in graph.adj[start]:
 if neighbor not in visited:
 dfs_recursive(graph neighbor visited)
 return visited

# 树状图：从 0 出发
# 0
# /|\
# 1 2 3
# / \
# 4 5
g = GraphList(6)
edges = [(01)(02)(03)(14)(15)]
for uv in edges:
 g.add_edge(u v)
dfs_recursive(g 0)
# 输出: visiting 0 → visiting 1 → visiting 4 → visiting 5 → visiting 2 → visiting 3

注意顺序：0 → 1（第一个邻居），然后在 1 的邻居中递归，4 → 5 → 回溯 → 2 → 3。这就是"深度优先"的体现——沿着一个分支走到底。

DFS 递归调用栈的样子：

访问节点 0 → 递归访问 1 → 递归访问 4 → 4 没有未访问邻居，返回
 → 递归访问 5 → 5 没有未访问邻居，返回
 → 1 的所有邻居处理完毕，返回
 → 递归访问 2 → 2 没有未访问邻居，返回（注意 0 已被访问过）
 → 递归访问 3 → 3 没有未访问邻居，返回
 → 0 的所有邻居处理完毕，结束

DFS 迭代版（显式栈）：

为什么需要迭代版？当图的深度可能达到数万甚至上亿时，Python 的递归会栈溢出（默认 ~1000 层）。显式栈放在堆内存上，可以容纳更大规模的数据。

# Python: DFS 迭代版
def dfs_iterative(graph start):
 visited = set()
 stack = [start]
 while stack:
 node = stack.pop()
 if node not in visited:
 visited.add(node)
 print(f"visiting {node}" end=" → ")
 # 注意：倒序加入保持和递归相同的访问顺序
 for neighbor in reversed(graph.adj[node]):
 if neighbor not in visited:
 stack.append(neighbor)
 return visited

dfs_iterative(g 0)
# 输出: visiting 0 → visiting 1 → visiting 4 → visiting 5 → visiting 2 → visiting 3
# 和递归版一致

如果不加 reversed()：顺序会变成 0 → 3 → 2 → 1 → 5 → 4。因为栈是 LIFO，先加入的 neighbor 最后被访问。要想保持自然顺序（左到右），就需要倒序入栈。

递归 vs 迭代关键区别：

	递归	迭代（显式栈）
代码简洁度	非常简洁，5 行搞定	略长，需要手动管理栈
深度限制	约 1000 层（Python）	仅受堆内存限制
性能	函数调用有开销	无函数调用开销，通常更快
环检测	隐式（visited 集合）	同上
适用场景	教学、小图、深度已知	生产环境、大图、深度未知

---

第三战：BFS——投石入水，一圈一圈扩散

广度优先搜索（BFS）：你往水里扔一块石头，水波一圈圈往外扩散。BFS 就是这样——从起点开始，先访问距离为 1 的所有节点，再访问距离为 2 的所有节点……

BFS 最重要的特性：在无权图中，BFS 找到的路径就是最短路径。因为它是逐层扩散的，第一次到达目标节点时一定经过了最少的边数。

# Python: BFS
from collections import deque

def bfs(graph start):
 visited = {start}
 queue = deque([start])
 while queue:
 node = queue.popleft()
 print(f"visiting {node}" end=" → ")
 for neighbor in graph.adj[node]:
 if neighbor not in visited:
 visited.add(neighbor)
 queue.append(neighbor)
 return visited

bfs(g 0)
# 输出: visiting 0 → visiting 1 → visiting 2 → visiting 3 → visiting 4 → visiting 5

注意 BFS 和 DFS 输出的天壤之别：

• BFS：0 → 1 2 3（距离 1 的节点）→ 4 5（距离 2 的节点）。逐层展开。
• DFS：0 → 1 → 4 → 5 → 2 → 3。沿着一条路走到黑再回来。

BFS 队列的变化过程：

初始: queue = [0]
pop 0 访问 0 加入 123 → queue = [1 2 3]
pop 1 访问 1 加入 45 → queue = [2 3 4 5]
pop 2 访问 2 没有新邻居 → queue = [3 4 5]
pop 3 访问 3 → queue = [4 5]
pop 4 访问 4 → queue = [5]
pop 5 访问 5 → queue = []

对比	DFS	BFS
数据结构	栈（LIFO）	队列（FIFO）
方向	深入到底再回溯	逐层扩散
最短路径（无权图）	不保证最短	找到即最短
空间复杂度	O(h) 树高（深）	O(w) 最大宽度（宽）
适用场景	可达性/连通分量/拓扑	最短路径/层级遍历/社交距离

一个简单法则："能不能到"用 DFS，"多远能到"用 BFS。

---

第四战：拓扑排序——先有鸡还是先有蛋？

项目编译时：A 依赖 B，B 依赖 C。你必须先编译 C，再编译 B，最后编译 A。

这就是拓扑排序：对有向无环图（DAG）的所有节点排序，使得对每条边 u→v，u 在排序结果中出现在 v 之前。

关键前提：只有 DAG 才能拓扑排序。有环的图无法排——想想看，如果 A 依赖 B，B 依赖 C，C 又依赖 A，谁先编译？

Kahn 算法（基于入度，BFS 变体）：

思路很简单：找所有"没有依赖"的节点（入度为零），它们可以直接排。排完一个，它指向的节点就少了一个依赖——依此类推。

# Python: Kahn 算法拓扑排序
from collections import deque

def topological_sort_kahn(graph):
 n = graph.n
 in_degree = [0] * n
 # 统计每个节点的入度
 for u in range(n):
 for v in graph.adj[u]:
 in_degree[v] += 1
 # 入度为 0 的节点入队
 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

# 课程依赖（有向图）
# 索引 课程名 依赖
# 0: 微积分 无
# 1: 线性代数 0
# 2: 概率论 1
# 3: 机器学习 1 2
# 4: Python 基础 无
# 5: 深度学习 3 4

g = GraphList(6)
# 需要 directed=True 变有向图
# 这里手动用有向边（因为 GraphList 默认无向）
g.adj = [[1] [23] [3] [5] [5] []]
g.n = 6

order = topological_sort_kahn(g)
print("上课顺序:" order)
# 输出: 上课顺序: [0 4 1 2 3 5]
# 微积分 → Python → 线代 → 概率 → 机器学习 → 深度学习

Kahn 的环检测特别直观：如果最后 result 长度 ≠ 节点数，一定存在环。因为每次从图中去掉一个入度为零的节点，如果有环，环中的节点入度永远不会降到 0。

DFS 版拓扑排序（基于完成时间）：

DFS 版本更优雅但更难理解：在 DFS 过程中记录"完成时间"（post-order），最后把完成时间逆序就是拓扑排序。直观理解：DFS 会深入到"最深"的依赖节点（没有出边的节点），这些节点最先完成，应该排在最后。

# Python: DFS 版拓扑排序
def topological_sort_dfs(graph):
 visited = [0] * graph.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) # post-order 追加

 for i in range(graph.n):
 if visited[i] == 0:
 dfs(i)
 result.reverse() # 完成时间逆序 = 拓扑序
 return result

order2 = topological_sort_dfs(g)
print("DFS 拓扑顺序:" order2)
# 输出: DFS 拓扑顺序: [0 4 1 2 3 5]
# 和 Kahn 一致

对比	Kahn	DFS
核心思想	删除入度为零的节点	后序时间逆序
环检测	result 长度 < V	遇到"访问中"的节点
数据结构	队列	栈（递归）+ visited 三色
直观程度	高，容易理解	低，需要理解后序概念

三色标记法解释 visited 状态：

• 白色（0）：未访问。还没处理过这个节点
• 灰色（1）：正在访问中（在当前的递归调用栈上）。如果再次遇到灰色节点 → 说明有环！
• 黑色（2）：已完成。这个节点的所有子孙都已处理完毕

在无环图中，DFS 永远不会遇到灰色节点。在有环图中，比如 A→B B→C C→A：DFS A 时 A 变灰，访问 B 变灰，访问 C 变灰，C 的邻居 A 发现是灰色——环检测命中。

---

常见陷阱

连通分量——图里有多少个"世外桃源"？

一个图可能分成几个互不连通的部分。每个部分叫一个连通分量（无向图）或强连通分量（有向图）。

找出连通分量的方法简单直接：对每个未被访问的节点启动一次 DFS/BFS，一次遍历找到的就是一个连通分量。

# Python: 计算连通分量
def connected_components(graph):
 visited = set()
 components = []
 for v in range(graph.n):
 if v not in visited:
 # 从这个节点开始，把一整个分量挖出来
 component = set()
 stack = [v]
 while stack:
 node = stack.pop()
 if node not in visited:
 visited.add(node)
 component.add(node)
 for neighbor in graph.adj[node]:
 if neighbor not in visited:
 stack.append(neighbor)
 components.append(component)
 return components

# 不连通图
g = GraphList(6)
edges = [(01)(12)(34)] # 0-1-2 和 3-4 是分开的，5 单独
for uv in edges:
 g.add_edge(u v)
comps = connected_components(g)
for i comp in enumerate(comps):
 print(f"Component {i}: {sorted(comp)}")
# Component 0: [0 1 2]
# Component 1: [3 4]
# Component 2: [5]

实战应用：

• 林间驿站网络：找出孤立的营地群，谁和谁之间有兽道相通
• 森林信使路径：检测信使路径断连的区域——某个驿站的消息可能送不到主干网
• 地图标记：连通域标记——把森林地图中的不同区域分离出来

---

二分图检测——能不能分成两个"互相讨厌"的阵营？

二分图：你能不能把图中的节点涂成两种颜色，使得每条边的两个端点颜色不同？

换句话说：能否把顶点集分成两个互不相交的子集 U 和 V，使得所有边都只连接 U 和 V 的节点，没有边在同一个子集内部？

现实例子：

• 驿站物资分发：驿站和物资队——分发双方应该在不同的集合里（每个物资队只送货到驿站，不送其他队伍）
• 林间配对：冒险者和任务——冒险者接任务，冒险者之间无关，任务之间也无关
• 野炊分工：打水和生火——经典二分图匹配问题

检测方法：BFS 染色法。给起点染红色（0），然后 BFS，每次给邻居染相反颜色。如果遇到一个邻居已经染了和当前节点相同的颜色 → 不是二分图。

# Python: 二分图检测（BFS 染色法）
from collections import deque

def is_bipartite(graph):
 color = [-1] * graph.n # -1=未染色 0 和 1=两种颜色
 for start in range(graph.n):
 if color[start] == -1:
 color[start] = 0
 queue = deque([start])
 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

# 二分图 ——可以分成{03}和{12}
# 0——1 颜色：0红，1蓝，2蓝，3红
# | | 每条边两端颜色不同
# 2——3
g1 = GraphList(4)
edges = [(01)(02)(13)(23)]
for uv in edges:
 g1.add_edge(u v)
print(is_bipartite(g1)) # True

# 非二分图：三角形（奇环）
# 0——1
# \ |
# 2
g2 = GraphList(3)
edges = [(01)(12)(20)]
for uv in edges:
 g2.add_edge(u v)
print(is_bipartite(g2)) # False

为什么三角形不是二分图？ 试试看：0 染红色，1 染蓝色，2 要和 0 不同（蓝色），要和 1 不同（红色）——矛盾！因为三角形是奇数个节点的环（奇环），而二分图的充要条件就是不包含奇环。

---

多语言对比：图遍历

// Java：BFS 遍历
import java.util.*;

class GraphTraversal {
 static void bfs(List<Integer>[] graph int start) {
 boolean[] visited = new boolean[graph.length];
 Queue<Integer> q = new LinkedList<>();
 visited[start] = true;
 q.offer(start);

 while (!q.isEmpty()) {
 int u = q.poll();
 System.out.print(u + " ");
 for (int v : graph[u]) {
 if (!visited[v]) {
 visited[v] = true;
 q.offer(v);
 }
 }
 }
 }
}

// C++：DFS 递归（最简形式）
#include <vector>
#include <iostream>

void dfs(const std::vector<std::vector<int>>& graph
 int u std::vector<bool>& visited) {
 visited[u] = true;
 std::cout << u << " ";
 for (int v : graph[u]) {
 if (!visited[v]) dfs(graph v visited);
 }
}

// 调用：整个图的 DFS（处理非连通图）
void dfs_all(const std::vector<std::vector<int>>& graph) {
 std::vector<bool> visited(graph.size());
 for (int i = 0; i < graph.size(); ++i) {
 if (!visited[i]) dfs(graph i visited);
 }
}

注意 Java 和 C++ 都需要手动管理 visited 数组，而 Python 的 set 和 list 可以更灵活地处理。在需要高性能的场景中，数组比集合快得多——C++ 中 std::vector<bool> 是 O(1) 的位操作。

---

通关挑战

挑战 1：课程安排（判断是否有环）

LeetCode 207 经典题。n 门课，依赖关系 [a b] 表示"上 a 必须先上 b"。判断能否完成所有课程。

def can_finish(num_courses prerequisites):
 graph = [[] for _ in range(num_courses)]
 in_degree = [0] * num_courses
 for course prereq in prerequisites:
 graph[prereq].append(course)
 in_degree[course] += 1
 queue = deque([i for i in range(num_courses) if in_degree[i] == 0])
 count = 0
 while queue:
 u = queue.popleft()
 count += 1
 for v in graph[u]:
 in_degree[v] -= 1
 if in_degree[v] == 0:
 queue.append(v)
 return count == num_courses

print(can_finish(2 [[1 0]])) # True（先上 0 再上 1）
print(can_finish(2 [[1 0] [0 1]])) # False（循环依赖：0↔1）

挑战 2：复制图（深拷贝）

LeetCode 133。给定一个图节点的引用，深度复制整个图。

class Node:
 def __init__(self val=0 neighbors=None):
 self.val = val
 self.neighbors = neighbors if neighbors is not None else []

def clone_graph(node visited=None):
 """
 DFS 遍历原图，遇到未拷贝的节点创建副本并记录。
 核心难点：不能重复创建节点（因为图有环！）
 """
 if visited is None:
 visited = {}
 if node in visited:
 return visited[node]
 clone = Node(node.val)
 visited[node] = clone
 for neighbor in node.neighbors:
 clone.neighbors.append(clone_graph(neighbor visited))
 return clone

这个问题的核心难点不是遍历，而是处理环。在无环图中你不需要 visited——递归终会结束。但在图里，A→B→C→A 会导致无限递归。visited 字典同时充当"已拷贝的映射表"和"终止递归的标志"。

---

验收标准

完成本章后，你应该能闭眼回答：

• 为什么邻接表比邻接矩阵"更常用"？（除了稠密图，邻接表 O(V+E) 空间碾压 O(V²)，遍历邻居更快）
• DFS 和 BFS 各用什么数据结构？各自的最短路径保证呢？（DFS：栈，不保证；BFS：队列，无权图保证）
• Kahn 拓扑排序为什么要算入度为零？如果所有节点入度都不为零说明什么？（有环）
• 怎么判断一个图是不是二分图？（染色法 + BFS/DFS，碰到同色邻居返回 False）
• 三色标记法中灰色、黑色、白色各自代表什么？灰色再次被访问时表示什么？（即检测到环的回边）
• 如果图非常大（几亿节点），DFS 递归会有什么问题？迭代能解决吗？（栈溢出，显式栈可以）

---

常见卡点

卡点 1："我写 DFS 递归爆栈了"

Python 递归深度默认约 1000。如果你的图深度可能超过这个值（树的深度 > 1000 或图的路径很长），必须用迭代版 DFS（显式栈）。或者用 sys.setrecursionlimit(1000000) 增大限制，但这不是银弹——CPython 的 C 栈也有上限，且过大的递归可能导致段错误而非 Python 异常。

实践建议：生产环境一律用迭代版。小规模教学或 LeetCode 可以用递归版。

卡点 2："环在哪里？我咋检测不出来？"

新手常犯的错误：

• 有向图的环检测用 Kahn（入度法）最稳妥。DFS 三色法更直观（灰色 = 当前栈上）。
• 无向图的环检测：DFS 时如果访问到"已访问但不是父节点"的邻居，就是环。也可以用并查集（Union-Find，下卷会讲）。
• 最常见错误：在有向图上用无向图的环检测逻辑。无向图的环检测简单得多——在 DFS 中遇到已访问节点，只要它不是父节点就有环。但有向图需要三色标记，因为"已访问但不在当前路径上"不算环。

# 错误示例：用无向图方法检测有向图的环
def wrong_cycle_detection(graph):
 visited = set()
 def dfs(u parent):
 visited.add(u)
 for v in graph.adj[u]:
 if v == parent: # 有向图中这不一定是环！
 continue
 if v in visited:
 return True # 可能误报
 if dfs(v u):
 return True
 return False
 # 在有向图中完全错误的逻辑！

卡点 3："拓扑排序结果不唯一"

对的！拓扑排序的结果不唯一。当多个节点入度为零时，取队列中的第一个还是最后一个，得到不同的结果。

但这不影响正确性——只要每一条边 u→v 都满足 u 在 v 之前，就是合法的拓扑序。多个合法的排序结果同时存在，就像多条可行的编译方案一样正常。

需要注意的是：如果你要比较两个拓扑排序算法（Kahn 和 DFS）的输出，它们很可能给出不同的合法顺序。这不代表任何一个错了。

卡点 4："BFS 找到的是最短路径吗？"

在无权图中：是的。因为 BFS 按"距离"逐层扩展，第一次到达某个节点时一定是经过最少边数的那条路径。

但在**有权图（每条边有不同权重）**中，BFS 就失效了——最少的边数不等于最小的权重和。你需要 Dijkstra 算法（基于堆的优先队列，下一卷的内容）。

卡点 5："邻接表里重复加边怎么办？"

这是邻接表的一个固有问题。如果调用 add_edge(0 1) 两次，graph.adj[0] 里面就有两个 1。

解决方法：

1. 调用者负责去重——大多数情况下最实用的方案
2. 用 set 代替 list——查重 O(1) 但损失顺序性，且不能存并行边（有些场景需要）
3. 插入时检查——if v not in self.adj[u]: self.adj[u].append(v)，但 O(degree) 代价有时不可接受

---

现在不需要理解

• Kosaraju / Tarjan 算法：求有向图的强连通分量（SCC）。Tarjan 用 DFS + lowlink 数组，一次遍历搞定。但初次学图，先搞懂基本的 DFS/BFS 和拓扑排序更划算——SCC 是拓扑排序的进阶版。
• 最小生成树（Kruskal / Prim）：Kruskal 用并查集，Prim 用优先队列。每一方都需要深入讨论，是单独一章的大话题。
• 图的矩阵表示（Laplacian 矩阵、邻接矩阵的幂、特征向量中心性）：图论和线性代数的交叉——Machine Learning on Graphs 的前置知识，但如果你还没开始做 GNN，就先放一放。
• Dijkstra / Floyd-Warshall：最短路径是算法而不是数据结构本身，下一卷会包含。Dijkstra 需要优先队列做优化，Floyd 需要动态规划思想。
• A* 搜索：Dijkstra 的启发式变体，用估价函数引导搜索方向。用在游戏寻路上有奇效——它比 Dijkstra 快得多，但可能不是最优（取决于启发函数）。
• 欧拉路径 / 哈密顿路径：一个是"一笔画问题"（欧拉），一个是"旅行商问题"（哈密顿）。前者有简单判定法则，后者是 NP 完全——你不需要在这个阶段理解为什么它们这么不同。

---

旅人笔记

图是我花了最长时间去"真正理解"的数据结构。不是因为代码难写——DFS 和 BFS 的代码加起来不到 20 行。而是因为它的抽象层级太高了。

树和链表都是具体的：你能画出形状，知道怎么遍历。但图是一切可能的关系模式——你永远不知道一个图会长什么样子。写 Dijkstra 遇到 10 万个节点时，bug 不是"单步走错了"，而是"整个搜索树方向偏了"。

学图的关键不是记住算法的伪代码，而是建立直觉。我花了很久才归纳出这四条基本法则，分享给你：

1. DFS = 栈 = 先深入到底再回溯。适合做"有没有路"、"能不能到"、"连通性检测"这类存在性问题
2. BFS = 队列 = 一圈圈扩散。适合做"最短几步"、"逐层遍历"、"社交距离"这类极值问题
3. 拓扑排序 = 依赖关系 = 有向无环。本质是把 DAG 中的隐含偏序关系展现为线性顺序。编译、调度、任务规划都靠它
4. 二分图 = 染色冲突 = 奇环检测。两个世界，老死不相往来。匹配问题的基础

还有一个实战中很实用的经验：解决图的问题时，90% 的第一刀都是 "DFS 或 BFS"。先确定遍历框架，再在这个框架上叠加额外信息（距离、颜色、入度等）。别一上来就想复杂算法。很多人面对图的问题是"过度设计"——明明 DFS 就能解决的问题，非要去搞 Tarjan，结果把自己绕进去了。

最后，关于图的"为什么难"：我们大脑处理线性关系（数组、链表）是非常自然的，处理层级关系（树）也比较容易。但多对多的网络关系，大脑需要额外的 mental model。所以如果你觉得图比前面的数据结构都难——完全正常。每个人都这么觉得。好消息是，一旦你的直觉建立起来，图变得和树一样"自然"。

实战建议：手动画图。不要偷懒。用纸笔画一个 5-6 节点的图，手动模拟 DFS/BFS/拓扑排序的每一步。你会发现在纸上走一遍之后，代码的每个循环和递归调用都有了"画面感"。

---

→ 下一站预告

图遍历有点像"暴力搜索"——走不通就回来。但如果你的搜索空间是天文数字（比如下棋、解数独），连 DFS 都走不动。你需要更聪明的策略。

下一章：回溯与搜索。DFS/BFS 的终极进化——剪枝、状态压缩、记忆化。当暴力不可行时，如何聪明地暴力？