图：术语与存储结构

8.1 图是什么：定义、分类与规模

8.1.1 从线性表、树到图：逻辑结构的第三次跳跃

回顾一下我们走过的路。第 02 讲的线性表里，每个元素最多有一个直接前驱和一个直接后继， 元素之间的关系是「一对一」的一条链；第 07 讲的树里，每个结点可以有多个孩子但只有一个双亲， 关系是「一对多」的层次结构。它们都有一个共同的前提：元素之间不允许随便乱连。 可是现实世界并不这么听话——城市之间的航线是对称的、课程之间的先修关系是有方向的、 人与人之间的好友关系既不对称也不分层。

当元素之间的关系变成任意的「多对多」时，线性表和树都不够用了，于是有了图（graph）。 请注意用词：树和图都是「非线性结构」，但树其实是图的一个特例—— 一棵有 n 个结点的树，就是「有 n−1 条边、连通、无回路」的无向图。 换句话说，图是比树更一般的结构，树是加了限制条件的图。 理解了这一点，你就会发现本讲很多术语（路径、连通、生成树）在树那一讲其实已经见过，只是当时不需要强调。

8.1.2 图的严格定义：G = (V, E)

一个图由两部分组成，记作

• 顶点（vertex / node）：也叫结点，是图中的基本元素。顶点集 V 必须是非空有限集合 （教材约定 V ≠ ∅，因为空图没什么好研究的），顶点个数记作 n = |V|。
• 边（edge / arc）：顶点之间的连线。无向边记作 (v, w) 或 vw，圆括号表示无序； 有向边（弧）记作 <v, w>，尖括号表示有序，v 叫弧尾（tail）， w 叫弧头（head），表示「从 v 指向 w」。边数记作 e = |E|。
• 顶点集不能为空，但边集可以为空：E = ∅ 时，图里只有 n 个孤零零的顶点，一条边也没有。 这种图叫零图，n = 1 时叫平凡图。

一个常见的追问是：「图里到底存不存顶点本身的数据？」 答案是：数学意义上的图只关心「谁和谁连着」，不关心顶点上挂的信息。 但工程实现时（比如导航软件）我们会给顶点加上名字、经纬度，给边加上长度、限速—— 这些叫权（weight），加了权的图叫网（network），见 8.2.6 节。

用集合的方式描述图，有个好处：顶点编号完全可以重新排列。 把 {0,1,2} 改叫 {A,B,C}，图的性质一点都不变。这叫图的同构（isomorphism）思想—— 以后你写程序时看到「图长得不一样但答案一样」，就不必惊讶了。

8.1.3 有向图、无向图、简单图、多重图、自环

按边的性质，图可以分成几类，这些分类决定了后面存储结构和算法细节的选择：

无向图 undirected graph

每条边都是无向边，(v, w) 与 (w, v) 是同一条边。例：好友关系、无向路网。

有向图 directed graph / digraph

每条边都是有向边（弧），<v, w> 与 <w, v> 是两条不同的弧。例：微博关注、课程先修、网页链接。

简单图 simple graph

满足两条：不存在自环，且任意两点之间至多一条边（有向图里是至多一条同向弧）。本讲后面谈「完全图」「邻接矩阵」时，默认都是简单图。

多重图 multigraph

允许两个顶点之间有多条边（平行边 / 重边）。例：两座城市之间有多条航线；此时邻接矩阵只能存「边的条数」或「最小权值」，不能只存 0/1。

自环 self-loop

边的两个端点重合，即 (v, v)。自环让该顶点的度增加 2（无向图），在邻接矩阵里表现为对角线上的 1。

稀疏图 / 稠密图

边数远小于 n² 的叫稀疏图，接近 n² 的叫稠密图。这只是「感觉」，工程上常取 e < n log n（或 e < n²/10）作为分界。

8.1.4 完全图、稠密图与稀疏图：n 与 e 的取值范围

一张有 n 个顶点的简单图，最多能有多少条边？这就是完全图（complete graph）要回答的问题。

无向完全图：任意两个顶点之间都恰好有一条边。数一数：n 个顶点两两配对，共有 C(n, 2) = n(n−1)/2 条边。所以简单无向图的边数范围是

有向完全图：任意两个顶点之间都有一对方向相反的弧。每一对顶点贡献 2 条弧，所以边数上限翻倍：

例如 n = 8 时，无向完全图有 8×7/2 = 28 条边，有向完全图有 8×7 = 56 条弧。 而本讲贯穿全篇的示例图只有 9 条边——它是典型的稀疏图（9 远远小于 28）。

8.2 图的术语体系：把「图的语言」说利索

8.2.1 邻接点与度

如果两个顶点之间有一条边，就说它们互为邻接点（adjacent），这条边与这两个顶点相关联（incident）。 在无向图里，「相邻」是对称的：v 与 w 相邻 ⟺ w 与 v 相邻。

度（degree） 是图论里出现频率最高的概念：顶点 v 的度 d(v)，就是与它相关联的边的条数。 一个小坑：自环对度的贡献是 2，因为这条边的两个端点都是 v，它「进出各算一次」。 度数为 0 的顶点叫孤立点（isolated vertex），度数为 1 的顶点叫悬挂点（pendant vertex）， 与悬挂点相连的那条边叫悬挂边。

在有向图里，「度」被拆成两个方向：入度（in-degree）ID(v) 是以 v 为弧头的弧的条数， 出度（out-degree）OD(v) 是以 v 为弧尾的弧的条数，二者之和就是该顶点的度 d(v) = ID(v) + OD(v)。注意自环在有向图里会同时给入度和出度各加 1。

下面图 8-2 把所有术语都标在了同一张图上。请对照着把每个数字自己算一遍—— 这一步花三分钟，后面所有算法都会轻松很多。

8.2.2 入度与出度：有向图的两套账

有向图必须把「度」拆成入度和出度，因为方向决定了「能不能走出去」。 一个出度为 0 的顶点叫汇点（sink），一个入度为 0 的顶点叫源点（source）； 这两类点在拓扑排序、网络流里都是重点关注对象。

8.2.3 握手定理：证明与例题

整章最重要的一个定量结论来了。它有一个形象的名字：握手定理（handshaking lemma）—— 想象一次聚会，每握一次手都要用到两只手，所以「所有人握手的次数总和」一定是偶数。

证明（无向图，用「算两次」的方法）：

1. 把图中所有顶点 v 的度数 d(v) 加起来，得到 S = Σ d(v)。
2. 换个角度数同一个 S：每一条边 (u, w) 的端点有两个，它给 d(u) 贡献 1，也给 d(w) 贡献 1，所以每条边对 S 的贡献恰好是 2。
3. e 条边总共贡献 2e，于是 S = 2e。∎

第 2 步里「每条边被数了两次」，正是「握手要两只手」的严格表述。这个证明短得出奇，但它有三个威力巨大的推论：

推论 2 有个漂亮的应用：任何一张图的奇度顶点个数都是偶数，所以「只有 1 个奇度顶点」的图不存在。 这也直接决定了欧拉路径的判定条件（见 8.9.4）。

#include <bits/stdc++.h>
using namespace std;

/* ============================================================
   握手定理的代码验证：Σdeg(v) == 2e
   顺便演示"能否构成无向图"的判定

   竞赛写法：链式前向星（数组模拟邻接表），
   与第 08 讲 8.4 节、第 09 讲 graph_base.cpp 完全同一套模板：
       head[u] = u 的第一条出边下标（-1 表示没有）
       to[i] / nxt[i] = 第 i 条边的终点 / 同起点的下一条边
   另外用 eu[] / ev[] 存下每条边的两个端点，deg[] 顺手统计度数。
   ============================================================ */

const int MAXN = 100005;        /* 顶点数上限 */
const int MAXM = 200005;        /* 边数上限（无向图要开 2 倍） */

int head[MAXN], to[MAXM], nxt[MAXM];
int eu[MAXM], ev[MAXM];         /* 第 i 条边的两个端点（无向边只记一次） */
int deg[MAXN];                  /* deg[v] = 顶点 v 的度数 */
int n, etot = 0;                /* n 个顶点，etot 条边 */

void initGraph(int n_) {
    n = n_;
    memset(head, -1, sizeof(head));    /* -1 表示"链表为空"，加边前必须做 */
    memset(deg, 0, sizeof(deg));
    etot = 0;
}

/* 加一条无向边：给两个端点各 +1 度，注意在无向图里这是一条边，不是两条 */
void addEdge(int u, int v) {
    eu[etot] = u; ev[etot] = v;

    to[etot] = v; nxt[etot] = head[u]; head[u] = etot; ++etot;   /* u -> v */
    to[etot] = u; nxt[etot] = head[v]; head[v] = etot; ++etot;   /* v -> u */

    deg[u]++; deg[v]++;                /* 无向边给两个端点各 +1 */
}

int sumDeg() {
    int s = 0;
    for (int v = 0; v < n; ++v) s += deg[v];
    return s;
}

/* 给定度数序列，判断是否存在一个无向简单图（只用必要条件做快速否定） */
bool possible(const vector<int>& d) {
    int cnt = d.size(), s = 0, odd = 0;
    for (int x : d) { s += x; if (x & 1) odd++; if (x < 0 || x >= cnt) return false; }
    if (s % 2 != 0) return false;        // 度数之和必须是偶数
    if (odd % 2 != 0) return false;      // 奇度顶点个数必须是偶数（上一条的推论）
    return true;                         // 只是必要条件，充分性要用 Havel-Hakimi
}

int main() {
    initGraph(8);
    int E[9][2] = {{0,1},{0,6},{1,2},{1,7},{2,3},{3,4},{4,5},{5,6},{5,7}};
    for (int i = 0; i < 9; ++i) addEdge(E[i][0], E[i][1]);

    cout << "e = " << etot / 2 << "\n";                     // 9（无向边存了两条弧，别忘除以 2）
    for (int v = 0; v < n; ++v) cout << deg[v] << " ";      // 2 3 2 2 2 3 2 2
    cout << "\nΣdeg = " << sumDeg() << " , 2e = " << 2 * (etot / 2) << "\n";  // 18 18

    /* 顺带验证链式前向星没建错：顶点 0 的邻接点个数应当等于 deg[0] */
    int cnt0 = 0;
    for (int i = head[0]; i != -1; i = nxt[i]) ++cnt0;
    if (cnt0 != deg[0]) printf("forward star error!\n");   /* 正常情况不会打印 */

    vector<int> d1 = {3,3,3,3,3,3,3,3,3,3};
    vector<int> d2 = {3,3,3,3,3,3,3,3,3,2};
    cout << possible(d1) << "\n";        // 1：10 个 3 度点，和为 30，可行
    cout << possible(d2) << "\n";        // 0：和为 29 是奇数，不可能
    return 0;
}

8.2.4 路径、简单路径、回路与简单回路

路径（path）是从顶点 v 出发，经过一系列边到达顶点 w 的顶点序列， 例如 0 → 1 → 2 → 3。路径上边的条数叫路径长度（length）—— 注意教材里「长度」数的是边而不是顶点，别数错了。

• 简单路径（simple path）：路径上的顶点不重复出现（起点与终点也不重合）。
• 回路 / 环（cycle）：起点与终点相同的路径，例如 0-1-2-3-4-5-6-0。
• 简单回路（simple cycle）：除起点=终点外，其余顶点都不重复的回路。图 8-2 中的 0-1-7-5-6-0 就是一条简单回路。
• 有向路径 / 有向回路：有向图里要求每一段都沿着弧的方向走。 A→B→C→A 是有向回路，但 A→B→C 之后再想「回」到 A 就必须有弧 C→A。

8.2.5 连通、连通图、连通分量、强连通分量

连通（connected）是只对无向图说的：如果顶点 u 到 v 存在路径，就说 u 与 v 连通。 若图中任意两个顶点都连通，则称这张无向图是连通图（connected graph）。 图 8-2 的示例图就是连通的，你可以验证任意两点之间都能走通。

连通分量（connected component）是无向图里「极大的连通子图」： 把图拆成若干块，每块内部连通，块与块之间不连通，这些块就是连通分量。 关键词是极大——只要能再加一个顶点进去还保持连通，就说明还没取到极大。 连通图的连通分量个数是 1；孤立点自己单独构成一个连通分量。

有向图不能简单说「连通」，要分成三个层次：

强连通 strongly connected

有向图中，若对任意两个顶点 u、v，既有 u 到 v 的路径，也有 v 到 u 的路径，则称图强连通。注意是「双向可达」，缺一不可。

强连通分量 SCC

有向图的极大强连通子图，记作 强连通分量（Strongly Connected Component）。任何一个有向图都可以唯一地分解成若干强连通分量。求 SCC 的两大算法是 Kosaraju 与 Tarjan，属于下一讲的内容。

单向连通 / 弱连通

若任意两点之间至少有一个方向可达，称单向连通；若把弧都当成无向边后图是连通的，称弱连通。层次关系：强连通 ⟹ 单向连通 ⟹ 弱连通。

图 8-3 中的有向图：{A,B,C} 内部两两可达，是一个强连通分量； D、E 各自单独成为强连通分量（单个顶点永远强连通）。 把每个强连通分量「缩」成一个点，得到的图一定是 DAG（有向无环图）——这是缩点法的理论基础。

8.2.6 子图、生成树、生成森林、网与 DAG

子图 subgraph

从原图中选出部分顶点和部分边构成的图，记作 G' ⊆ G：要求 V' ⊆ V、E' ⊆ E，且 E' 中的边端点都在 V' 里。若 V' = V，叫生成子图。

生成树 spanning tree

连通无向图的一个生成子图，它同时是一棵树（连通 + 无回路）。n 个顶点的连通图，其生成树恰好有 n−1 条边。图 8-2 里的粗线就是一棵生成树。

生成森林 spanning forest

