图的存储与遍历

环境：Windows 11 x64，GCC 13.1.0，g++ -std=c++17 -O2。内存数字由重写 operator new 统计，拓扑排序用 400 组随机图与传递闭包对拍。

一、三种存储：内存和建图速度差一个数量级

20 万个节点、每点 10 条出边（共 200 万条边）：

vector<vector<int>>  建图 49.1 ms  遍历 2.0 ms  分配 1000001 次 / 28.2 MB
CSR（offset+column） 建图  6.6 ms  遍历 1.2 ms  分配       3 次 /  9.2 MB
邻接矩阵（位图）     596 MB；同样稀疏度下邻接表只需 7.6 MB

结构	内存	枚举 u 的邻居	加边	适用
邻接矩阵 `bool g[V][V]`	O(V²)	O(1) 判断”有没有边”	O(1)	稠密图、需要频繁判相邻
`vector<vector<int>>`	O(V+E)	每点一段连续内存，但各段分散	摊还 O(1)	通用、边动态增删
CSR（压缩稀疏行）	O(V+E)，无每点开销	完全连续，可向量化	建好后不可增删	静态图、数值计算、图数据库
前向星（`head[]/to[]/next[]`）	O(V+E)，一次分配	链式，随机访问	O(1) 插	竞赛、边数已知且要快速建图

CSR 为什么快：vector<vector<int>> 要为每个节点单独分配一段（20 万次 push_back 触发了 100 万次分配，因为还有倍增），节点之间地址无关；CSR 只有两个数组、3 次分配，遍历时 col[deg[u] .. deg[u+1]) 是一段连续内存。

/* CSR 建图：计数 → 前缀和 → 填充，三趟线性扫描 */
std::vector<int> deg(V + 1, 0);
for (auto [u, v] : edges) deg[u + 1]++;
for (int i = 1; i <= V; i++) deg[i] += deg[i - 1];
std::vector<int> col(edges.size()), cur = deg;
for (auto [u, v] : edges) col[cur[u]++] = v;

邻接矩阵在 20 万节点上要 596MB（位图），而实际只有 200 万条边（稀疏度 0.005%）——稀疏图用矩阵是纯浪费。反过来，如果 V 只有几百且需要大量”u、v 是否相邻”的查询，矩阵的 O(1) 判定完胜。

二、BFS：队列 + 入队时标记

std::vector<int> dist(n, -1);
std::queue<int> q;
dist[src] = 0; q.push(src);                     /* ← 入队时就标记 */
while (!q.empty()) {
    int u = q.front(); q.pop();
    for (int v : adj[u]) if (dist[v] == -1) { dist[v] = dist[u] + 1; q.push(v); }
}

“入队时标记”而不是”出队时标记”：后者会让同一个节点被重复入队多次（高图时指数级膨胀），队列内存和耗时都会爆。这是 BFS 最常见的实现 bug。

无权图最短路径 = BFS，O(V+E)。要分层处理（比如”每一秒同时扩散”）就在循环里先取 q.size() 当本层节点数。

三、DFS：递归的代价是栈，实测 10 万层就崩

同一条链状图（深度 = 节点数），递归版与显式栈版：

迭代（显式栈）  深度 100000 ✅   1000000 ✅   5000000 ✅
递归            深度  10000 ✅   100000 崩溃   200000 崩溃   400000 崩溃

（递归版用 std::function 承载，帧比裸函数更大；即便如此，10 万层就已经撑不住 2MB 栈。）

结论与对策：

图的深度不可控时一律用迭代版。链状图、深嵌套的表达式树、超长的依赖链都很常见。
迭代版必须自己保存”续作状态”。简单场景（只要能到达）压节点即可：

std::vector<int> st{ src };
while (!st.empty()) {
    int u = st.back(); st.pop_back();
    if (seen[u]) continue;
    seen[u] = 1;
    for (int v : adj[u]) if (!seen[v]) st.push_back(v);
}

