图论 · DFS / BFS 与拓扑排序
从 LC 207 课程表出发，用三色 DFS 在 O(V + E) 内做环检测和拓扑排序。
1. 核心原理
图论题的"母题"就两类：一类问连通性 / 最短无权路径（无向图为主，DFS 或 BFS 都行），另一类问拓扑顺序 / 环检测（有向图，DFS 三色法或 Kahn BFS）。再上一层是带权图（最短路 Dijkstra、最小生成树）、再上一层是网络流——但所有这些算法的"骨架"都建立在 DFS / BFS 之上。
图的两种表示
| 表示 | 存储 | 适用 | 看 u 的邻居 |
|---|---|---|---|
| 邻接表 | 每个节点一个 list | 一般情况（V ≤ 10⁵） | O(deg(u)) |
| 邻接矩阵 | V × V 0/1 矩阵 | 稠密图、V ≤ 1000 | O(V) |
LC 大多数图题 V 在 10⁴ ~ 10⁵，邻接矩阵 V² 会爆内存——默认用邻接表。Python defaultdict(list)、Java List<List<Integer>>、C++ vector<vector<int>> 都是标准写法。
DFS 还是 BFS？
| 场景 | 选 | 原因 |
|---|---|---|
| 找所有路径 / 子集 / 排列 | DFS | 天然的回溯结构 |
| 最短无权步数 | BFS | 第一次访问到目标即最短 |
| 有向图环检测 / 拓扑 | DFS 三色 或 Kahn BFS | 都行，看个人喜好 |
| 字典序最小拓扑序 | Kahn + 优先队列 | 入度归零时按字典序取最小 |
| 不能用递归（栈深） | BFS | 显式队列，没有递归栈限制 |
三色法（环检测的核心）
普通 visited[] 在有向图上不够用——遇到 visited 节点没法判断它是"递归栈上的祖先"还是"已完成的旁系子树"。三色法把"已访问"细分：
0 = 白：未访问
1 = 灰：进入 DFS 但还没返回（在递归栈中）
2 = 黑：DFS 完整返回，子图无环DFS 走到邻居 v：白色就递归进去；灰色说明走回了栈上祖先——找到环；黑色就跳过（已经验证无环）。
Kahn 拓扑排序（BFS 版预告）
不用递归的另一种拓扑写法：
- 算每个节点的入度（指向它的边数）
- 入度为 0 的节点入队
- BFS 每次出队
u，把u所有出边邻居的入度 −1；如果减到 0 就入队 - 出队总数 = 拓扑序长度。若
< V说明有环
DFS 三色 vs Kahn BFS 都是 O(V + E)，本章 §3 / §5 会各用一次。
2. 通用模板
下面四块骨架是后续所有图论题的起点：邻接表建图、DFS 递归（带 visited）、BFS 队列、Kahn 拓扑。
from collections import defaultdict, deque
# 骨架一：邻接表建图
def build_graph(n: int, edges: list[list[int]], directed: bool = True):
g = defaultdict(list)
for u, v in edges:
g[u].append(v)
if not directed:
g[v].append(u)
return g
# 骨架二：DFS 递归（visited 版，无向图 / 连通分量）
def dfs(u: int, g, visited: list[bool]):
visited[u] = True
for v in g[u]:
if not visited[v]:
dfs(v, g, visited)
# 骨架三：BFS 队列（最短无权步数）
def bfs(src: int, g, n: int) -> list[int]:
dist = [-1] * n
dist[src] = 0
q = deque([src])
while q:
u = q.popleft()
for v in g[u]:
if dist[v] == -1:
dist[v] = dist[u] + 1
q.append(v)
return dist
# 骨架四：Kahn 拓扑（有向图，同时检测环）
def kahn(n: int, edges: list[list[int]]) -> list[int]:
g = defaultdict(list)
indeg = [0] * n
for u, v in edges:
g[u].append(v)
indeg[v] += 1
q = deque(i for i in range(n) if indeg[i] == 0)
order = []
while q:
u = q.popleft()
order.append(u)
for v in g[u]:
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)
return order # len(order) < n ⇒ 有环// 骨架一：邻接表建图
List<List<Integer>> buildGraph(int n, int[][] edges, boolean directed) {
List<List<Integer>> g = new ArrayList<>();
for (int i = 0; i < n; i++) g.add(new ArrayList<>());
for (int[] e : edges) {
g.get(e[0]).add(e[1]);
if (!directed) g.get(e[1]).add(e[0]);
}
return g;
}
// 骨架二：DFS 递归（visited 版）
void dfs(int u, List<List<Integer>> g, boolean[] visited) {
visited[u] = true;
for (int v : g.get(u)) {
if (!visited[v]) dfs(v, g, visited);
}
}
// 骨架三：BFS 队列（最短无权步数）
int[] bfs(int src, List<List<Integer>> g, int n) {
int[] dist = new int[n];
Arrays.fill(dist, -1);
dist[src] = 0;
Deque<Integer> q = new ArrayDeque<>();
q.offer(src);
while (!q.isEmpty()) {
int u = q.poll();
for (int v : g.get(u)) {
if (dist[v] == -1) {
dist[v] = dist[u] + 1;
q.offer(v);
}
}
}
return dist;
}
// 骨架四：Kahn 拓扑
int[] kahn(int n, int[][] edges) {
List<List<Integer>> g = new ArrayList<>();
for (int i = 0; i < n; i++) g.add(new ArrayList<>());
int[] indeg = new int[n];
for (int[] e : edges) {
g.get(e[0]).add(e[1]);
indeg[e[1]]++;
}
Deque<Integer> q = new ArrayDeque<>();
for (int i = 0; i < n; i++) if (indeg[i] == 0) q.offer(i);
int[] order = new int[n];
int k = 0;
while (!q.isEmpty()) {
int u = q.poll();
order[k++] = u;
for (int v : g.get(u)) {
if (--indeg[v] == 0) q.offer(v);
}
}
return k == n ? order : new int[0]; // k < n ⇒ 有环
}#include <vector>
#include <queue>
#include <deque>
using namespace std;
// 骨架一：邻接表建图
vector<vector<int>> buildGraph(int n, vector<vector<int>>& edges, bool directed) {
vector<vector<int>> g(n);
for (auto& e : edges) {
g[e[0]].push_back(e[1]);
if (!directed) g[e[1]].push_back(e[0]);
}
return g;
}
// 骨架二：DFS 递归（visited 版）
void dfs(int u, vector<vector<int>>& g, vector<bool>& visited) {
visited[u] = true;
for (int v : g[u]) {
if (!visited[v]) dfs(v, g, visited);
}
}
// 骨架三：BFS 队列（最短无权步数）
vector<int> bfs(int src, vector<vector<int>>& g, int n) {
vector<int> dist(n, -1);
dist[src] = 0;
queue<int> q;
q.push(src);
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : g[u]) {
if (dist[v] == -1) {
dist[v] = dist[u] + 1;
q.push(v);
}
}
}
return dist;
}
// 骨架四：Kahn 拓扑
vector<int> kahn(int n, vector<vector<int>>& edges) {
vector<vector<int>> g(n);
vector<int> indeg(n, 0);
for (auto& e : edges) {
g[e[0]].push_back(e[1]);
indeg[e[1]]++;
}
queue<int> q;
for (int i = 0; i < n; i++) if (indeg[i] == 0) q.push(i);
vector<int> order;
order.reserve(n);
while (!q.empty()) {
int u = q.front(); q.pop();
order.push_back(u);
for (int v : g[u]) {
if (--indeg[v] == 0) q.push(v);
}
}
return order; // order.size() < n ⇒ 有环
}三色 DFS 不在骨架里——它和普通 DFS 的区别只在 color[] 三态 + 进入时染灰 / 退出时染黑，§3 母题里完整展开。
3. 母题精讲：LC 207 课程表
链接：LeetCode 207
题意：要选修 numCourses 门课，编号 0 到 numCourses − 1。给定一个先修关系数组 prerequisites，其中 prerequisites[i] = [a, b] 表示要修课 a 必须先修完课 b。判断能否修完全部课程。
数据范围：
numCourses：1 到 2000prerequisites.length：0 到 5000- 每条边
[a, b]：0 ≤ a, b < numCourses，a ≠ b
示例：
输入：numCourses = 4, prerequisites = [[1,0],[2,1],[3,2]]
输出：true
解释：依次修 0 → 1 → 2 → 3 即可。
输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：0 依赖 1、1 又依赖 0，形成环。把先修关系画成有向图：每个课是一个节点，[a, b] 是一条 b → a 的有向边（先修 b 才能修 a）。问题等价于：这张有向图里有没有环？没有环就能拓扑排序，存在环就修不完。
暴力思路：枚举所有合法修课顺序
直觉是把"修完课程"的过程具象化——试着穷举一种合法顺序。形式化地说，找到一个长度为 n 的排列 p[0], p[1], ..., p[n-1]，使得对每条边 b → a，b 在排列中的位置早于 a。
最朴素的写法是枚举所有 n! 种排列，逐个验证每条边是否满足顺序约束：
from itertools import permutations
class Solution:
def canFinish_brute(self, numCourses: int, prerequisites: list[list[int]]) -> bool:
for perm in permutations(range(numCourses)):
pos = {c: i for i, c in enumerate(perm)} # 每门课在排列中的位置
ok = True
for a, b in prerequisites: # 边 b → a，要求 pos[b] < pos[a]
if pos[b] >= pos[a]:
ok = False
break
if ok:
return True
return Falseclass SolutionBrute {
public boolean canFinish(int numCourses, int[][] prerequisites) {
int[] perm = new int[numCourses];
for (int i = 0; i < numCourses; i++) perm[i] = i;
return permute(perm, 0, prerequisites);
}
private boolean permute(int[] perm, int k, int[][] prereqs) {
if (k == perm.length) {
int[] pos = new int[perm.length];
for (int i = 0; i < perm.length; i++) pos[perm[i]] = i;
for (int[] p : prereqs) { // p = [a, b]，要求 pos[b] < pos[a]
if (pos[p[1]] >= pos[p[0]]) return false;
}
return true;
}
for (int i = k; i < perm.length; i++) {
int t = perm[k]; perm[k] = perm[i]; perm[i] = t;
if (permute(perm, k + 1, prereqs)) return true;
t = perm[k]; perm[k] = perm[i]; perm[i] = t;
}
return false;
}
}class SolutionBrute {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
vector<int> perm(numCourses);
iota(perm.begin(), perm.end(), 0);
do {
vector<int> pos(numCourses);
for (int i = 0; i < numCourses; i++) pos[perm[i]] = i;
bool ok = true;
for (auto& p : prerequisites) { // p = [a, b]，要求 pos[b] < pos[a]
if (pos[p[1]] >= pos[p[0]]) { ok = false; break; }
}
if (ok) return true;
} while (next_permutation(perm.begin(), perm.end()));
return false;
}
};时间复杂度 O(n! × m)，其中 n = numCourses，m = prerequisites.length。n = 12 时 n! 就接近 5 × 10⁸，n = 20 已经跑不动。题目给的 numCourses 上限是 2000，暴力出不了第一组样例。
更深层的浪费在于：暴力枚举每种顺序时，前缀冲突的信息没有复用。比如尝试 [0, 1, 2, ...] 时发现 0 应该在 1 之后，那 [0, 1, ...] 这一整块前缀的所有排列都不用看了——但 permutations 不知道这一点，仍会一种种试下去。
关键观察：环的判定不需要枚举顺序
换个角度看：能否修完全部课程，等价于有向图里没有环。判断有向图有没有环，根本不需要构造任何一种修课顺序，只要做一遍 DFS：
- 沿着
b → a的方向递归 - 如果走着走着回到了当前递归路径上的某个节点，说明存在环
- 如果一个节点的所有出边都走完了还没遇到环，标记为"安全"
这件事的关键是区分两种"已访问"状态——是"还在当前 DFS 栈里"，还是"已经完整跑完且没有发现环"。如果只用一个 visited[]，碰到 visited 节点没法判断它是不是当前路径上的祖先。
经典写法是三色标记：
- 白（0）：未访问
- 灰（1）：进入了 DFS 但尚未返回，当前在递归栈里
- 黑（2）：DFS 完整返回，子树确认无环
DFS 沿一条边走到下一个节点时：
- 邻居是白色 → 递归进去
- 邻居是灰色 → 走到了递归栈上的祖先，找到环，返回 false
- 邻居是黑色 → 这个子图已经验证过无环，直接跳过
每个节点至多被着色三次（白 → 灰 → 黑），每条边至多被遍历一次，总复杂度 O(V + E)。在 V = 2000, E = 5000 下也就 7000 次基本操作。
下面这个演示走一遍 numCourses = 4, prerequisites = [[1,0],[2,1],[3,2],[1,3]] 的过程。建图后 b → a 的边是 0→1, 1→2, 2→3, 3→1，所以 1 → 2 → 3 → 1 构成一个环：
canFinish 三色 DFS
节点 0..3，邻接表表示 b→a 的有向边。颜色：白=未访问，红=在递归栈中（灰），蓝=完成（黑），金=刚发现环
最终结论：有环，返回 false。整个过程每个节点至多被着色三次、每条边至多被遍历一次，复杂度 O(V + E)。
三色 DFS 解：完整代码
from collections import defaultdict
class Solution:
def canFinish(self, numCourses: int, prerequisites: list[list[int]]) -> bool:
g = defaultdict(list)
for a, b in prerequisites:
g[b].append(a) # 先修 b 才能修 a，所以 b → a
color = [0] * numCourses # 0 白 1 灰 2 黑
def dfs(u: int) -> bool: # 返回 True = 发现环
color[u] = 1
for v in g[u]:
if color[v] == 1:
return True
if color[v] == 0 and dfs(v):
return True
color[u] = 2
return False
for i in range(numCourses):
if color[i] == 0 and dfs(i):
return False # 任意环 → 修不完
return Trueclass Solution {
private List<List<Integer>> g;
private int[] color;
public boolean canFinish(int numCourses, int[][] prerequisites) {
g = new ArrayList<>();
for (int i = 0; i < numCourses; i++) g.add(new ArrayList<>());
for (int[] p : prerequisites) g.get(p[1]).add(p[0]); // b → a
color = new int[numCourses];
for (int i = 0; i < numCourses; i++) {
if (color[i] == 0 && dfs(i)) return false;
}
return true;
}
private boolean dfs(int u) {
color[u] = 1;
for (int v : g.get(u)) {
if (color[v] == 1) return true;
if (color[v] == 0 && dfs(v)) return true;
}
color[u] = 2;
return false;
}
}class Solution {
vector<vector<int>> g;
vector<int> color;
bool dfs(int u) { // 返回 true 表示发现环
color[u] = 1;
for (int v : g[u]) {
if (color[v] == 1) return true;
if (color[v] == 0 && dfs(v)) return true;
}
color[u] = 2;
return false;
}
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
g.assign(numCourses, {});
for (auto& p : prerequisites) g[p[1]].push_back(p[0]); // b → a
color.assign(numCourses, 0);
for (int i = 0; i < numCourses; i++) {
if (color[i] == 0 && dfs(i)) return false; // 任意环 → 修不完
}
return true;
}
};复杂度：时间 O(V + E)、空间 O(V + E)——V = numCourses，E = prerequisites.length，邻接表本身 O(E)、颜色数组 O(V)、递归栈最坏 O(V)。
几个易错点：
- 边的方向。
prerequisites[i] = [a, b]表示b先于a，所以图里是b → a。建图时把a放进g[b]——写反了拓扑序方向会反，但环检测结果不变（反转所有边后是否有环和原图等价）。 - 外层循环。图可能不连通——从节点 0 开始 DFS 只能覆盖 0 所在的连通分量。外层要扫所有节点，遇到白色才启动新的 DFS。
- 递归栈深度。
numCourses ≤ 2000在 Python 默认递归深度 1000 下可能爆栈，写题时手动sys.setrecursionlimit(3000)，或者用 Kahn BFS 完全绕开递归。Java / C++ 默认栈深够用。
下面把图的两种表示、三色 DFS、Kahn BFS 抽出来——这些是后续所有图论章节都要复用的基础工具。
4. 抽象：邻接表 + 三色 DFS + Kahn 拓扑排序
图的两种表示
| 表示 | 存储 | 空间 | 看 u 的邻居 | 看边 (u, v) 是否存在 |
|---|---|---|---|---|
| 邻接表 | 每个节点存一个 list 邻居 | O(V + E) | O(deg(u)) | O(deg(u)) 线性扫 |
| 邻接矩阵 | V × V 的 0/1 矩阵 | O(V²) | O(V) 扫一行 | O(1) 直接索引 |
LC 这类题里 V 上限通常 10⁴ 到 10⁵，邻接矩阵 V² 会爆内存——默认用邻接表（Python 的 defaultdict(list)、Java 的 List<List<Integer>>、Go 的 [][]int 都是标准写法）。
只有当图非常稠密（E ≈ V²）或需要频繁查"边是否存在"且 V ≤ 1000 时（如 LC 547），邻接矩阵才更合适。
三色 DFS 用于环检测
把"已访问"细分成两种状态：
0 = 白：未访问
1 = 灰：在当前 DFS 递归栈中
2 = 黑：DFS 完成，子图无环DFS 处理节点 u：
- 进入
dfs(u)时把color[u]从白染灰 - 遍历所有出边
(u, v)：color[v] == 0：递归dfs(v)，递归返回环就向上传color[v] == 1：找到环，立即返回 truecolor[v] == 2：跳过，已经验证过无环
- 出
dfs(u)前把color[u]从灰染黑
每个节点 push 灰 → pop 黑 的过程对应一次完整 DFS 子树。如果 DFS 后逆序记录"染黑顺序"，就得到一个逆拓扑序——再反转就是拓扑序。这就是 DFS 版本的拓扑排序。
Kahn BFS 拓扑排序
另一种拓扑排序思路完全不用递归，叫 Kahn 算法：
- 算出每个节点的入度（指向它的边数）
- 把所有入度为 0 的节点入队
- BFS：每次出队一个
u，把它的每个出边邻居v的入度减 1。如果v入度变 0，入队 - 出队总数 = 拓扑序
直观上，"入度为 0"意味着"它没有任何未完成的前驱"——可以立刻"修课"。修完它就释放它的所有后继的一个依赖。
环的判定：如果出队总数 < V，说明剩下的节点都有未释放的入度——这堆节点必然构成至少一个环。
DFS 三色版和 Kahn BFS 版都是 O(V + E)，选哪个看个人喜好和题目要求：
- 题目要"任意一个拓扑序" → 两者都行
- 题目要"字典序最小拓扑序" → Kahn + 优先队列（堆）更直接
- 不能用递归（栈深限制） → Kahn
- 同时要环检测 + 子树性质（如祖先关系） → DFS 三色
下面三道例题里，LC 210 给 Kahn BFS 版，LC 547 用 DFS / 并查集都行——把三种主流写法都过一遍。
5. 例题（两道）
下面两道按"问题形态递进"排：输出拓扑序 → 无向图连通分量。每道带 follow-up 直接续到下一题。
5.1 LC 210 课程表 II
链接：LeetCode 210
题意：参数同 LC 207。返回一个合法的修课顺序（任意一个即可）；如果修不完，返回空数组。
数据范围：
numCourses：1 到 2000prerequisites.length：0 到 5000
示例：
输入：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
输出：[0, 1, 2, 3] 或 [0, 2, 1, 3]这次需要真正的拓扑序。两种写法都能做——下面用 Kahn BFS 版（不会爆栈、代码更干净）：
from collections import deque
class Solution:
def findOrder(self, numCourses: int, prerequisites: list[list[int]]) -> list[int]:
g = [[] for _ in range(numCourses)]
indeg = [0] * numCourses
for a, b in prerequisites:
g[b].append(a) # b → a
indeg[a] += 1
q = deque(i for i in range(numCourses) if indeg[i] == 0)
order = []
while q:
u = q.popleft()
order.append(u)
for v in g[u]:
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)
return order if len(order) == numCourses else []class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
List<List<Integer>> g = new ArrayList<>();
for (int i = 0; i < numCourses; i++) g.add(new ArrayList<>());
int[] indeg = new int[numCourses];
for (int[] p : prerequisites) {
g.get(p[1]).add(p[0]); // b → a
indeg[p[0]]++;
}
Deque<Integer> q = new ArrayDeque<>();
for (int i = 0; i < numCourses; i++) {
if (indeg[i] == 0) q.offer(i);
}
int[] order = new int[numCourses];
int k = 0;
while (!q.isEmpty()) {
int u = q.poll();
order[k++] = u;
for (int v : g.get(u)) {
if (--indeg[v] == 0) q.offer(v);
}
}
return k == numCourses ? order : new int[0];
}
}class Solution {
public:
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>> g(numCourses);
vector<int> indeg(numCourses, 0);
for (auto& p : prerequisites) {
g[p[1]].push_back(p[0]); // b → a
indeg[p[0]]++;
}
queue<int> q;
for (int i = 0; i < numCourses; i++) {
if (indeg[i] == 0) q.push(i);
}
vector<int> order;
order.reserve(numCourses);
while (!q.empty()) {
int u = q.front(); q.pop();
order.push_back(u);
for (int v : g[u]) {
if (--indeg[v] == 0) q.push(v);
}
}
return (int)order.size() == numCourses ? order : vector<int>{};
}
};复杂度仍是 O(V + E)。每个节点入队一次、出队一次；每条边在被遍历到时让目标节点的 indeg 减 1。
为什么 len(order) < numCourses 等价于有环？因为一个 DAG 的拓扑序长度一定等于节点数——每个节点最终都会被某个时刻入度归零。如果跑完队列还剩节点没入队，这些节点构成的子图里每个节点都至少有一条来自子图内部的入边，按鸽巢原理必然存在环。
DFS 版输出拓扑序的写法稍微绕——在 dfs(u) 返回前把 u 加到 order 列表，最后把 order 反转就是拓扑序：
# DFS 版输出拓扑序（备选写法）
def findOrder_dfs(self, numCourses, prerequisites):
g = [[] for _ in range(numCourses)]
for a, b in prerequisites:
g[b].append(a)
color = [0] * numCourses
order = []
has_cycle = False
def dfs(u):
nonlocal has_cycle
color[u] = 1
for v in g[u]:
if color[v] == 1:
has_cycle = True
return
if color[v] == 0:
dfs(v)
if has_cycle:
return
color[u] = 2
order.append(u) # 染黑时记录
for i in range(numCourses):
if color[i] == 0:
dfs(i)
if has_cycle:
return []
return order[::-1] # 反转得到拓扑序// DFS 版输出拓扑序（备选写法）
class SolutionDfs {
private List<List<Integer>> g;
private int[] color;
private List<Integer> order;
private boolean hasCycle;
public int[] findOrder(int numCourses, int[][] prerequisites) {
g = new ArrayList<>();
for (int i = 0; i < numCourses; i++) g.add(new ArrayList<>());
for (int[] p : prerequisites) g.get(p[1]).add(p[0]);
color = new int[numCourses];
order = new ArrayList<>(numCourses);
hasCycle = false;
for (int i = 0; i < numCourses; i++) {
if (color[i] == 0) {
dfs(i);
if (hasCycle) return new int[0];
}
}
int[] res = new int[numCourses];
for (int i = 0; i < numCourses; i++) {
res[i] = order.get(numCourses - 1 - i); // 反转
}
return res;
}
private void dfs(int u) {
color[u] = 1;
for (int v : g.get(u)) {
if (color[v] == 1) { hasCycle = true; return; }
if (color[v] == 0) {
dfs(v);
if (hasCycle) return;
}
}
color[u] = 2;
order.add(u); // 染黑时记录
}
}// DFS 版输出拓扑序（备选写法）
class SolutionDfs {
vector<vector<int>> g;
vector<int> color;
vector<int> order;
bool hasCycle = false;
void dfs(int u) {
color[u] = 1;
for (int v : g[u]) {
if (color[v] == 1) { hasCycle = true; return; }
if (color[v] == 0) {
dfs(v);
if (hasCycle) return;
}
}
color[u] = 2;
order.push_back(u); // 染黑时记录
}
public:
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
g.assign(numCourses, {});
for (auto& p : prerequisites) g[p[1]].push_back(p[0]);
color.assign(numCourses, 0);
order.clear();
hasCycle = false;
for (int i = 0; i < numCourses; i++) {
if (color[i] == 0) {
dfs(i);
if (hasCycle) return {};
}
}
reverse(order.begin(), order.end()); // 反转得到拓扑序
return order;
}
};为什么 DFS 染黑时记录 + 反转就是拓扑序？因为节点 u 染黑时，它的所有后继都已经染黑了（先压栈、后弹栈的顺序）。所以 order 列表里后继先于前驱——反转后前驱在前，正好是拓扑序。
Follow-up：上面两题都在有向图上做。如果图是无向的——比如要数一张人际关系图里有多少个独立"朋友圈"呢？
5.2 LC 547 省份数量
链接：LeetCode 547
题意：给 n 座城市，用 n × n 的邻接矩阵 isConnected 表示直接相连关系：isConnected[i][j] = 1 表示城市 i 和 j 直接相连。如果 a 与 b 直接相连、b 与 c 直接相连，那么 a 和 c 也属于同一个省份（连通分量传递）。返回省份总数。
数据范围：
n：1 到 200isConnected[i][j]：0 或 1，isConnected[i][i] = 1，矩阵对称
示例：
输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
输出：2
解释：城市 0 和 1 互相连接成一个省份；城市 2 自成一省。
输入：isConnected = [[1,0,0],[0,1,0],[0,0,1]]
输出：3
解释：三座城市互不相连，三个省份。注意输入是邻接矩阵（题目数据范围 n ≤ 200，200² = 40000 矩阵规模够小）。问题等价于求无向图的连通分量个数——对每个未访问的节点启动一次 DFS / BFS 把它的整个连通分量染掉，启动次数就是答案。
class Solution:
def findCircleNum(self, isConnected: list[list[int]]) -> int:
n = len(isConnected)
visited = [False] * n
def dfs(u: int):
visited[u] = True
for v in range(n):
if isConnected[u][v] == 1 and not visited[v]:
dfs(v)
count = 0
for i in range(n):
if not visited[i]:
count += 1
dfs(i)
return countclass Solution {
private int[][] mat;
private boolean[] visited;
private int n;
public int findCircleNum(int[][] isConnected) {
mat = isConnected;
n = mat.length;
visited = new boolean[n];
int count = 0;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
count++;
dfs(i);
}
}
return count;
}
private void dfs(int u) {
visited[u] = true;
for (int v = 0; v < n; v++) {
if (mat[u][v] == 1 && !visited[v]) dfs(v);
}
}
}class Solution {
int n;
vector<vector<int>>* mat;
vector<bool> visited;
void dfs(int u) {
visited[u] = true;
for (int v = 0; v < n; v++) {
if ((*mat)[u][v] == 1 && !visited[v]) dfs(v);
}
}
public:
int findCircleNum(vector<vector<int>>& isConnected) {
mat = &isConnected;
n = isConnected.size();
visited.assign(n, false);
int count = 0;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
count++;
dfs(i);
}
}
return count;
}
};复杂度：时间 O(n²)（每次访问邻居要扫一整行邻接矩阵），空间 O(n)（visited + 递归栈）。n ≤ 200 下完全够。
几个工程细节：
- 无向图不需要三色。无向图里"走到已访问节点"只可能是走回来的边（父节点）或同一连通分量的横向边，不存在"有向环"概念。一个
visited[]就够。 - 邻接矩阵下扫邻居要扫整行。即使节点
u只有 2 个邻居，也要扫完n列才能确认。这就是为什么n ≤ 200时矩阵 OK、n = 10⁵时必须用邻接表。 - 备选解法是并查集（Union-Find）——遍历矩阵上三角，对每个
isConnected[i][j] = 1做union(i, j)，最后数有多少个不同的根。代码更长但有概念上的优势（在线增加边时仍能维护连通分量）。并查集会在后续 数据结构 章节专题展开。
6. 边界、易错与复杂度
自环与重边
题目偶尔出现 prerequisites[i] = [a, a]（自环）或同一对 (a, b) 出现两次（重边）。两者都不会让代码崩溃，但需要注意：
- 自环直接构成环——三色 DFS 走到自己的灰色版本，立刻返回 true。Kahn 算法里自环节点的入度被自己贡献了 1，永远到不了 0，导致拓扑序长度
< n。两种算法都能正确识别自环为"环"。 - 重边对 DFS 无影响（多走一条边，邻居颜色不变）。对 Kahn 算法，重边会让入度多增 1、出边邻接表多存一份——计数一致，结果正确。
不连通图
一定要对所有节点跑外层循环——LC 207 / 210 的图可能由多个独立连通分量组成，从节点 0 开始只能覆盖 0 所在的分量。外层 for i in range(n) 遇到白色（或入度为 0）就启动一次 DFS / push 进 BFS 队列。
有向图 vs 无向图的环检测
- 有向图：必须用三色（白/灰/黑），单一
visited会漏掉"已经从另一条路径访问过、但不是当前栈祖先"的情况。 - 无向图：单一
visited就够，但要传父节点给递归函数——遇到visited[v] = true且v != parent才算环（否则就是走回父节点的反向边，不算环）。
混淆这两件事是常见 bug：在无向图上用三色 DFS，会把"走回父节点"误判为环；在有向图上只用 visited，会漏掉跨子树的环。
Python 递归栈深度
numCourses ≤ 2000 在 Python 默认递归深度 1000 下不一定够。三个选项：
import sys; sys.setrecursionlimit(10**5)- 用 Kahn BFS 完全绕开递归
- 用显式栈把 DFS 改写为迭代
Java / Go 默认线程栈深度大得多，DFS 一般不会爆栈。
复杂度速查
| 题 | 时间 | 空间 |
|---|---|---|
| LC 207 课程表 | O(V + E) | O(V + E) |
| LC 210 课程表 II | O(V + E) | O(V + E) |
| LC 547 省份数量 | O(n²) 邻接矩阵 | O(n) |
8. 小结
图的两种表示（邻接表 / 邻接矩阵）+ 三色 DFS（环检测）+ Kahn BFS（拓扑排序）是图论题的基础工具箱。掌握后续所有图论章节——最短路、最小生成树、网络流——都建立在这套基本骨架上。下一节 最短路径 把 BFS 推到带权图：Dijkstra / Bellman-Ford / Floyd 三件套。
对应灵神题单：图论 DFS / BFS / 拓扑排序
进一步阅读：灵茶山艾府《图论题单》；LeetCode 拓扑排序标签 高频题