非连通图的每个连通分量各取一棵生成树，合起来就是生成森林，共 n − k 条边（k 为连通分量个数）。

网 network / 带权图

边上带有数值（权值，如距离、费用、时间）的图叫网。带权图的邻接矩阵存的不再是 0/1 而是权值，无边处存 ∞。最短路径、最小生成树都是网上的问题。

有向无环图 DAG

Directed Acyclic Graph，不存在有向回路的图。它是「可以拓扑排序」的等价说法，用于任务调度、依赖解析、动态规划的状态转移图。

稠密图与稀疏图

见 8.1.3。选择邻接矩阵还是邻接表，第一步就是判断图的疏密。

8.2.7 术语总表（考前速查）

下面这张表把本章出现的术语一次收齐，建议对照图 8-2、图 8-3 逐个指着念一遍：

顶点 vertex

图的基本元素，记 n = |V|。

边 / 弧 edge / arc

顶点间的连线，记 e = |E|。无向边 (v,w)，有向弧 <v,w>。

邻接点 adjacent

被同一条边连接的两个顶点互为邻接点。

度 degree

无向图中与 v 关联的边数 d(v)；自环贡献 2。

入度 in-degree

有向图中以 v 为弧头的弧数 ID(v)。

出度 out-degree

有向图中以 v 为弧尾的弧数 OD(v)。

握手定理

Σd(v) = 2e；有向图 ΣID = ΣOD = e。推论：奇度顶点个数为偶数。

路径 path

顶点与边的交替序列；长度 = 边的条数。

简单路径

顶点不重复出现的路径。

回路 cycle

起点与终点相同的路径，也叫环。

简单回路

除起终点外顶点不重复的回路。

连通 connected

无向图中两点之间存在路径。

连通图

任意两点都连通的无向图。

连通分量

无向图的极大连通子图；个数用 DFS/BFS 扫描求得。

强连通图

有向图中任意两点互相可达。

强连通分量 SCC

有向图的极大强连通子图；缩点后得到 DAG。

子图 subgraph

顶点集与边集都是原图子集的图。

生成树

连通图的极小连通生成子图，恰有 n−1 条边。

生成森林

各连通分量生成树的并，共 n−k 条边。

网 network

边上带权的图；邻接矩阵中无边处记 ∞。

DAG

有向无环图，可拓扑排序。

完全图

任意两点间都有边；无向 n(n−1)/2 条，有向 n(n−1) 条。

稀疏图 / 稠密图

按 e 相对 n² 的大小划分，常以 e < n log n 为稀疏的分界。

自环 / 重边

端点重合的边 / 两点间的多条边；两者都会破坏「简单图」的前提。

欧拉路径 / 欧拉回路

经过每条边恰好一次的路径 / 回路；判定见 8.9.4。

割点 / 桥

删掉后使连通分量个数增加的顶点 / 边；见 8.9.2。

8.3 存储结构（一）：邻接矩阵

8.3.1 定义：用一个二维数组记录「谁和谁相邻」

图的逻辑结构是「多对多」，而计算机的内存是一维线性的，所以我们必须想办法把关系「压平」。 最朴素的想法是：把所有顶点两两之间的关系都记下来，做成一张 n×n 的表格。这就是邻接矩阵（adjacency matrix）。

设图 G = (V, E)，V = {v0, v1, …, vn−1}，用一个二维数组 A[n][n] 表示：

注意「顶点必须编号」。矩阵的行列下标就是顶点编号，所以建图前要先给顶点编好 0..n−1 的号 （或者把字符串名字用 map<string,int> 映射成整数），这也是几乎所有图论题目的第一步。

无向图：矩阵一定对称

无向边 (u, v) 既是 u 的边也是 v 的边，所以在矩阵里要写 两格： A[u][v] = 1 且 A[v][u] = 1。于是无向图的邻接矩阵必然满足 A[i][j] = A[j][i]，即关于主对角线对称。

反过来，有向图的邻接矩阵一般不对称：A[i][j] = 1 表示有弧 i→j， 至于 j 能不能走到 i，要看 A[j][i] 是不是 1。这个差别让「求度」的公式也分成了两套（见 8.3.3）。

有向图：行和是出度，列和是入度

有向图的矩阵把方向信息直接编码进了下标顺序：A[i][j] = 1 读作「有一条从 i 出发、 指向 j 的弧」。所以第 i 行非零元素的个数就是 i 的出度，第 i 列非零元素的个数就是 i 的入度。 这个「行出列入」的口诀请务必背下来，考试里求入度出度的题基本都靠它。

8.3.2 与第 06 讲的对称矩阵压缩存储接上头

第 06 讲我们讲过：如果一个 n×n 矩阵满足 A[i][j] = A[j][i]，它就是对称矩阵， 可以把 n² 个元素压缩进 n(n+1)/2 个单元，只存下三角（含对角线）。 映射公式是（行优先，下标从 0 开始）：

无向图的邻接矩阵天然满足对称性，所以理论上也能这么压。n = 1000 时， n² = 1,000,000 而 n(n+1)/2 ≈ 500,500，省了一半。 但是——实际写图论程序时几乎没人压缩，原因有三个：

1. 压缩后取值要算下标（多一次乘法与除法），代码复杂度上去了，常数也变大了；
2. 稀疏图用邻接矩阵本来就是错的选择，压缩只是把「浪费」从 100% 降到 50%，治标不治本；
3. 带权图要存 ∞，压缩后还要额外判断「这一格到底存过没存过」，得不偿失。

所以考试里「无向图的邻接矩阵是对称矩阵，可压缩存储」这句话你要会判断， 但写代码时请老老实实用二维数组或者干脆换邻接表。

8.3.3 从矩阵能读出什么：度、邻接判断、邻接点枚举

8.3.4 空间复杂度 O(n²)：与边数无关的代价

邻接矩阵占 n² 个存储单元，与边数 e 完全无关。 这意味着：一张有 10000 个顶点、却只有 100 条边的稀疏图（比如一个社交网络的局部）， 用邻接矩阵要开 108 个 int，约 400 MB——直接内存超限； 而用邻接表只需要 n + 2e ≈ 10200 个单元，差了一万倍。

反过来，如果图很稠密（e ≈ n²/2），两者空间同阶，邻接矩阵因为实现简单、 访问连续反而更快。所以选择存储结构的第一原则永远是：先看图的疏密，再看需要的操作。

还有一个非常实用的技巧要在这里讲清楚：用 0x3f3f3f3f 表示无穷大 INF。 带权图的邻接矩阵里，两个不相邻的顶点之间的距离要填 ∞。C++ 里现成的 INT_MAX 是 2147483647，看起来正合适，但它在做松弛运算时会出事：

#include <climits>
#include <cstring>
#include <iostream>
using namespace std;

/* ============================================================
   带权图的邻接矩阵（网）与 INF 的选取
   ============================================================ */
const int MAXN = 105;
const int INF  = 0x3f3f3f3f;        // 1061109567

int W[MAXN][MAXN];

/* ---------- 为什么不用 INT_MAX？ ----------
   Dijkstra / Floyd 里到处都有 W[u][v] + W[v][w] 这样的松弛运算。
   若用 INT_MAX：
       INT_MAX + INT_MAX = 4294967294  →  超出 int 上限，有符号溢出（未定义行为）
       INT_MAX + 一条正常边权         →  同样溢出
   若用 0x3f3f3f3f：
       0x3f3f3f3f + 0x3f3f3f3f = 2122219134 < INT_MAX = 2147483647  →  安全
       “两个 INF 相加仍是（更大的）有限数，不会变成负数”是它最大的价值。 */

void initWeighted(int n) {
    memset(W, 0x3f, sizeof(W));     // 逐字节填 0x3f，每个 int 恰好变成 0x3f3f3f3f
    for (int i = 0; i < n; ++i) W[i][i] = 0;   // 自己到自己的距离为 0
}

void addWeightedEdge(int u, int v, int w) {    // 无向网：对称写两格
    W[u][v] = W[v][u] = w;
}

int main() {
    initWeighted(5);
    addWeightedEdge(0, 1, 4);
    addWeightedEdge(1, 2, 3);
    addWeightedEdge(0, 2, 9);
    addWeightedEdge(2, 3, 7);

    cout << "W[0][1] = " << W[0][1] << "\n";                 // 4
    cout << "W[0][4] = " << W[0][4] << "  (即 INF)\n";       // 1061109567
    cout << "INF*2  = " << INF * 2 << "\n";                  // 2122219134，未溢出
    cout << "INT_MAX= " << INT_MAX << "\n";                 // 2147483647
    cout << "W[0][4] + W[4][0] = " << W[0][4] + W[4][0] << "  ← 两个 INF 相加仍安全\n";
    return 0;
}

8.3.5 邻接矩阵的完整 C++ 实现

下面这份代码把「建图 → 求度 → 判相邻 → DFS → BFS」串成了一条完整链路，可以直接编译运行。 注意 addEdge 里的对称赋值，以及矩阵版 DFS 为什么必须扫描整行。

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

/* ============================================================
   邻接矩阵版：无向无权图
   A[i][j] = 1 表示有边，0 表示无边
   ============================================================ */
const int MAXN = 105;
int A[MAXN][MAXN];              // 全局数组，自动全部清零
int n = 8, e = 0;               // 顶点数、边数

void addEdge(int u, int v) {
    if (A[u][v]) return;        // 已经有边（重边）就不再计数
    A[u][v] = A[v][u] = 1;      // 无向图：对称写两格
    ++e;
}

int degree(int u) {             // 无向图求度：第 u 行之和
    int s = 0;
    for (int v = 0; v < n; ++v) s += A[u][v];
    return s;
}

bool adjacent(int u, int v) { return A[u][v] != 0; }   // O(1) 判相邻

/* ---------- 邻接矩阵上的 DFS：每个顶点要扫一整行 ---------- */
void dfs(int u, vector<bool>& vis, vector<int>& order) {
    vis[u] = true;
    order.push_back(u);
    for (int v = 0; v < n; ++v)          // 注意是 O(n)，不是 O(deg(u))
        if (A[u][v] && !vis[v]) dfs(v, vis, order);
}

/* ---------- 邻接矩阵上的 BFS：顺带求无权最短路 ---------- */
vector<int> bfs(int s) {
    vector<int> dist(n, -1), order;
    queue<int> q;
    dist[s] = 0; q.push(s);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);
        for (int v = 0; v < n; ++v)
            if (A[u][v] && dist[v] == -1) { dist[v] = dist[u] + 1; q.push(v); }
    }
    cout << "dist[] = ";
    for (int x : dist) cout << x << " ";
    cout << "\n";
    return order;
}

int main() {
    int E[9][2] = {{0,1},{0,6},{1,2},{1,7},{2,3},{3,4},{4,5},{5,6},{5,7}};
    for (int i = 0; i < 9; ++i) addEdge(E[i][0], E[i][1]);

    cout << "n = " << n << ", e = " << e << "\n";
    int sum = 0;
    for (int u = 0; u < n; ++u) { int d = degree(u); sum += d; cout << "deg(" << u << ")=" << d << " "; }
    cout << "\nΣdeg = " << sum << " = 2e = " << 2 * e << "\n";
    cout << "0 与 1 相邻? " << (adjacent(0, 1) ? "yes" : "no") << "\n";   // yes
    cout << "0 与 2 相邻? " << (adjacent(0, 2) ? "yes" : "no") << "\n";   // no

    vector<bool> vis(n, false);
    vector<int> ord;
    dfs(0, vis, ord);
    cout << "DFS: "; for (int x : ord) cout << x << " "; cout << "\n";     // 0 1 2 3 4 5 6 7
    cout << "BFS: "; for (int x : bfs(0)) cout << x << " "; cout << "\n";  // 0 1 6 2 7 5 3 4
    return 0;
}

下面用同一张示例图，逐条边演示矩阵是怎么被填出来的。注意每一步都同时点亮两格——这就是对称性的来源：

8.4 存储结构（二）：邻接表家族

8.4.1 邻接表：只存真正存在的边

邻接矩阵的浪费来自「把不存在的边也记下来了」。邻接表的思路非常自然： 为每个顶点挂一条链表，链表中只存它真正的邻接点。 具体由两部分组成：

• 顶点表（vertex array）：长度为 n 的一维数组，第 i 项存顶点 i 的信息（名字 / 数据）以及 指向它第一条出边的指针 firstEdge（或叫 head[i]）。
• 边结点（edge node）：每个边结点至少有两个域——adjvex（该边另一端顶点的下标） 和 next（指向下一条边的指针）。带权图再加一个 weight 域。

于是「枚举顶点 u 的所有邻接点」就变成了「遍历 u 的链表」，花费的时间正比于 u 的度， 而不是 n。这就是邻接表相对邻接矩阵最本质的优势。

8.4.2 边结点数、求度，以及「入度不方便」引出的逆邻接表

邻接表有一个必须记牢的数字：无向图的边结点数是 2e，有向图是 e。 原因很简单——无向图的一条边 (u,v) 在数学上是一个对象，但在邻接表里必须 在 u 的链表和 v 的链表中各出现一次；有向图的弧 u→v 只出现在 u 的链表里， 所以正好 e 个。这也解释了 8.5 节对比表里的空间公式 O(n + 2e) = O(n + e)。

注意倒数第二行：判断两点是否相邻，邻接表反而比邻接矩阵慢。 这是「没有免费午餐」的典型例子——邻接表省了空间、快了遍历，代价是查边变慢。

有向图的入度问题怎么解决？答案是再建一张逆邻接表（inverse adjacency list）： 它的链表里存的是指向自己的那些顶点。有了逆邻接表，求入度就变成「遍历自己的逆链表」， 也是 O(deg) 了。当然代价是空间翻倍，所以通常只在确实需要频繁问入度时才建 （例如拓扑排序的 Kahn 算法、Tarjan 求强连通分量）。