需要”后序”（如依赖拓扑、表达式求值）时，压 pair<节点, 下一个子节点下标>，或者用”双栈法”（前序变体再倒序输出）。
递归转迭代还要小心：递归版天然是”路径栈”，显式栈版如果只存节点，回溯时的路径信息会丢（比如求所有路径、判环要区分”在当前路径上”和”已访问过”）。

四、拓扑排序：Kahn 算法自带环检测

std::vector<int> indeg(n, 0);
for (auto [u, v] : edges) { g[u].push_back(v); indeg[v]++; }
std::queue<int> q;
for (int i = 0; i < n; i++) if (!indeg[i]) q.push(i);
std::vector<int> order;
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);
}
bool is_dag = (int)order.size() == n;      /* 排不完 → 有环 */

“队列空了但还没处理完所有点”就等价于存在环——这个判据极其简洁，也是它常被选用的原因。

验证正确性不能只看”跑通了”。我用 400 组随机小图做了两件事：① 把 Kahn 的环判定与 Floyd 传递闭包（i→i 有路径即为环）比对；② 对判定为 DAG 的结果，检查输出序是否满足每一条边都向后：

400 组随机图：Kahn 的环判定与传递闭包一致、且输出的序满足所有边=1

注意随机图里我故意允许自环和重边（u == v 和重复边），这两个是拓扑排序实现最常见的翻车点。

五、判环的另一种写法：三色 DFS

需要”输出具体环路径”时用 DFS 染色：白=未访问、灰=在当前路径上、黑=已完成。

/* 0 白 1 灰 2 黑 */
bool dfs(int u) {
    color[u] = 1;
    for (int v : adj[u]) {
        if (color[v] == 1) return true;            /* 指回灰节点 → 找到环 */
        if (color[v] == 0 && dfs(v)) return true;
    }
    color[u] = 2;                                   /* 注意：不是 0！ */
    return false;
}

两个必错点：① 结束时必须置为 **2（黑）**而不是 0，否则会把”DAG 里两条路径汇聚到同一节点”误判成环（这是最经典的错误）；② 遇到灰节点才是环，遇到黑节点直接跳过。

六、强连通分量：Tarjan 与参照实现对拍

Tarjan 一次 DFS 求出所有 SCC，O(V+E)。它难写在于 low 的更新时机：

if (disc[v] == 0) { dfs(v); low[u] = std::min(low[u], low[v]); }        /* 树边：用 low[v] */
else if (on_stack[v]) { low[u] = std::min(low[u], disc[v]); }           /* 后向边：用 disc[v]，不是 low[v] */

“已在栈上才更新，且用 disc[v] 而不是 low[v]” 是 Tarjan 的命门，写错时它仍然会输出结果，只是分量划分悄悄错。

所以别凭感觉调它，配一个暴力参照：用 Floyd 求传递闭包，i 与 j 互相可达即同属一个 SCC，这就是最朴素但绝对正确的分量划分。然后拿随机小图（≤ 20 点、含自环与重边、允许不连通）比对”分量个数 + 每个点的分量编号”。图论代码不靠对拍基本不可能一次写对——上一节我自己写反了两处堆比较方向，就是靠 30 万次随机操作对拍才抓出来的。

七、这一节的自查清单

稀疏图绝不用邻接矩阵；先算一遍 V² 的字节数再决定
静态大图用 CSR，能省 3 倍内存并快 7 倍建图
BFS 在入队时标记 visited
深度不可控的 DFS 用显式栈，并想清楚要不要保存路径状态
拓扑排序用 order.size() != n 判环，别手写额外的检测
三色 DFS 回溯时置”黑”，不是置”白”
图算法一律配一个暴力参照 + 随机小图对拍，且随机数据要含自环、重边、不连通
无向图存边要存两条（u→v 和 v→u），遍历时判 v != parent 而不是判 visited 之前
记得图可能不连通：外层要有”对每个未访问点起一次遍历”的循环

下一节讲排序算法全族：插入/希尔/堆排的适用边界、快排的最坏情况与三路划分、归并与稳定性、基数排序，以及 std::sort 到底做了什么。