小技巧：如果图是静态的、不常改动，也可以干脆同时维护正向与逆向两套 vector， 建图时各 push_back 一次，代码几乎不增加复杂度，却把出入度都变成了 O(1) 级访问。

8.4.3 邻接表的 C++ 实现（vector 版，最省心）

在 C++ 里，最省心的邻接表写法是 vector<vector<int> >： 外层 vector 对应顶点表，内层 vector 就是那条链表。 它不需要手写指针、不需要预先知道边数、还能用范围 for 循环遍历，非常适合教学与刷题。

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

/* ============================================================
   邻接表版（vector<vector<int> >）：最省心的写法
   无向图：addEdge 调用两次     有向图：只调用一次
   ============================================================ */
const int MAXN = 100005;
vector<int> g[MAXN];            // g[u] 里存 u 的所有邻接点
int n = 8;

void addEdge(int u, int v) {    // 无向边
    g[u].push_back(v);
    g[v].push_back(u);
}
/* 若是有向图，只写 g[u].push_back(v); 一行即可 */

int degree(int u) { return (int)g[u].size(); }   // 无向图的度 = 链表长度

void dfs(int u, vector<bool>& vis, vector<int>& order) {
    vis[u] = true;
    order.push_back(u);
    for (int v : g[u])                       // 只遍历真实存在的边 → O(deg(u))
        if (!vis[v]) dfs(v, vis, order);
}

vector<int> bfs(int s) {
    vector<int> dist(n, -1), order;
    queue<int> q;
    dist[s] = 0; q.push(s);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);
        for (int v : g[u])
            if (dist[v] == -1) { dist[v] = dist[u] + 1; q.push(v); }
    }
    return order;
}

int main() {
    int E[9][2] = {{0,1},{0,6},{1,2},{1,7},{2,3},{3,4},{4,5},{5,6},{5,7}};
    for (int i = 0; i < 9; ++i) addEdge(E[i][0], E[i][1]);
    for (int u = 0; u < n; ++u) sort(g[u].begin(), g[u].end());   // 升序枚举

    int total = 0;
    for (int u = 0; u < n; ++u) {
        cout << u << " 的邻接点: ";
        for (int v : g[u]) cout << v << " ";
        cout << " 度=" << degree(u) << "\n";
        total += degree(u);
    }
    cout << "所有链表长度之和 = " << total << " = 2e = " << 2 * 9 << "\n";

    vector<bool> vis(n, false); vector<int> ord;
    dfs(0, vis, ord);
    cout << "DFS: "; for (int x : ord) cout << x << " "; cout << "\n";
    cout << "BFS: "; for (int x : bfs(0)) cout << x << " "; cout << "\n";
    return 0;
}

8.4.4 链式前向星：竞赛选手的主流写法

vector<vector<int> > 虽然好写，但有两个隐患： 一是每个顶点的 vector 都要单独申请堆内存，内存不连续、缓存不友好， 在 10⁶ 级别的数据上常数明显偏大；二是频繁 push_back 可能触发扩容。 于是竞赛圈广泛使用一种「用数组模拟链表」的写法——链式前向星（forward star）。

它只需要三个（带权时四个）一维数组：

head[u]

以 u 为起点的「第一条边」在边数组中的下标；没有出边时为 −1。

to[idx]

第 idx 条边的终点（弧头）。

nxt[idx]

与第 idx 条边同起点的下一条边的下标，构成链表的后继指针；没有则为 −1。

w[idx]

第 idx 条边的权值（无权图可省略）。

插入一条边 u→v 只有三行：

三行的含义分别是「记录终点」「把新结点接在原来的链表头部」「让 head 指向新结点」。 因为是头插法，枚举顺序与插入顺序相反——这一点在需要固定遍历顺序时要注意。 遍历顶点 u 的所有出边，写成一行经典的 for 循环：

#include <cstring>
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

/* ============================================================
   链式前向星（数组模拟邻接表）—— 竞赛主流写法
   head[u] : u 的第一条出边下标（-1 表示没有）
   to[i]   : 第 i 条边的终点
   nxt[i]  : 与第 i 条边同起点的下一条边
   w[i]    : 第 i 条边的权值
   ============================================================ */
const int MAXN = 100005;      // 顶点数上限
const int MAXM = 200005;      // 边数上限（无向图要开 2 倍）

int head[MAXN], to[MAXM], nxt[MAXM], w[MAXM];
int idx = 0;                  // 下一个可用的边结点下标

void initGraph() {
    memset(head, -1, sizeof(head));   // -1 表示“链表为空”
    idx = 0;
}

/* 加一条有向边 u -> v，权值为 c；无向边请调用两次 */
void addEdge(int u, int v, int c = 1) {
    to[idx]  = v;
    nxt[idx] = head[u];       // 新结点接在头部
    w[idx]   = c;
    head[u]  = idx;
    ++idx;
}

/* 遍历 u 的所有出边：这是链式前向星最经典的循环 */
void listEdges(int u) {
    cout << u << " 的出边: ";
    for (int i = head[u]; i != -1; i = nxt[i])
        cout << "(" << u << "->" << to[i] << ",w=" << w[i] << ") ";
    cout << "\n";
}

void dfs(int u, vector<bool>& vis, vector<int>& order) {
    vis[u] = true;
    order.push_back(u);
    for (int i = head[u]; i != -1; i = nxt[i])
        if (!vis[to[i]]) dfs(to[i], vis, order);
}

vector<int> bfs(int s, int n) {
    vector<int> dist(n, -1), order;
    queue<int> q;
    dist[s] = 0; q.push(s);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);
        for (int i = head[u]; i != -1; i = nxt[i]) {
            int v = to[i];
            if (dist[v] == -1) { dist[v] = dist[u] + 1; q.push(v); }
        }
    }
    return order;
}

int main() {
    int n = 8;
    initGraph();
    int E[9][2] = {{0,1},{0,6},{1,2},{1,7},{2,3},{3,4},{4,5},{5,6},{5,7}};
    for (int k = 0; k < 9; ++k) {         // 无向图 → 每条边插两次
        addEdge(E[k][0], E[k][1]);
        addEdge(E[k][1], E[k][0]);
    }
    cout << "边结点总数 = " << idx << "（无向图 = 2e = 18）\n";   // 18

    for (int u = 0; u < n; ++u) listEdges(u);

    vector<bool> vis(n, false); vector<int> ord;
    dfs(0, vis, ord);
    cout << "DFS: "; for (int x : ord) cout << x << " "; cout << "\n";
    cout << "BFS: "; for (int x : bfs(0, n)) cout << x << " "; cout << "\n";
    return 0;
}

下面这个动画用同一张示例图，把 18 个边结点一条一条插进去，你可以盯着 head 的变化看—— 它永远指向最新插入的那条边：

8.4.5 十字链表：有向图的「出入两全」结构

邻接表存有向图的痛点是：出边很好找，入边很难找。能不能让每个顶点同时掌握自己的出边链和入边链？ 能，这就是十字链表（orthogonal list / cross list）。 它把邻接表与逆邻接表「交叉」在一起，所以叫十字链表。

结构分两部分：

顶点结点

三个域：data（数据）、firstIn（指向第一条以我为弧头的边结点，即入边链）、firstOut（指向第一条以我为弧尾的边结点，即出边链）。

边结点（弧结点）

四个域：tailVex（弧尾顶点下标）、headVex（弧头顶点下标）、hLink（指向同一个弧头的下一条弧，串起入边链）、tLink（指向同一个弧尾的下一条弧，串起出边链）。

记忆口诀：t 开头管尾巴（tail），h 开头管脑袋（head）。 于是：顺着 firstOut 走 tLink，得到该顶点的全部出边； 顺着 firstIn 走 hLink，得到该顶点的全部入边。 求入度和出度都变成了 O(deg)，而且每条弧只存一个结点，空间仍是 O(n + e)。

代价是每个边结点要多一个指针域，指针维护也更复杂，所以十字链表主要用于 需要频繁修改、且同时关心出入边的有向图场景（例如某些编译器中的依赖图、网络流建模）。

#include <iostream>
#include <vector>
using namespace std;

/* ============================================================
   十字链表（orthogonal list）—— 有向图专用
   顶点结点：data + firstIn + firstOut
   弧结点  ：tailVex + headVex + hLink + tLink
   每条弧只存一个结点；出边链沿 tLink 走，入边链沿 hLink 走
   ============================================================ */
struct ArcBox {                  // 弧结点
    int tailVex, headVex;        // 弧尾、弧头顶点下标
    int hLink, tLink;            // 同弧头的下一条弧 / 同弧尾的下一条弧（数组下标，-1 表示空）
    int weight;
};

struct VexNode {                 // 顶点结点
    int data;
    int firstIn, firstOut;
};

vector<VexNode> vex;
vector<ArcBox>  arc;

void initOL(int n) {
    vex.assign(n, VexNode());
    for (int i = 0; i < n; ++i) { vex[i].data = i; vex[i].firstIn = -1; vex[i].firstOut = -1; }
    arc.clear();
}

/* 插入一条弧 u -> v */
void addArc(int u, int v, int w = 1) {
    ArcBox a;
    a.tailVex = u; a.headVex = v; a.weight = w;
    a.tLink = vex[u].firstOut;    // 头插到 u 的出边链
    a.hLink = vex[v].firstIn;     // 头插到 v 的入边链
    arc.push_back(a);
    int id = (int)arc.size() - 1;
    vex[u].firstOut = id;
    vex[v].firstIn  = id;
}

void printOut(int u) {            // 枚举 u 的所有出弧（顺 tLink）
    cout << "v" << u << " 的出弧: ";
    int c = 0;
    for (int i = vex[u].firstOut; i != -1; i = arc[i].tLink) {
        cout << arc[i].tailVex << "->" << arc[i].headVex << " ";
        ++c;
    }
    cout << " 出度=" << c << "\n";
}

void printIn(int u) {             // 枚举 u 的所有入弧（顺 hLink）
    cout << "v" << u << " 的入弧: ";
    int c = 0;
    for (int i = vex[u].firstIn; i != -1; i = arc[i].hLink) {
        cout << arc[i].tailVex << "->" << arc[i].headVex << " ";
        ++c;
    }
    cout << " 入度=" << c << "\n";
}

int main() {
    initOL(3);
    addArc(0, 1);
    addArc(0, 2);
    addArc(1, 2);

    for (int u = 0; u < 3; ++u) { printOut(u); printIn(u); }
    /* 输出：
       v0 的出弧: 0->2 0->1  出度=2
       v0 的入弧:             入度=0
       v1 的出弧: 1->2        出度=1
       v1 的入弧: 0->1        入度=1
       v2 的出弧:             出度=0
       v2 的入弧: 1->2 0->2   入度=2   */
    cout << "弧结点总数 = " << arc.size() << " = e = 3\n";
    return 0;
}

8.4.6 邻接多重表：无向图里每条边只存一个结点

无向图的邻接表有个「冗余」：一条边要存两个结点。如果要做的操作是 「删除一条边」「给边打标记（比如判断某条边是否已经走过）」，就得同时找到两份并分别删除，很麻烦。 邻接多重表（adjacency multilist）正是为解决这个问题而生： 每条边只存一个结点，两个端点各自通过自己的指针链指向它。

边结点

五个域：mark（标记位，可用于「这条边是否访问过」）、ivex、ilink（顶点 ivex 的下一条关联边）、jvex、jlink（顶点 jvex 的下一条关联边）。

顶点结点

data + firstEdge（指向第一条依附于该顶点的边结点）。

于是 3 个顶点的完全图只需要 3 个边结点（邻接表要 6 个），空间从 O(n + 2e) 降到 O(n + e)，而且删除一条边只需摘掉一个结点。 代价是每个结点多两个指针域，结构更绕，所以它主要用于需要频繁对边做标记 / 删除的无向图算法 （例如欧拉路径的求解中给边打「已走过」标记）。

#include <iostream>
#include <vector>
using namespace std;

/* ============================================================
   邻接多重表 —— 无向图专用，每条边只存一个结点
   边结点：mark + ivex + ilink + jvex + jlink
   ============================================================ */
struct EdgeBox {
    bool mark;                   // 标记：这条边是否被访问过（欧拉路径等算法用）
    int ivex, ilink;             // 端点 ivex 及其下一条关联边
    int jvex, jlink;             // 端点 jvex 及其下一条关联边
    int weight;
};

struct VexNode2 { int data; int firstEdge; };

vector<VexNode2> mv;
vector<EdgeBox>  me;

void initML(int n) {
    mv.assign(n, VexNode2());
    for (int i = 0; i < n; ++i) { mv[i].data = i; mv[i].firstEdge = -1; }
    me.clear();
}

/* 插入无向边 (u,v)：只生成一个边结点，分别挂到两个端点的链上 */
void addEdgeML(int u, int v, int w = 1) {
    EdgeBox e;
    e.mark = false;
    e.ivex = u; e.jvex = v; e.weight = w;
    e.ilink = mv[u].firstEdge;   // 挂到 u 的链
    e.jlink = mv[v].firstEdge;   // 挂到 v 的链
    me.push_back(e);
    int id = (int)me.size() - 1;
    mv[u].firstEdge = id;
    mv[v].firstEdge = id;
}

/* 枚举顶点 u 的所有邻接点：注意先判断自己站在 ivex 还是 jvex 这一侧 */
void neighbors(int u) {
    cout << "v" << u << " 的邻接点: ";
    int deg = 0;
    for (int i = mv[u].firstEdge; i != -1; ) {
        EdgeBox& e = me[i];
        if (e.ivex == u) { cout << e.jvex << " "; i = e.ilink; }
        else             { cout << e.ivex << " "; i = e.jlink; }
        ++deg;
    }
    cout << " 度=" << deg << "\n";
}

int main() {
    initML(3);
    addEdgeML(0, 1);
    addEdgeML(0, 2);
    addEdgeML(1, 2);

    for (int u = 0; u < 3; ++u) neighbors(u);
    cout << "边结点总数 = " << me.size() << " = e = 3（邻接表需要 2e = 6 个）\n";

    /* 给边打标记只需改一个结点：把边 (0,2) 标记为已访问 */
    for (size_t i = 0; i < me.size(); ++i)
        if ((me[i].ivex == 0 && me[i].jvex == 2) || (me[i].ivex == 2 && me[i].jvex == 0))
            me[i].mark = true;
    cout << "边 (0,2) 已标记\n";
    return 0;
}

8.5 邻接矩阵 vs 邻接表：九个维度的大对比

前面两节把两种存储结构分别讲完了，现在把它们放到同一张表里逐项对比。 这张表是本讲最可能在选择题里出现的内容，建议先自己填一遍，再对照答案。 设图有 n 个顶点、e 条边，deg(u) 表示顶点 u 的度（有向图指出度）。

8.6 图的遍历（一）：深度优先搜索 DFS

8.6.1 一句话本质：一条路走到黑，撞墙再回头

深度优先搜索（Depth-First Search, DFS）的思想可以用走迷宫来类比： 每到一个岔路口，先随便选一条没走过的路往前走；如果走不通（或者走到已经去过的地方）， 就退回上一个岔路口，换一条路继续试，直到所有路都试完。

形式化地描述：从起点 s 出发，

1. 访问 s，并把它标记为「已访问」；
2. 依次检查 s 的每个邻接点 v：若 v 未被访问，就以 v 为新起点递归地做同样的事；
3. 当 s 的所有邻接点都检查完，就回溯（退回上一层）。

这里有三个细节必须注意，它们决定了你的代码对不对：

• 访问标记要在「进入时就打」，而不是「离开时」或者「发现时忘了打」。 否则在无向图里两点会互相递归，直接栈溢出。
• 无向图必须记录父结点（或者用边编号），否则从 u 走到 v 后，v 又会看到「u 是邻接点且已访问」， 把来路误判成回路，见 8.6.6 的判环部分。
• 遍历顺序依赖于邻接点的枚举顺序。同一张图，邻接点按升序枚举和按降序枚举， 得到的是两个不同的（但都合法的）DFS 序列。考试若无特别说明，按编号从小到大来。

DFS 与第 07 讲学的二叉树先序遍历本质上是同一个东西：都是「先访问自己，再递归子树」。 只不过二叉树的「子结点」只有两个且有左右之分，而图的邻接点有任意多个、还没有顺序。 所以可以说：DFS 是「先序遍历」在图上的推广，图是「去掉左右与层次约束」的树。

8.6.2 手推完整过程：访问序列与每次回溯

我们仍然用本讲的示例图 G（n = 8、e = 9），从顶点 0 出发，约定邻接点按编号从小到大访问。 请拿一张纸跟着下面的表格一步步走，重点看「什么时候进、什么时候退」。

结论：DFS 访问序列 = 0 → 1 → 2 → 3 → 4 → 5 → 6 → 7； 共走了 7 条树边（0-1、1-2、2-3、3-4、4-5、5-6、5-7），恰好构成一棵生成树； 另外发现 2 条回边（0-6、1-7），它们说明图中存在环。 数一数：树边 + 回边 = 7 + 2 = 9 = e，一条不多一条不少——DFS 会把每条边恰好检查一遍（无向图是两遍，每个方向一遍）。

下面的动画把整个过程逐帧展开，包括递归栈的变化、访问序列的生长、以及每一条边被判定为树边还是回边：

8.6.3 DFS 的递归实现（邻接表版）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/* ============================================================
   邻接表 + 递归 DFS：同时完成三件事
     1) 记录访问序列
     2) 记录每个顶点的父结点（parent）
     3) 对边分类：树边 / 回边，从而判断有没有环
   ============================================================ */
const int MAXN = 100005;
vector<int> g[MAXN];
vector<bool> vis;
vector<int>  ord, parentNode;
vector<pair<int,int> > treeEdges, backEdges;

void dfs(int u, int p) {
    vis[u] = true;
    parentNode[u] = p;
    ord.push_back(u);                       // 进入时记录 → 这就是 DFS 序列
    for (size_t i = 0; i < g[u].size(); ++i) {
        int v = g[u][i];
        if (!vis[v]) {
            treeEdges.push_back(make_pair(u, v));
            dfs(v, u);                      // 递归深入
        } else if (v != p) {
            /* 已访问且不是父结点 → 回边（无向图中回边等价于“有环”）
               注意：无向图每条边存了两次，v == p 的那一次必须排除 */
            int a = min(u, v), b = max(u, v);
            bool dup = false;
            for (size_t k = 0; k < backEdges.size(); ++k)
                if (backEdges[k].first == a && backEdges[k].second == b) dup = true;
            if (!dup) backEdges.push_back(make_pair(a, b));
        }
    }
    /* 这里可以做“离开 u”的收尾工作，例如拓扑排序的逆序输出 */
}

int main() {
    int n = 8;
    int E[9][2] = {{0,1},{0,6},{1,2},{1,7},{2,3},{3,4},{4,5},{5,6},{5,7}};
    for (int i = 0; i < 9; ++i) { g[E[i][0]].push_back(E[i][1]); g[E[i][1]].push_back(E[i][0]); }
    for (int u = 0; u < n; ++u) sort(g[u].begin(), g[u].end());  // 保证升序枚举

    vis.assign(n, false);
    parentNode.assign(n, -1);
    dfs(0, -1);

    cout << "DFS 序列: ";
    for (int x : ord) cout << x << " ";              // 0 1 2 3 4 5 6 7
    cout << "\n树边 " << treeEdges.size() << " 条: ";
    for (size_t i = 0; i < treeEdges.size(); ++i)
        cout << "(" << treeEdges[i].first << "," << treeEdges[i].second << ") ";
    cout << "\n回边 " << backEdges.size() << " 条: ";
    for (size_t i = 0; i < backEdges.size(); ++i)
        cout << "(" << backEdges[i].first << "," << backEdges[i].second << ") ";   // (0,6) (1,7)
    cout << "\n";
    cout << "图中有环? " << (backEdges.empty() ? "没有" : "有") << "\n";
    return 0;
}

8.6.4 DFS 的非递归实现（用栈模拟递归）

递归的本质是「系统帮你维护了一个栈」，所以改成非递归就是「自己维护一个栈」。 但这里有一个非常经典的坑：如果只是简单地把邻接点全部压栈，得到的访问序列 和递归版不一样。原因是「入栈时就打访问标记」会让某个顶点被过早地标记， 从而在栈里排到后面才弹出来，顺序就乱了。

下面给出两个版本，请务必对比它们输出的差别：

#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 100005;
vector<int> g[MAXN];
int n = 8;

/* ---------- 版本 A：常见但“不等价”的写法 ----------
   入栈时打标记，邻接点全部压栈（为了和递归顺序接近，要逆序压）。
   它能正确地遍历所有顶点，但访问序列与递归版不同，也不能直接用来求“回溯顺序”。 */
vector<int> dfsStackSimple(int s) {
    vector<int> order;
    vector<bool> vis(n, false);
    stack<int> st;
    st.push(s); vis[s] = true;             // 入栈即标记，避免同一个点被压多次
    while (!st.empty()) {
        int u = st.top(); st.pop();
        order.push_back(u);
        for (int i = (int)g[u].size() - 1; i >= 0; --i) {   // 逆序压栈
            int v = g[u][i];
            if (!vis[v]) { vis[v] = true; st.push(v); }
        }
    }
    return order;
}

/* ---------- 版本 B：与递归严格等价的写法 ----------
   栈里保存“栈帧”：(当前顶点 u, 下一次要从它的第几个邻接点开始看)。
   只有当 u 的邻接表全部扫完时，才真正弹栈——这正是递归里“函数返回”的时刻。 */
vector<int> dfsStackExact(int s) {
    vector<int> order;
    vector<bool> vis(n, false);
    vector<pair<int,int> > st;             // (u, next index)
    vis[s] = true; order.push_back(s);
    st.push_back(make_pair(s, 0));
    while (!st.empty()) {
        int u = st.back().first;
        int& i = st.back().second;         // 引用：直接改栈顶那一帧
        if (i >= (int)g[u].size()) { st.pop_back(); continue; }   // 扫完 → 回溯
        int v = g[u][i++];                 // 取下一个邻接点，并把游标前移
        if (!vis[v]) {
            vis[v] = true;
            order.push_back(v);            // 进入 v 的那一刻就记录
            st.push_back(make_pair(v, 0));
        }
    }
    return order;
}

int main() {
    int E[9][2] = {{0,1},{0,6},{1,2},{1,7},{2,3},{3,4},{4,5},{5,6},{5,7}};
    for (int i = 0; i < 9; ++i) { g[E[i][0]].push_back(E[i][1]); g[E[i][1]].push_back(E[i][0]); }
    for (int u = 0; u < n; ++u) sort(g[u].begin(), g[u].end());

    cout << "递归版     : 0 1 2 3 4 5 6 7\n";
    cout << "版本A(简单): "; for (int x : dfsStackSimple(0)) cout << x << " "; cout << "\n";
    /* 输出 0 1 2 3 4 5 7 6 —— 顶点 6 被提前标记，弹栈顺序与递归不同 */
    cout << "版本B(等价): "; for (int x : dfsStackExact(0)) cout << x << " "; cout << "\n";
    /* 输出 0 1 2 3 4 5 6 7 —— 与递归版完全一致 */
    return 0;
}

8.6.5 DFS 的复杂度分析

解释一下「每条边恰好检查两次」：在无向图的 DFS 里，对边 (u,v)， 当我们在 u 的邻接表中看到 v 时检查一次，在 v 的邻接表中看到 u 时又检查一次 （第二次会被 v == p 或 vis[v] 挡掉）。所以总的检查次数是 2e， 加上 n 次「进入顶点」的开销，就是 O(n + e)。

如果图是非连通的，需要在外层对每个顶点做一次「未访问就 DFS」的循环， 总复杂度依然是 O(n + e)——因为每个顶点最多被当作起点一次，每次 DFS 只碰自己分量内的边。

8.6.6 DFS 的六大应用

① 求连通分量个数（最直接的应用）

外层循环对每个顶点检查一次：若未访问，说明发现了新分量，计数器 +1，并从这个顶点 DFS 把整个分量吃掉。 详见 8.8.1 的完整代码。

② 判断无向图是否有环：看「是否访问过父结点」

无向图中，DFS 遇到一条「指向已访问顶点、且该顶点不是自己的父结点」的边，就说明存在回路。 为什么必须排除父结点？因为无向图的每条边在邻接表里出现两次， 从 u 走到 v 之后，v 一定会看到 u，如果不排除就会把这条来路误判成环，导致「任何一条边都被判成环」。

还有一个更简单的判据：n 个顶点的无向图，若 DFS 产生过回边，则 e ≥ n； 反之，若 e ≥ n 且图连通，则必有环（因为生成树只有 n−1 条边，多出来的边必然成环）。

③ 判断有向图是否有环：三色标记法

有向图的判环不能用「父结点」那一套（因为有向边没有对称性），标准做法是三色标记： 白色 = 未访问，灰色 = 正在访问（在递归栈上），黑色 = 已完成。 如果在 DFS 中遇到一条指向灰色顶点的边，就说明找到了一个有向环。

#include <iostream>
#include <vector>
using namespace std;

/* ============================================================
   两种判环：
     无向图 —— DFS + “排除父结点”
     有向图 —— DFS + 三色标记（白 0 / 灰 1 / 黑 2）
   ============================================================ */
const int MAXN = 100005;
vector<int> ug[MAXN], dg[MAXN];      // 无向图 / 有向图的邻接表
int color[MAXN];                     // 0 未访问 1 在栈上 2 已完成

/* ---------- 无向图判环 ---------- */
bool undirectedHasCycle(int u, int parent, vector<bool>& vis) {
    vis[u] = true;
    for (size_t i = 0; i < ug[u].size(); ++i) {
        int v = ug[u][i];
        if (!vis[v]) {
            if (undirectedHasCycle(v, u, vis)) return true;
        } else if (v != parent) {
            return true;                 // 撞到已访问且不是父结点 → 有环
        }
    }
    return false;
}

/* ---------- 有向图判环（三色标记） ---------- */
bool directedHasCycle(int u) {
    color[u] = 1;                        // 灰：进入
    for (size_t i = 0; i < dg[u].size(); ++i) {
        int v = dg[u][i];
        if (color[v] == 1) return true;              // 指向栈上的祖先 → 有向环
        if (color[v] == 0 && directedHasCycle(v)) return true;
    }
    color[u] = 2;                        // 黑：离开，后续再遇到它不算环
    return false;
}

int main() {
    /* 无向图：示例图 G 有环（0-1-2-3-4-5-6-0） */
    int E[9][2] = {{0,1},{0,6},{1,2},{1,7},{2,3},{3,4},{4,5},{5,6},{5,7}};
    for (int i = 0; i < 9; ++i) { ug[E[i][0]].push_back(E[i][1]); ug[E[i][1]].push_back(E[i][0]); }
    vector<bool> vis(8, false);
    cout << "无向图有环? " << (undirectedHasCycle(0, -1, vis) ? "有" : "没有") << "\n";  // 有

    /* 无向图：一棵树（去掉两条边）应当无环 */
    for (int i = 0; i < 8; ++i) ug[i].clear();
    int T[7][2] = {{0,1},{1,2},{2,3},{3,4},{4,5},{5,6},{5,7}};
    for (int i = 0; i < 7; ++i) { ug[T[i][0]].push_back(T[i][1]); ug[T[i][1]].push_back(T[i][0]); }
    vector<bool> vis2(8, false);
    cout << "这棵树有环? " << (undirectedHasCycle(0, -1, vis2) ? "有" : "没有") << "\n";  // 没有

    /* 有向图：0→1→2→0 有环；0→1→2 无环 */
    dg[0].push_back(1); dg[1].push_back(2); dg[2].push_back(0);
    cout << "有向图 0→1→2→0 有环? " << (directedHasCycle(0) ? "有" : "没有") << "\n";     // 有
    for (int i = 0; i < 3; ++i) { dg[i].clear(); color[i] = 0; }
    dg[0].push_back(1); dg[1].push_back(2);
    cout << "有向图 0→1→2 有环? " << (directedHasCycle(0) ? "有" : "没有") << "\n";       // 没有
    return 0;
}

④ 求割点与桥（Tarjan 的 low 值）

割点（articulation point）是「删掉它之后连通分量个数增加」的顶点； 桥（bridge）是「删掉它之后连通分量个数增加」的边。 DFS 过程中记录两个量：dfn[u]（时间戳，第几个被访问）与 low[u] （u 及其子树能通过回边到达的最小时间戳），就能线性求出全部割点与桥。 判定规则：

• 桥：若 low[v] > dfn[u]（v 是 u 的孩子），则边 (u,v) 是桥—— 因为 v 的子树没有任何回边能绕回 u 或 u 的祖先。
• 割点：非根结点 u 只要有一个孩子 v 满足 low[v] ≥ dfn[u]，u 就是割点； 根结点则需至少两个孩子才是割点。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/* ============================================================
   Tarjan 求割点与桥（无向连通图，顶点编号从 1 开始）
   dfn[u]：u 被访问的时间戳
   low[u]：u 及其子树通过回边能到达的最小 dfn
   ============================================================ */
const int MAXN = 100005;
vector<int> g[MAXN];
int dfn[MAXN], low[MAXN], timer = 0;
bool isCut[MAXN];
vector<pair<int,int> > bridges;
int n, m;

void tarjan(int u, int parent) {
    dfn[u] = low[u] = ++timer;
    int child = 0;
    for (size_t i = 0; i < g[u].size(); ++i) {
        int v = g[u][i];
        if (!dfn[v]) {                       // v 还没访问 → 树边
            ++child;
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
            if (low[v] > dfn[u]) bridges.push_back(make_pair(min(u,v), max(u,v)));   // 桥
            if (parent != 0 && low[v] >= dfn[u]) isCut[u] = true;                     // 非根割点
        } else if (v != parent) {            // 回边（重边场景需改用边编号判断）
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (parent == 0 && child >= 2) isCut[u] = true;   // 根结点：两个孩子以上才是割点
}

int main() {
    n = 6;
    int E[6][2] = {{1,2},{2,3},{3,1},{3,4},{4,5},{5,6}};
    m = 6;
    for (int i = 0; i < m; ++i) { g[E[i][0]].push_back(E[i][1]); g[E[i][1]].push_back(E[i][0]); }

    tarjan(1, 0);

    cout << "割点: ";
    for (int i = 1; i <= n; ++i) if (isCut[i]) cout << i << " ";     // 割点: 3 4 5
    cout << "\n桥: ";
    for (size_t i = 0; i < bridges.size(); ++i)
        cout << "(" << bridges[i].first << "," << bridges[i].second << ") ";
    cout << "\n";
    /* 实际输出：桥: (5,6) (4,5) (3,4) —— 顺序是 DFS 发现的先后，
       但桥的集合就是 {(3,4), (4,5), (5,6)}：这条路 3-4-5-6 上每条边都是桥。 */
    return 0;
}

⑤ 走迷宫与「一笔画」的路径搜索

迷宫问题把每个格子看成一个顶点，相邻可走的格子之间连边，于是「能不能走出去」就变成了 「起点与终点是否连通」，「最短步数」就变成了「无权图最短路」。 DFS 能找到一条可行路径（但不保证最短），BFS 才能保证最短——这是搜索类题目最基本的分工。

⑥ 与二叉树先序遍历的关系

DFS 的前序写法（进入即访问）与二叉树先序遍历完全一致：先访问自己，再依次递归每个孩子。 后序写法（离开时才处理）对应二叉树后序遍历，它在拓扑排序、强连通分量（Kosaraju）、 树形 DP 的答案回传里都是关键；中序则在一般图上没有对应物，因为一般图没有「左右子树」的概念。

8.7 图的遍历（二）：广度优先搜索 BFS

8.7.1 一句话本质：一圈一圈向外扩散

广度优先搜索（Breadth-First Search, BFS）像往水里丢一颗石子： 波纹从源点开始，一层一层向外扩散。算法描述只有三步：

1. 把源点 s 入队，并标记 visited[s] = true；
2. 每次从队头取出一个顶点 u，把它的所有未访问邻接点依次入队并打标记；
3. 重复第 2 步直到队列为空。

与 DFS 最大的区别是：DFS 用栈（后进先出，所以一路深入），BFS 用队列（先进先出，所以逐层扩散）。 数据结构一换，遍历的性质就全变了——这正是第 03、04 讲学栈与队列的用处。

BFS 有一个 DFS 没有的重要性质：在无权图中，BFS 第一次到达某顶点时经过的边数，就是它到源点的最短距离。 原因很直观：BFS 是按「距离源点 0 步、1 步、2 步……」的顺序访问顶点的， 第一次访问 v 时，所有可能更短的路径早就应该把它访问掉了。这个性质是「无权图单源最短路」的全部理论基础。

8.7.2 手推过程：队列变化与分层

仍然用示例图 G，从顶点 0 出发（邻接点按升序入队）：

BFS 访问序列：0 → 1 → 6 → 2 → 7 → 5 → 3 → 4，它按层严格递增：

注意第 7 步：顶点 4 在顶点 3 出队之前就已经被 5 放进了队列， 所以 3 看到 4 时不能重复入队——这正是「dist[v] == -1 判断」的作用。 如果忘记判断，4 会被入队两次，队列长度失控。

下面是 BFS 的逐帧动画，请对照队列表格观察队列的进出与 dist[] 的写入时刻：

8.7.3 BFS 的复杂度

与 DFS 完全一致，因为「每个顶点入队出队各一次、每条边检查常数次」这个事实没有变：

注意空间：BFS 的队列规模在最坏情况下可能接近 n（例如星形图，源点一次把所有叶子入队）， 所以空间是 O(n) 而不是 O(1)。这也是 BFS 在超大规模图（如整个互联网的网页图）上不如 DFS 省内存的原因之一。

8.7.4 重头戏：无权图的单源最短路（含路径还原）

「单源最短路（Single Source Shortest Path, SSSP）」是图论里最重要的问题家族。 带权图要用 Dijkstra / Bellman-Ford / SPFA（下一讲的内容）， 但如果是无权图（或者每条边权都相同），用 BFS 就够了，而且更快、更简单：

dist[v] 记录源点到 v 的最短边数，pre[v] 记录「v 是从谁走过来的」（前驱）。 有了 pre[]，从终点一路 v = pre[v] 倒推到源点，把经过的顶点倒序输出，就得到了完整路径。 这两个数组是所有路径类问题的标配，务必熟练掌握。

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

/* ============================================================
   无权图单源最短路：BFS
   返回 dist[]；同时用 pre[] 还原出 s 到 t 的具体路径
   时间 O(n + e)，空间 O(n)
   ============================================================ */
const int MAXN = 100005;
const int INF  = 0x3f3f3f3f;
vector<int> g[MAXN];
int n = 8;

vector<int> dist, pre;

void bfsShortest(int s) {
    dist.assign(n, INF);          // INF 表示“还没到达”
    pre.assign(n, -1);
    queue<int> q;
    dist[s] = 0;
    q.push(s);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (size_t i = 0; i < g[u].size(); ++i) {
            int v = g[u][i];
            if (dist[v] == INF) {          // 第一次到达 → 这就是最短距离
                dist[v] = dist[u] + 1;
                pre[v]  = u;               // 记录前驱，供路径还原
                q.push(v);
            }
        }
    }
}

/* 还原 s → t 的路径（正序）；若不可达返回空数组 */
vector<int> getPath(int s, int t) {
    vector<int> path;
    if (dist[t] == INF) return path;       // 不可达
    for (int v = t; v != -1; v = pre[v]) path.push_back(v);
    reverse(path.begin(), path.end());
    if (path[0] != s) return vector<int>();   // 安全校验
    return path;
}

int main() {
    int E[9][2] = {{0,1},{0,6},{1,2},{1,7},{2,3},{3,4},{4,5},{5,6},{5,7}};
    for (int i = 0; i < 9; ++i) { g[E[i][0]].push_back(E[i][1]); g[E[i][1]].push_back(E[i][0]); }
    for (int u = 0; u < n; ++u) sort(g[u].begin(), g[u].end());

    bfsShortest(0);

    cout << "从 0 出发的 dist[]: ";
    for (int i = 0; i < n; ++i) cout << dist[i] << " ";       // 0 1 2 3 3 2 1 2
    cout << "\n";

    vector<int> p = getPath(0, 4);
    cout << "0 → 4 的最短路径: ";
    for (size_t i = 0; i < p.size(); ++i) cout << p[i] << (i + 1 < p.size() ? " -> " : "");
    cout << "　长度 " << dist[4] << "\n";                     // 0 -> 6 -> 5 -> 4　长度 3

    p = getPath(0, 3);
    cout << "0 → 3 的最短路径: ";
    for (size_t i = 0; i < p.size(); ++i) cout << p[i] << (i + 1 < p.size() ? " -> " : "");
    cout << "　长度 " << dist[3] << "\n";                     // 0 -> 1 -> 2 -> 3　长度 3
    return 0;
}

注意上面 0 → 3 与 0 → 4 的两条路径长度都是 3，但走法完全不同—— BFS 求的是长度，最短路径本身可能有多条，BFS 只会还原出「按照邻接表枚举顺序」找到的那一条。 如果题目要求输出字典序最小的最短路，或者要求统计最短路径条数， 就要在 dist[v] == dist[u] + 1 时另行处理（累加计数 / 比较前驱编号）。

下面的动画展示 dist[] 的逐层写入与最后的路径还原过程：

8.7.5 BFS 的另外两个经典应用

① 二分图判定（染色法）

二分图（bipartite graph）是可以把顶点分成两个集合 X、Y，使得每条边的两个端点 分别落在不同集合里的图。等价说法：可以用两种颜色给顶点染色，使每条边两端颜色不同。

判定方法非常自然：从任意未染色顶点出发，染成颜色 0，然后 BFS/DFS，把它的邻居染成颜色 1， 邻居的邻居染成颜色 0……如果在过程中遇到一条边，两个端点颜色相同，就说明不是二分图。 本质上，这等价于判断「图中是否存在奇环（长度为奇数的环）」—— 一张图是二分图 ⟺ 它不含奇环。示例图 G 中含有一个长度为 7 的环 0-1-2-3-4-5-6-0，是奇环，所以 G 不是二分图（你可以试着染一下，一定会在某个地方冲突）。

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

/* ============================================================
   二分图判定：BFS 染色（0 / 1 两种颜色，-1 表示未染色）
   注意外层循环：非连通图要对每个连通分量分别染色
   ============================================================ */
const int MAXN = 100005;
vector<int> g[MAXN];
int color[MAXN];                 // -1 未染色，0 / 1 两种颜色
int n = 8;

bool isBipartite() {
    for (int i = 0; i < n; ++i) color[i] = -1;
    for (int s = 0; s < n; ++s) {
        if (color[s] != -1) continue;
        color[s] = 0;
        queue<int> q;
        q.push(s);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (size_t i = 0; i < g[u].size(); ++i) {
                int v = g[u][i];
                if (color[v] == -1) {           // 未染色 → 染成相反色
                    color[v] = color[u] ^ 1;
                    q.push(v);
                } else if (color[v] == color[u]) {
                    return false;               // 相邻同色 → 不是二分图
                }
            }
        }
    }
    return true;
}

int main() {
    /* 图 1：一个偶环（0-1-2-3-0）→ 二分图 */
    int E1[4][2] = {{0,1},{1,2},{2,3},{3,0}};
    for (int i = 0; i < 4; ++i) { g[E1[i][0]].push_back(E1[i][1]); g[E1[i][1]].push_back(E1[i][0]); }
    cout << "偶环图是二分图? " << (isBipartite() ? "是" : "不是") << "\n";    // 是

    /* 图 2：加一条弦 0-2，出现三角形（奇环）→ 不是二分图 */
    g[0].push_back(2); g[2].push_back(0);
    cout << "带三角形的图是二分图? " << (isBipartite() ? "是" : "不是") << "\n";  // 不是

    /* 图 3：本讲示例图 G（含 7 元奇环）→ 不是二分图 */
    for (int i = 0; i < n; ++i) g[i].clear();
    int E3[9][2] = {{0,1},{0,6},{1,2},{1,7},{2,3},{3,4},{4,5},{5,6},{5,7}};
    for (int i = 0; i < 9; ++i) { g[E3[i][0]].push_back(E3[i][1]); g[E3[i][1]].push_back(E3[i][0]); }
    cout << "示例图 G 是二分图? " << (isBipartite() ? "是" : "不是") << "\n";   // 不是
    return 0;
}

② 层序类比：从二叉树层序遍历到图的 BFS

第 07 讲二叉树的层序遍历就是 BFS 的特例：用一个队列，先放根结点， 每次取出一个结点并把它的左右孩子入队，取出的顺序就是「一层一层」的。 图的 BFS 只是把「左右孩子」换成了「邻接表里的所有邻接点」， 把「树的唯一路径」换成了「需要 visited 去重的任意图」。

既然 BFS 天然分层，那么只要在出队时记录「当前层有几个结点」（q.size()）， 就能一次处理一整层。这个技巧在「求二叉树最大宽度」「求图中距离为 k 的结点个数」 「多源 BFS（把所有源点同时入队）」里反复出现：

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

/* ============================================================
   BFS 的三种常见写法
     1) 基础版：求访问序列
     2) 分层版：一次处理一整层（可统计层数、层宽）
     3) 多源版：多个起点同时入队（例如“火势蔓延”“最近的出口”）
   ============================================================ */
const int MAXN = 100005;
vector<int> g[MAXN];
int n = 8;

/* ---------- 1) 基础版 ---------- */
vector<int> bfs(int s) {
    vector<int> order;
    vector<bool> vis(n, false);
    queue<int> q;
    vis[s] = true; q.push(s);              // 入队即打标记
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);
        for (size_t i = 0; i < g[u].size(); ++i) {
            int v = g[u][i];
            if (!vis[v]) { vis[v] = true; q.push(v); }
        }
    }
    return order;
}

/* ---------- 2) 分层版 ---------- */
void bfsByLevel(int s) {
    vector<int> dist(n, -1);
    queue<int> q;
    dist[s] = 0; q.push(s);
    int level = 0;
    while (!q.empty()) {
        int sz = q.size();                 // 当前层的结点个数
        cout << "第 " << level << " 层（" << sz << " 个）: ";
        for (int k = 0; k < sz; ++k) {     // 只处理这一层
            int u = q.front(); q.pop();
            cout << u << " ";
            for (size_t i = 0; i < g[u].size(); ++i) {
                int v = g[u][i];
                if (dist[v] == -1) { dist[v] = dist[u] + 1; q.push(v); }
            }
        }
        cout << "\n";
        ++level;
    }
}

/* ---------- 3) 多源版 ---------- */
vector<int> bfsMultiSource(const vector<int>& srcs) {
    vector<int> dist(n, -1);
    queue<int> q;
    for (size_t i = 0; i < srcs.size(); ++i) { dist[srcs[i]] = 0; q.push(srcs[i]); }  // 源点同时入队
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (size_t i = 0; i < g[u].size(); ++i) {
            int v = g[u][i];
            if (dist[v] == -1) { dist[v] = dist[u] + 1; q.push(v); }
        }
    }
    return dist;
}

int main() {
    int E[9][2] = {{0,1},{0,6},{1,2},{1,7},{2,3},{3,4},{4,5},{5,6},{5,7}};
    for (int i = 0; i < 9; ++i) { g[E[i][0]].push_back(E[i][1]); g[E[i][1]].push_back(E[i][0]); }
    for (int u = 0; u < n; ++u) sort(g[u].begin(), g[u].end());

    cout << "BFS 序列: ";
    vector<int> o = bfs(0);
    for (size_t i = 0; i < o.size(); ++i) cout << o[i] << " ";        // 0 1 6 2 7 5 3 4
    cout << "\n";
    bfsByLevel(0);
    /* 第 0 层（1 个）: 0
       第 1 层（2 个）: 1 6
       第 2 层（3 个）: 2 7 5
       第 3 层（2 个）: 3 4 */

    vector<int> srcs; srcs.push_back(0); srcs.push_back(3);
    vector<int> d = bfsMultiSource(srcs);
    cout << "多源 dist（源点 0 与 3）: ";
    for (int i = 0; i < n; ++i) cout << d[i] << " ";
    cout << "\n";
    return 0;
}

8.8 连通分量与生成树

8.8.1 用 DFS / BFS 求连通分量个数

这是遍历最直接的应用：外层循环扫一遍所有顶点，遇到没访问过的就启动一次遍历， 并把计数器 +1。每一次遍历会把「一个完整的连通分量」全部标记为已访问， 所以计数器的值就是连通分量的个数。时间复杂度 O(n + e)，空间 O(n)。

为了演示多分量，我们在示例图 G 的基础上追加两个顶点： 顶点 8 与 顶点 9 之间连一条边，顶点 10 谁都不连（孤立点）。 记这张图为 G′：n = 11、e = 10，它的连通分量有 3 个： {0,1,2,3,4,5,6,7}、{8,9}、{10}。

下面这个动画逐帧展示「从一个未访问顶点出发，把这个分量整个吃掉并染色」的过程：

#include <iostream>
#include <vector>
using namespace std;

/* ============================================================
   求无向图的连通分量个数（以及每个顶点属于哪个分量）
   时间 O(n + e)，空间 O(n)
   ============================================================ */
const int MAXN = 100005;
vector<int> g[MAXN];
int n, m;
vector<bool> vis;
vector<int>  comp;              // comp[v] = v 所属分量编号（从 0 开始）

void dfs(int u, int cid) {
    vis[u] = true;
    comp[u] = cid;
    for (size_t i = 0; i < g[u].size(); ++i)
        if (!vis[g[u][i]]) dfs(g[u][i], cid);
}

/* 若只要个数，把 comp 相关代码删掉即可；这里保留是为了能输出分量成员 */
int countComponents() {
    vis.assign(n, false);
    comp.assign(n, -1);
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
        if (!vis[i]) {                 // 发现新分量
            dfs(i, cnt);               // 一次 DFS 吃掉整个分量
            ++cnt;
        }
    }
    return cnt;
}

int main() {
    n = 11;                            // G′：8 个顶点的示例图 + 8-9 一条边 + 孤立点 10
    int E[10][2] = {{0,1},{0,6},{1,2},{1,7},{2,3},{3,4},{4,5},{5,6},{5,7},{8,9}};
    for (int i = 0; i < 10; ++i) { g[E[i][0]].push_back(E[i][1]); g[E[i][1]].push_back(E[i][0]); }

    int k = countComponents();
    cout << "连通分量个数 = " << k << "\n";        // 3
    for (int c = 0; c < k; ++c) {
        cout << "分量 " << c + 1 << ": ";
        int sz = 0;
        for (int v = 0; v < n; ++v) if (comp[v] == c) { cout << v << " "; ++sz; }
        cout << "（" << sz << " 个顶点）\n";
    }
    /* 分量 1: 0 1 2 3 4 5 6 7 （8 个顶点）
       分量 2: 8 9 （2 个顶点）
       分量 3: 10 （1 个顶点）  */
    return 0;
}

8.8.2 生成树：定义与「n−1 条边」的证明

生成树（spanning tree）：连通无向图 G 的一个生成子图，它本身是一棵树。 换句话说，它包含 G 的全部 n 个顶点、n−1 条边，而且是连通的、无回路的。 若图不连通，则各连通分量各取一棵生成树，合起来叫生成森林。

定理：n 个顶点的连通图，其任意生成树恰有 n−1 条边。证明用「夹逼」的思路最清楚：

1. 连通性给出下界：e ≥ n−1。 对 n 做归纳。n = 1 时平凡成立。设 n−1 个顶点的连通图至少 n−2 条边， 考虑 n 个顶点的连通图 G：若存在度为 1 的顶点 v（悬挂点），删去 v 及其悬挂边后剩下的图仍连通， 由归纳假设它有 ≥ n−2 条边，故 G 有 ≥ n−1 条边； 若不存在度为 1 的顶点，则所有顶点度 ≥ 2，由握手定理 2e = Σd(v) ≥ 2n，即 e ≥ n > n−1，也成立。
2. 无回路给出上界：e ≤ n−1。 从「n 个孤立顶点」（n 个连通块、0 条边）出发，每加一条边，最多把两个连通块合并成一个， 所以连通块数最多减少 1。要从 n 块变成 1 块（连通），至少要加 n−1 条边； 而如果加的边造成了回路，连通块数根本没减少，反而浪费了一条边。 因此一个「连通且无回路」的图，其边数恰好是 n−1（少于 n−1 不可能连通，多于 n−1 必然有回路）。

两条合起来：生成树的边数恰好是 n−1。这个结论还有几个常用推论：

• 生成树是「极小连通子图」：删掉任意一条边就不连通了。
• 生成树是「极大无回路子图」：任意再加一条原图的边就必然成环。
• 加上任意一条非树边，会形成唯一的一个回路（叫基本回路），回路长度 = 该边两端点在树上的距离 + 1。
• 非连通图有 n 个顶点、k 个连通分量时，生成森林有 n−k 条边。

8.8.3 DFS 生成树与 BFS 生成树

遍历一张连通图时，我们只会「沿着某些边」走到新顶点，这些边就是树边， 它们连同全部顶点构成一棵生成树。用 DFS 得到的叫 DFS 生成树， 用 BFS 得到的叫 BFS 生成树，两者的形状差别很大：

本讲示例图的结果：DFS 生成树的树边是 0-1, 1-2, 2-3, 3-4, 4-5, 5-6, 5-7（7 条），非树边是 0-6, 1-7； BFS 生成树的树边是 0-1, 0-6, 1-2, 1-7, 6-5, 2-3, 5-4（7 条）， 非树边是 3-4, 5-7。 两棵树的边集完全不同，但边数都是 7 = n−1，这就是「生成树不唯一」的最直接例证。

8.8.4 生成树不唯一，最小生成树也不唯一（但权值和唯一）

从 8.8.3 的例子里已经看到：同一张图的生成树有很多棵。 如果给边加上权值（这时图叫网），我们就会问： 哪一棵生成树的总权值最小？这就是最小生成树（Minimum Spanning Tree, MST）问题， 求法有 Prim 与 Kruskal 两种经典算法，是下一讲的主角。

这里先埋三个伏笔，下一讲会正式证明：

1. 最小生成树不一定唯一。当图中存在权值相同的边时，可能有多棵不同的最小生成树。
2. 但最小生成树的权值和一定唯一。不管选出哪一棵，总权值都相同——这是 MST 最重要的性质， 也是很多题目「只问权值和」的底气所在。
3. 切性质（cut property）：把顶点任意分成两部分，横跨这两部分的所有边中权值最小的那条， 一定属于某棵最小生成树。Prim 与 Kruskal 都是这条性质的推论。

8.9 图的经典小题速览

这一节把图论里最常见的几个「小问题」集中过一遍。它们本身不难，但每一个都对应着一类 考试题与竞赛模板，而且都会在后面的算法课里反复出现。这里只给结论与一句话思路， 完整的推导留给对应的专题。

8.9.1 判断二分图

结论：一张图是二分图 ⟺ 它不含长度为奇数的环（奇环）。 判定方法就是 BFS/DFS 染色：相邻顶点必须异色，一旦发现相邻同色就失败。 时间复杂度 O(n + e)（邻接表）。

直觉理解：沿着一条边颜色必然翻转，所以绕一个环走一圈回到起点时，颜色翻转的次数 = 环长。 环长为偶数时颜色能回到原样，为奇数时必然冲突。二分图的典型应用是任务分配与 冲突检测（例如「把学生分成两组，每组内部不能有矛盾关系」）。

8.9.2 求无向图的割点与桥

割点是删掉后连通分量变多的顶点，桥是删掉后连通分量变多的边。 一句话思路：DFS 时记 dfn（时间戳）与 low（子树能回到的最小时间戳）， low[v] ≥ dfn[u] 说明 v 的子树「绕不回去」，u 就是割点； low[v] > dfn[u] 则说明这条边是桥。 根结点要单独判断（孩子数 ≥ 2 才是割点）。完整代码见 8.6.6 的 graph_cut_vertex.cpp。

应用场景：网络中的关键路由器（删掉它网络就分裂）、交通网中的咽喉要道、 社交网络中的「桥接人物」。这个算法也是 Tarjan 系列（强连通分量、双连通分量、2-SAT）的入门。

8.9.3 有向图的可达性

「从 u 能不能走到 v」是最基础的有向图问题。如果只问一对点，一次 DFS/BFS 就够（O(n+e)）； 如果要把所有点对的可达性都算出来（叫传递闭包），有三种做法：

传递闭包还有一个漂亮的等价说法：把 reach 矩阵看成布尔矩阵， 它等于 I ∨ A ∨ A² ∨ … ∨ An−1。这也顺便解释了 8.5 节里提到的 「A² 的元素是长度为 2 的路径条数」这一性质。

#include <bitset>
#include <iostream>
#include <vector>
using namespace std;

/* ============================================================
   有向图的可达性（传递闭包）
   这里给出 bitset 版：reach[u] 的第 v 位为 1 表示 u 可达 v
   ============================================================ */
const int MAXN = 2005;
vector<int> g[MAXN];
bitset<MAXN> reach[MAXN];
int n = 5;

/* 从 s 出发 DFS，把所有可达点写进 reach[s] */
void dfsReach(int u, int s) {
    reach[s].set(u);                       // 进入即标记“可达”
    for (int v : g[u])
        if (!reach[s].test(v)) dfsReach(v, s);
}

/* Floyd 版：n ≤ 500 时最省事 */
void floydReach(vector<vector<bool>>& r) {
    for (int k = 0; k < n; ++k)
        for (int i = 0; i < n; ++i)
            if (r[i][k])
                for (int j = 0; j < n; ++j)
                    if (r[k][j]) r[i][j] = true;
}

int main() {
    /* 有向图：0→1, 1→2, 2→3, 0→3, 3→4 */
    g[0].push_back(1); g[1].push_back(2); g[2].push_back(3);
    g[0].push_back(3); g[3].push_back(4);

    for (int s = 0; s < n; ++s) dfsReach(s, s);
    for (int u = 0; u < n; ++u) {
        cout << u << " 可达: ";
        for (int v = 0; v < n; ++v) if (reach[u].test(v)) cout << v << " ";
        cout << "\n";
    }
    /* 0 可达: 0 1 2 3 4
       1 可达: 1 2 3 4
       2 可达: 2 3 4
       3 可达: 3 4
       4 可达: 4      */

    cout << "0 可达 4 ? " << (reach[0].test(4) ? "是" : "否") << "\n";   // 是
    cout << "4 可达 0 ? " << (reach[4].test(0) ? "是" : "否") << "\n";   // 否（单向）
    cout << "整张图强连通? " << ([&]{ for (int i = 0; i < n; ++i) if ((int)reach[i].count() != n) return false; return true; }() ? "是" : "否") << "\n";
    return 0;
}

8.9.4 欧拉路径与欧拉回路（一笔画问题）

欧拉路径（Euler path）：经过图中每条边恰好一次的路径（顶点可以重复经过）。 欧拉回路（Euler circuit）：起点与终点相同的欧拉路径。 这就是小时候玩的「一笔画」——笔不离开纸，每条线只画一次。

判定条件（无向图）要先保证「所有度数大于 0 的顶点在同一个连通块里」，然后数奇度顶点的个数：

有向图的判定稍作修改：把「度数为偶数」换成「每个顶点的入度 = 出度」（欧拉回路）， 或者「恰有一个顶点出度 = 入度+1（起点）、一个顶点入度 = 出度+1（终点），其余入度 = 出度」（欧拉路径）， 再加上「把有向边当成无向边后图连通」。

看看我们的示例图 G：度数为 2,3,2,2,2,3,2,2，奇度顶点恰好是 1 和 5，共 2 个，且图连通， 所以存在欧拉路径，必须从 1 出发、到 5 结束。这条路径是： 1 → 0 → 6 → 5 → 4 → 3 → 2 → 1 → 7 → 5，正好走完 9 条边、每条一次。

#include <iostream>
#include <vector>
using namespace std;

/* ============================================================
   无向图的欧拉路径 / 欧拉回路：判定 + Hierholzer 求路径
   判定：① 所有度 > 0 的顶点连通  ② 奇度顶点个数为 0（回路）或 2（路径）
   Hierholzer：DFS 走到底，回溯时把顶点压栈，最后逆序输出即为欧拉路径
   ============================================================ */
const int MAXN = 1005;
const int MAXM = 10005;
int deg[MAXN];
vector<pair<int,int> > g[MAXN];      // (邻接点, 边编号)
bool usedEdge[MAXM];
bool visV[MAXN];
vector<int> ans;
int n = 8, m = 0;

void addEdge(int u, int v) {
    g[u].push_back(make_pair(v, m));
    g[v].push_back(make_pair(u, m));
    deg[u]++; deg[v]++;
    ++m;
}

void dfsConnect(int u) {                  // 只关心有边的顶点是否连通
    visV[u] = true;
    for (size_t i = 0; i < g[u].size(); ++i)
        if (!visV[g[u][i].first]) dfsConnect(g[u][i].first);
}

void hierholzer(int u) {
    for (size_t i = 0; i < g[u].size(); ++i) {
        int v = g[u][i].first, id = g[u][i].second;
        if (usedEdge[id]) continue;       // 每条边只走一次
        usedEdge[id] = true;
        hierholzer(v);
    }
    ans.push_back(u);                     // 回溯时才记录 → 逆序输出即为路径
}

int main() {
    int E[9][2] = {{0,1},{0,6},{1,2},{1,7},{2,3},{3,4},{4,5},{5,6},{5,7}};
    for (int i = 0; i < 9; ++i) addEdge(E[i][0], E[i][1]);

    /* ① 连通性检查 */
    int startV = -1;
    for (int v = 0; v < n; ++v) if (deg[v] > 0) { startV = v; break; }
    dfsConnect(startV);
    bool connected = true;
    for (int v = 0; v < n; ++v) if (deg[v] > 0 && !visV[v]) connected = false;

    /* ② 数奇度顶点 */
    int odd = 0, first = -1;
    for (int v = 0; v < n; ++v)
        if (deg[v] % 2) { ++odd; if (first < 0) first = v; }

    if (!connected || (odd != 0 && odd != 2)) {
        cout << "不存在欧拉路径\n";
        return 0;
    }
    int s = (odd == 2) ? first : startV;          // 有奇度点就必须从奇度点出发
    cout << (odd == 0 ? "存在欧拉回路，起点 " : "存在欧拉路径，起点 ") << s << "\n";
    hierholzer(s);
    cout << "路径: ";
    for (int i = (int)ans.size() - 1; i >= 0; --i)
        cout << ans[i] << (i ? " -> " : "\n");
    /* 存在欧拉路径，起点 1
       路径: 1 -> 0 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> 7 -> 5  */
    cout << "共经过 " << m << " 条边，每条恰好一次\n";
    return 0;
}

8.10 工程视角：图存储与遍历撑起的系统

前九节我们一直在和一张 8 个顶点、9 条边的小图打交道。可一旦走出教室，图的规模会立刻换一个量级—— 社交网络、网页链接、编译器的模块依赖、GC 眼里的内存，全都是图。这一节换一个视角： 不再问「这张图的 DFS 序列是什么」，而是问「当图大到 10⁸ 个顶点时，那些结构还撑得住吗」。 答案会有点意外：课本上的两种存储结构和两种遍历，几乎都被「换过一次零件」才真正上线。

8.10.1 真实图的规模：从 8 个顶点到 30 亿用户

先看几个真实数字（记数量级即可）：

• 社交网络：Facebook 月活约 30 亿，人均好友 300~400，好友边数在 5000 亿（5×10¹¹）量级。
• 网页链接图：被索引的网页数十亿到上百亿，超链接边数在 万亿（10¹²）量级。
• 编译器依赖图：Linux 内核约 7 万个文件，边数量级 10⁵~10⁶。
• GC 的引用图：顶点就是堆里的对象，一次 Full GC 要遍历几千万到几亿个顶点。

现在做最关键的推算：1 亿个顶点（n = 10⁸）的图，用邻接矩阵要多少空间？ 矩阵有 n² = 1016 个格子。就算每格只占 1 个 bit，也要 1016 bit = 1.25×1015 字节 = 1.25 PB；按 int 存是 40 PB。 而这只是装下它——遍历一遍是 O(n²) = 1016 次操作。

同一个图换成 CSR（下节讲）：行指针 rowPtr 占 (108+1)×4 B ≈ 400 MB， 10⁹ 条边的列下标 colIdx 占 4 GB，合计约 4.4 GB。 差距是 1.25 PB 对 4.4 GB，约 28 万倍。所以工程第一条铁律是： 稀疏图必须用邻接表家族（邻接表 / 链式前向星 / CSR），邻接矩阵的 O(n²) 在真实规模上根本放不下。 8.4 节的邻接表、8.4.4 节的链式前向星，不是「另一种写法」，而是唯一可行的写法。

但矩阵没有死，它在三类场景里仍然稳赢：

1. 稠密图。e 接近 n² 时 O(n+e) 与 O(n²) 已是同一量级， 而矩阵内存连续、没有间接寻址，常数更小。
2. 需要反复 O(1) 判边。邻接表、前向星、CSR 判「u 与 v 相邻吗」都要扫一遍 u 的邻居（最坏 O(n)）， 矩阵一次寻址。
3. 算法本身长在二维数组上。Floyd、传递闭包的位运算、稠密图上的 Prim 都是这样， 它们本身就是 O(n³)，只适用于 n ≤ 500：n = 500 时是 1.25×108 次操作还能忍，n = 10⁴ 就是 10¹²，出局。

一句话：先看 n 和 e 谁大，再看你要「判边」还是要「遍历邻居」。 8.5 节那张九维对比表是考试视角，这里补的是规模视角。

8.10.2 三种存法的空间账：矩阵八成的格子是浪费

把一张 6 个顶点、7 条弧的稀疏图用三种方式各存一遍：

最该记住的是那个比例：1 亿个顶点、10 亿条边时，矩阵的浪费率是 1 − 109/1016 = 99.99999%——每 1000 万个格子才 1 个真数据。

8.10.3 CSR 与链式前向星：一个一次成型，一个支持动态加边

CSR（Compressed Sparse Row，压缩稀疏行）就是邻接表的工业化形态：把所有顶点的邻居链拆开、 按顶点顺序拼成一条大数组，再用行指针数组记住每段起点。rowPtr 有 n+1 个整数， 顶点 u 的邻居是 colIdx[rowPtr[u]] 到 colIdx[rowPtr[u+1]−1] 这一段； colIdx 有 e 个整数，按源点分组、组内连续；values 只有带权图才需要。

和 8.4.4 节的链式前向星相比，相同点很多：都是「一个数组存边 + 一个数组记起点」，都没有指针， 都远比「每个顶点一个 vector」缓存友好，遍历邻居都是 O(deg(u))。差别有三条：

一、邻居连不连续。链式前向星用 nxt 把同一起点的边串成链表，这些边可能散落在 数组任何位置，遍历时是一次次「跳」；CSR 里同一起点的边严格连续，遍历就是顺序扫一段内存。 一条缓存行能装 16 个 int，顺序扫几乎次次命中，跳着走则经常重取缓存行。 这是 CSR 在图计算里胜出的根本原因，也是 Ligra、GraphX 都以 CSR 为默认格式的理由。

二、能不能动态加边。链式前向星是头插法，加一条边三行、O(1)；CSR 是一整块压好的数组， 中间插一个数要把后面全部后移，所以它是「一次成型」的：先把边收集齐、按源点排序、再压实。 常见的折中是双缓冲——写入走邻接表，攒够一批整体重建一次 CSR，读走 CSR。

三、每条边的开销。链式前向星每条边要 2 个 int（to 与 nxt）； CSR 无权图上每条边只要 1 个 int（colIdx），行指针只占 n+1 个。 10⁹ 条边的有向图：链式前向星 8 GB，CSR 是 4 GB—— 同样的图，边数据只有一半。

CSR 只能快查出边；要连入边一起快查（PageRank 既要沿出边送分、又要沿入边收分）， 得再存一份转置 CSC，多花一倍存储换掉每轮一次全图转置。

8.10.4 DFS 的工程落点：依赖图、调用图与垃圾回收

8.6.6 节列了 DFS 的六大应用，那是算法视角的清单。现在把它们放回真实系统里，看各自长在哪里。

① 编译器的依赖图环检测与拓扑排序

把每个源文件、每个编译目标看成顶点，#include 或模块依赖看成边，就得到一张有向图。 图里一旦有环，make 会打印「Circular dependency dropped」，Bazel 直接拒绝构建。检测方法正是 8.6.6 节的有向图三色标记：DFS 中遇到指向「灰色」（还在递归栈上）顶点的边，就找到了环。 判完环，把 DFS 的后序序列逆序输出就是构建顺序，make -j 的并行调度、包管理器的 解析顺序用的是同一个套路。另外注意：拓扑序不唯一，调度器会在这些合法解里挑「关键路径最短」 的那一个来压缩总工时（第 09 讲）。

② 程序分析的调用图可达性

把函数当顶点、调用关系当边，就是调用图。优化器要做的第一件事是「从 main 出发 DFS， 标记所有可达函数」，没被标记的就是死代码，可以从二进制里删掉——链接器的 --gc-sections、Java 的类加载分析都是这个思路，代价 O(n+e)。 大型 C++ 程序的调用图有 10⁶ 量级顶点、10⁷ 量级边，听着便宜；但要做 上下文敏感的精确分析（区分「是谁调用的」），状态数会指数上升——这就是「O(n+e) 的可达性」 与「能落地的可达性」的差距。

③ 网页链接图上的 PageRank 迭代

PageRank 给每个网页打分，更新式是 r(v) = (1−d)/n + d × Σu→v r(u)/outdeg(u)。 把 r 看成向量、把链接看成矩阵 A，这正是一次 稀疏矩阵乘向量： r ← (1−d)/n + d·AT·(r/outdeg)。用 CSR 实现，一轮迭代就是遍历一遍所有边， O(n+e)。搜索引擎要处理几十亿网页、上万亿链接，一轮是 10¹² 次边访问， 还要迭代 20~30 轮才收敛——这就是「必须 CSR + 并行 + 分片」的全部理由。 注意它和 8.8 节的连通分量不同：那边只问「能不能到达」，一次遍历就结束；这边要反复迭代到分数稳定， 属于迭代式图计算。

④ 垃圾回收器里的引用图：递归 DFS 的滑铁卢

堆里每个对象是顶点，对象里的指针是边，「还有没有用」=「从根集合（栈、全局变量、寄存器）出发 能不能到达」，所以 GC 的标记阶段本质上就是一次 DFS/BFS。但这里有一个课本不会提的硬约束： 对象图的形状不受控，深度可以等于对象个数。一个 100 万结点的链表就能让递归 DFS 立刻爆栈， 而 GC 跑在别人的进程里，更不能崩。所以生产级 GC 一律不用递归：

• 显式栈的迭代 DFS：自己申请一块内存当栈、按需增长。Boehm GC 的标记阶段就是这么做的。
• 指针反转（Deutsch-Schorr-Waite，DSW）：连显式栈都不要，遍历时把「父指针」临时写进当前结点 自己的指针域，用对象自身的内存当栈，额外空间 O(1)。代价是遍历期间必须独占这些对象， 且很难和并发标记、移动式回收配合，所以现代 GC 更常用显式栈 + 增量三色标记：白 = 未访问， 灰 = 已发现待扫描，黑 = 扫描完毕，配合写屏障维持「黑对象不能直接指向白对象」这个不变式。 它和 8.6.6 节判环的三色是同一个抽象，但那边是找环，这边是保证并发遍历不漏标。

结论：教科书上的递归 DFS 在工程上不能用。它在小图上正确优美，但只要图的深度上到 10⁵ 就当场崩掉，而真实的图动辄 10⁸ 个顶点。

8.10.5 迭代 DFS：把调用栈搬到堆上

下面这段程序把这件事做实：同一张图，递归版与迭代版各跑一遍。图用 CSR 存，显式栈用 stack<int>（换成 int stk[MAXN] + top 指针完全等价， 一层只花 1 个 int；第 03 讲那种链栈就是它的原理）。

#include <cstdio>
#include <stack>
using namespace std;

/* ============================================================
   工程级 DFS：为什么生产代码用「显式栈」而不是递归
   图用 CSR 存：rowPtr[u]..rowPtr[u+1]-1 是 u 的出边在 colIdx 中的区间。
   ============================================================ */
const int MAXN = 1000005;      /* 顶点数上限 */
const int MAXM = 2000005;      /* 边数上限   */
int rowPtr[MAXN];              /* 行指针：n + 1 个 int */
int colIdx[MAXM];              /* 列下标：e 个 int     */
bool vis[MAXN];                /* 访问标记     */

int n = 0;                     /* 当前顶点数 */

/* ---------- 建图一：0 → 1 → 2 → … → n−1 的一条长链 ---------- */
void buildChain(int nodes) {
    n = nodes;
    rowPtr[0] = 0;
    for (int u = 0; u + 1 < n; ++u) {
        colIdx[rowPtr[u]] = u + 1;        /* u 的唯一出边指向 u+1 */
        rowPtr[u + 1] = rowPtr[u] + 1;
    }
    rowPtr[n] = n - 1;                    /* 末尾顶点没有出边 */
}

/* ---------- 建图二：梳状图：脊 0 → 1 → … → spine−1，每脊点再挂一片叶子 ----------
   两条出边刻意「先压叶子、后压下一脊点」，叶子被留在栈底一路累积，
   显式栈深度会涨到 spine。 */
void buildComb(int spine, int leaves) {
    n = spine + leaves;
    rowPtr[0] = 0;
    for (int i = 0; i < spine; ++i) {
        int deg = 0;
        if (i < leaves) { colIdx[rowPtr[i] + deg] = spine + i; ++deg; }  /* 先压叶子 */
        if (i + 1 < spine) { colIdx[rowPtr[i] + deg] = i + 1; ++deg; }   /* 后压脊点 */
        rowPtr[i + 1] = rowPtr[i] + deg;
    }
    for (int i = spine + 1; i <= n; ++i) rowPtr[i] = rowPtr[spine];      /* 叶子没有出边 */
}

void clearVis() { for (int i = 0; i < n; ++i) vis[i] = false; }

/* 写法 A：教科书递归版。每层递归都要在【调用栈】上留一个栈帧。 */
long long dfsRec(int u) {
    vis[u] = true;
    long long cnt = 1;
    for (int i = rowPtr[u]; i < rowPtr[u + 1]; ++i) {
        int v = colIdx[i];
        if (!vis[v]) cnt += dfsRec(v);
    }
    return cnt;
}

/* 写法 B：迭代版。把「调用栈」换成显式 stack<int>（在堆上），
   深度上限只受内存限制。等价写法：int stk[MAXN] + top 指针。 */
long long dfsIter(int s, int &maxDepth) {
    stack<int> st;
    vis[s] = true;
    st.push(s);                       /* 入栈即打标记 */
    maxDepth = 0;
    long long cnt = 0;
    while (!st.empty()) {
        int u = st.top(); st.pop();
        ++cnt;
        if ((int)st.size() + 1 > maxDepth) maxDepth = (int)st.size() + 1;   /* 含当前结点 */
        for (int i = rowPtr[u]; i < rowPtr[u + 1]; ++i) {
            int v = colIdx[i];
            if (!vis[v]) { vis[v] = true; st.push(v); }
        }
    }
    return cnt;
}

int main() {
    /* 1) 小图对拍：两种写法必须给出同一个答案 */
    buildChain(1000);
    clearVis();
    long long a = dfsRec(0);
    clearVis();
    int d1 = 0;
    long long b = dfsIter(0, d1);
    printf("1) n=1000 长链    ：递归版 %lld 个，迭代版 %lld 个，%s\n",
           a, b, (a == b ? "一致" : "不一致"));

    /* 2) 10^6 结点的长链：只跑迭代版 */
    buildChain(1000000);
    clearVis();
    int d2 = 0;
    long long c = dfsIter(0, d2);
    printf("2) n=1000000 长链 ：迭代版访问 %lld 个，显式栈最大深度 %d\n", c, d2);

    /* 3) 10^6 结点的梳状图：显式栈真的压到 50 万层 */
    buildComb(500000, 500000);
    clearVis();
    int d3 = 0;
    long long e = dfsIter(0, d3);
    printf("3) n=1000000 梳状 ：迭代版访问 %lld 个，显式栈最大深度 %d\n", e, d3);

    /* 4) 递归版在这里会怎样？——不真跑，只说明
       把第 2 步换成 dfsRec(0)，程序不会打印任何结果，而是直接以栈溢出收场。
       本机实测（MinGW-w64 g++ -O2）：递归 75000 层还能返回，80000 层进程
       以 0xC00000FD（STATUS_STACK_OVERFLOW）崩溃。10^6 的链要 10^6 层，必挂。 */
    printf("4) 递归版在 10^6 层深度下会爆栈（实测约 7.5 万层触顶），故跳过不跑\n");
    return 0;
}

真实输出（MinGW-w64 g++ -std=c++17 -O2）：

1) n=1000 长链    ：递归版 1000 个，迭代版 1000 个，一致
2) n=1000000 长链 ：迭代版访问 1000000 个，显式栈最大深度 1
3) n=1000000 梳状 ：迭代版访问 1000000 个，显式栈最大深度 500000
4) 递归版在 10^6 层深度下会爆栈（实测约 7.5 万层触顶），故跳过不跑

第二行反直觉——100 万结点的长链，迭代版访问了 100 万次，可显式栈最深只有 1 层，因为链上 每个顶点只有一条出边，压进去立刻被弹出。这说明递归深度不由「算法需要多少信息」决定，而由 「图里最长的那条路径有多长」决定：递归把这份路径记忆塞进调用栈，迭代把它写在明面上。 第三行才是重点：梳状图上显式栈压到 50 万层，占的是堆上的 500000 × 4 B ≈ 2 MB；同样深度换成递归，就是 50 万个栈帧压在线程栈上。

8.10.6 BFS 的工程落点：六度分隔、爬虫队列与消息扩散

8.7.4 与 8.7.5 讲了 BFS 的最短路与两个经典应用。BFS 在工程上还有一批「长得不像 BFS」的落点， 共同形态是：一层一层向外扩散，用一个队列维持当前边界。

① 六度分隔与 N 度人脉

「你和任何一个陌生人之间最多隔着六个人」来自 1967 年 Milgram 的连锁信实验，翻译成图论就是： 以你为源点做一次 BFS，最远那一层的层号是几。2016 年 Facebook 用 15.9 亿用户的社交图算过， 任意两人的平均分离度是 3.57，平均 4 跳就连上。可这张图上一次 BFS 要碰 10⁹ 个顶点、 10¹¹ 条边，不可能每个查询都跑一次全图 BFS。工程做法是离线预计算 + 双向 BFS + 地标索引： 预先算好一批「地标」到所有点的距离，任意两点的距离用 mink(dist(k,u) + dist(k,v)) 估出来，毫秒级返回，代价是结果只是上界。

② 网络爬虫的 URL 待抓队列

爬虫就是跑在网页链接图上的一次 BFS：种子 URL 入队，出队一个就下载、解析链接、把没见过的入队。 三个改造点：

• 去重。同一个 URL 会被成千上万个页面链到，必须记住「抓过没有」。100 亿条 URL 的哈希表 要几百 GB，所以工业爬虫常用布隆过滤器：1% 误判率时每个元素只要约 9.6 bit， 100 亿条约 12 GB；代价是可能漏抓，但绝不会重复抓（第 10 讲哈希思想的延伸）。
• 队列不再严格先进先出。纯 FIFO 会退化成「把某个站点抓穿」，所以要按站点分配配额、 加礼貌间隔，还要按 PageRank 之类的分数排优先级——换成优先队列就是 best-first search。
• 队列要能落地。爬到一半崩了不能从头再来，所以队列常常是分布式消息队列（磁盘 + 多机）。

③ P2P / 区块链的邻居扩散与路由跳数

比特币节点默认维持 8 条出站连接，新交易、新区块先发给这几个邻居，邻居再转发出去， 这叫 gossip（疫情扩散）协议：每轮把消息随机发给 k 个邻居，覆盖全网的期望轮数是 O(log n)，n = 10⁶、k = 8 时约 7 轮就能覆盖全网。关键在去重要极便宜—— 每个节点只为每条消息存几十字节的哈希（极简的 visited 集合），否则同一笔交易会被反复转成广播风暴。

路由协议 RIP 把每条链路看成权为 1 的边，用距离向量迭代求「到目的地最少几跳」，本质就是分布式 BFS。 它有一条著名的工程约束：最大跳数 15，16 表示不可达，因为距离向量算法遇到坏消息收敛极慢 （计数到无穷），只能用小上限兜底。想要权值就得换 OSPF——每个路由器用 Dijkstra 算最短路。 这一个例子把「BFS 只管无权图，带权要 Dijkstra」的边界画得清清楚楚（第 09 讲正题）。

8.10.7 选错容器，算法就错了

第 03 讲讲栈、第 04 讲讲队列时，它们是「两种受限的线性表」；到了图遍历，容器直接决定算法：

• 用队列取出下一个待扩展顶点 → 一层一层向外扩 → 就是 BFS，无权图上第一次到达即最短。
• 用栈（或递归）取出 → 一条路走到黑 → 就是 DFS，找到的路径不保证最短。
• 用优先队列（按累计代价排序）取出 → 每次先扩展当前最便宜的 → 就是 Dijkstra（第 09 讲）。

换句话说，这三个算法的代码骨架几乎是同一段，唯一的区别就是那个容器。更要命的是： 把 BFS 的队列换成栈，它就不再是 BFS，最短路的结论立刻失效，但访问序列仍然合法—— 算法「错了」不会报错，只会给出一个看起来合理的错误答案。

标记本身用什么存也是工程问题，这个「小小的布尔数组」在真实规模下并不小：

• 顶点编号连续时用布尔数组：1 字节/顶点，10⁸ 个顶点 = 100 MB；换成 bitset 压到 1 bit/顶点 = 12.5 MB，省 8 倍（第 06 讲的位运算在这里直接兑现成内存预算）。
• 顶点是字符串（URL、类型名）时编号不连续，只能用哈希表先做「名字 → 编号」映射（第 10 讲）。

8.10.8 图不一定在内存里：外存、图数据库与分布式

前面都偷偷假设了一件事：整张图能装进一台机器的内存。这个假设破了，工程上有三条路。

① 外存图算法（半外存 / semi-external）

网页图有 10¹² 条边，每条边两个 int 就是 8 TB，只能放磁盘。 半外存的意思是：顶点相关的 O(n) 数组（visited、dist）留在内存，边表放磁盘， 算法按「一遍一遍扫边」来组织。代价很实在：一次 BFS 的每一层都要扫一遍整张边表， 8 TB 按 500 MB/s 的读带宽算约 4.4 小时。这时 I/O 成了唯一瓶颈， O(n+e) 完全失去意义——要优化的是「扫几遍」，不是「比较几次」。

② 图数据库：为什么要专门的存储引擎

用关系数据库存图当然可以：一张 friend(a, b) 表。但「查朋友的朋友」在 SQL 里是 friend 表自己 JOIN 自己，查询深度每加 1，JOIN 的次数就加 1，代价随深度成倍增长。 Neo4j 这类图数据库用的是 免索引邻接（index-free adjacency）：每条关系记录直接存着两端结点 记录的物理位置，从 A 走到邻居就是顺着指针跳一下，成本是一次指针解引用，而不是一次索引查找或 JOIN，于是深度增加时代价只是线性叠加。代价也明确：为了「哪个方向都能 O(1) 跳过去」， 关系要双向各存一份，写入时同一份数据改多处，写放大明显；它也只擅长「顺着边走」的查询。 没有免费的午餐：图数据库是用写入代价和存储冗余，买下了遍历时的 O(1) 邻接。

③ 分布式图计算：以顶点为中心的 Pregel 模型

图大到单机内存绝对装不下时（10⁹ 顶点、10¹¹ 条边，CSR 要 400 GB 以上）， 只能把图切开分到多台机器上迭代。Google 2010 年的 Pregel 定下了这个模型：每一轮叫一个 superstep，每个顶点读上一轮收到的消息、更新自己的值、给邻居发消息；一轮结束后有一个 全局同步点（barrier），所有顶点都停下才进入下一轮；顶点可「投票停机」，全部停机则结束。 以 PageRank 为例，更新就是 rank(v) = (1−d)/n + d × Σ rank(u)/outdeg(u)，每条消息 就是一个数。好处是：程序员只写「一个顶点怎么处理消息」，不用操心怎么分片；Spark 上的 GraphX 是同一模型的实现。

代价也说清楚：同步屏障的长尾效应（一轮的时间由最慢的机器决定）、通信量惊人 （每条边一轮一条消息，10¹¹ 条边 × 4 B × 30 轮 ≈ 12 TB 网络流量）、以及 容错只能靠检查点加回滚重算——这也是真实图集群要上万兆网、分片时尽量把边留在本机的原因。

8.10.9 工程选型对比表

把这一节的结论压成一张表。考试看 8.5 节那张九维对比，工程落地看这张：

三条经验：规模先于一切——n ≤ 1000 且稠密就用矩阵，n ≥ 10⁵ 且 e 远小于 n² 就用 CSR 或链式前向星；读多写少用 CSR，写多用邻接表 / 前向星；别过早优化——绝大多数业务问题的图 只有几千个顶点，瓶颈在数据库和网络。真正需要 CSR、外存和 Pregel 的，就是社交网络、搜索引擎、 编译器和 GC 这几个「图就是主角」的领域——也正是本章开头列的那几个。

8.11 本章小结、易错点与自测

8.11.1 必须记住的十件事

8.11.2 易错点清单

8.11.3 考点速查

8.11.4 自测题（5 道）

8.11.5 配套编程练习