企业官网建设流程全解析

大家好，我是熊猫钓鱼！欢迎大家和我一起探讨技术。希望您能点赞关注，谢谢！

《把定理跑出来》系列第 2 讲。第 1 讲我们把握手定理、计数公式、存储结构全部跑了一遍；这一讲进入图论真正的"发动机"——遍历。

DFS 和 BFS 的伪代码，看懂只要十分钟，但考试和工程里的坑全在细节里：为什么"给邻接矩阵求遍历序列"的题不能直接背代码？BFS 凭什么能求无权最短路？有向图的"连通"为什么有三种口径？判环和判二分图为什么都是遍历的"顺手之事"？

本讲 8 张图全部由文末代码生成，随机种子固定（SEED=2026），可复现。每个课本结论配断言验证。

摘要

• 遍历序列与存储结构绑定：同一张图，邻接矩阵与邻接表（插入序）的 DFS 序列在91.2%的随机图上不同、BFS 在88.1%上不同；把表内邻居排序后，两序列与矩阵完全一致（断言通过）——"给矩阵求 DFS 序"考的就是"邻居按编号升序"这个约定；
• 复杂度分野：n=1600 稀疏图（m=6n）上 BFS 邻接矩阵 85.3ms vs 邻接表 0.62ms（138 倍）；矩阵耗时随 n 呈 ~n² 增长，表近线性——O(n²) 与 O(n+e) 不是纸面推导；
• DFS 树深而瘦、BFS 树矮而胖：同一张 60 点连通图，DFS 生成树高42（平均深度 23.9），BFS 生成树高4（平均深度 2.5）——而 BFS 的层号恰好就是无权最短路跳数；
• 连通有三种口径：同一底图随机定向后，n=300、平均度 0.5 时：无向分量 226、弱连通 226（精确相等，断言）、强连通300——几乎每个点各自为政；Tarjan 与 Kosaraju 300 组随机图对拍零分歧；
• 遍历的应用三件套：三色 DFS 判环（回边指向灰色祖先）；BFS 染色判二分图——C₃/C₅/C₇ 染不上、C₄/C₆/C₈ 可染，500 个随机图与"暴力找奇圈"判定完全一致；随机图是二分图的概率随 p 断崖式衰减（p=0.05 时只剩 5.5%，p=0.1 归零）；
• 还第 1 讲的账：连通相变完整扫描 c∈[0, 8.0]——c=1.2 巨分量吞下 26.5%，c=6.0 全图连通概率才 6.7%，c=7.2 达 43.3%，c=8.0 到 73.3%，验证"几乎必然连通"发生在 c≈ln n≈6.7 之后。

关键词：DFS；BFS；遍历序列；生成树；连通分量；强连通分量；Tarjan；Kosaraju；判环；二分图染色；无权最短路；随机图相变

目录

• 1. 遍历的全部秘密：按什么顺序摸邻居
• 2. 遍历序列不是图的属性，是「图＋存储」的属性
• 3. 复杂度：O(n²) 与 O(n+e) 跑出来的分野
• 4. DFS 树与 BFS 树：一个深而瘦，一个矮而胖
  • 4.1 BFS 的层号就是无权最短路
• 5. 连通的三种口径：无向、弱连通、强连通
• 6. 遍历的应用：判环与二分图染色
• 7. 还账：完整的连通相变图
• 8. 本讲检查清单
• 9. 复现指南
• 10. 下一讲预告

1. 遍历的全部秘密：按什么顺序摸邻居

图的遍历只有一句话：从某个顶点出发，每个顶点恰好访问一次。所有变化都来自一个问题——“当前节点的多个邻居，先摸哪个？”

defdfs_seq(g,start=0):seen=[False]*g.n seq,stack=[],[start]whilestack:u=stack.pop()ifseen[u]:continueseen[u]=True;seq.append(u)stack.extend(reversed(g.neighbors(u)))# 邻居顺序 = 表序returnseqdefbfs_walk(g,start=0):seq,q=[],deque([start])seen=[False]*g.n;seen[start]=Trueparent=[-1]*g.n;depth=[0]*g.nwhileq:u=q.popleft();seq.append(u)forving.neighbors(u):# 邻居顺序 = 表序ifnotseen[v]:seen[v]=True;parent[v]=u depth[v]=depth[u]+1q.append(v)returnseq,parent,depth

注意g.neighbors(u)——邻居以什么顺序返回，取决于存储结构。这就是本讲第一个考点的入口。

2. 遍历序列不是图的属性，是「图＋存储」的属性

图 1：左：一张 5 点示例图，加边顺序 (0,3)(0,1)(1,2)(0,2)(2,4)。邻接表里 0 的邻居是 [3,1,2]（插入序），邻接矩阵里永远是 [1,2,3]（索引序）。同一起点，DFS 序列：矩阵 [0,1,2,4,3] vs 表 [0,3,1,2,4]。右：1000 个随机 8 点图——91.2% 的图上 DFS 序列不同，88.1% 上 BFS 序列不同。

这个实验我第一版跑出来是"差异率 0%"——查下去发现是边生成顺序恰好让邻接表天然有序（按 u 升序加边时，每个节点的邻居自动就是升序）。真实程序读边表（文件、数据库、网络）顺序是任意的，打乱加边顺序后差异才如实暴露。这个"差点写错的实验"本身就是教训：遍历序列的"唯一性"是存储结构的假象。

两条推论直接对应考试：

• 题目给邻接矩阵让你求 DFS/BFS 序列 → 隐含约定"邻居按编号升序"，按这个约定模拟即可；
• 题目给邻接表→ 看表内结点顺序（真题通常写明"按插入顺序"或"按升序"），没写就是出题不严谨，两种都算对；
• 判断题：“同一张图的生成树唯一吗？” → 不唯一（第 4 节图 3 给你看两种长法）。

3. 复杂度：O(n²) 与 O(n+e) 跑出来的分野

课本原话：邻接矩阵遍历 O(n²)，邻接表遍历 O(n+e)。

图 2：BFS 全图耗时，n 从 200 扫到 1600（双对数轴）。稀疏图（m=6n）：矩阵 0.85→85.3ms（n×8 时 ×100，斜率 ≈2.2，就是 n²），表 0.06→0.62ms（×10，近线性）——n=1600 时差 138 倍。稠密图（p=0.5，m≈n²/4）：两条线都奔着 n² 去，但表仍快 6.6 倍（19.7 vs 130.1ms，因为矩阵遍历邻居要扫整行找非零）。（计时有毫秒级抖动，引用本次运行值；量级结论稳定。）

两个细节值得记进笔记：

1. 矩阵的 O(n²) 在稀疏图上不是"常数大一点"，而是数量级地亏——你为 99.6% 是 0 的格子付了扫描费；
2. 表的 O(n+e) 里那个 e 是主角：第 1 讲"判边"表要 O(deg)，但"遍历"表只要 O(n+e)——操作决定选型，同一份存储在不同操作下优劣互换。

4. DFS 树与 BFS 树：一个深而瘦，一个矮而胖

遍历过程会顺手长出一棵生成树（访问到 u 时记录"是谁把我第一次发现的"——父指针）。同一张图、同一个起点，两种遍历长出的树形态天差地别：

图 3：同一张 60 点连通图、同一起点 0，纵向 = 深度。左：DFS 生成树，树高42、平均深度 23.9——一条几乎贯穿全图的"脊柱"，侧枝稀疏；右：BFS 生成树，树高4、平均深度 2.5——第 3 层就挤下了 28 个节点的"宽伞"。

树高差 10 倍。这不是画图技巧，是两种算法性格的几何投影：DFS 一条道走到黑（栈：后进先出），BFS 一层一层平推（队列：先进先出）。

4.1 BFS 的层号就是无权最短路

BFS 树有个"免费"的性质：depth[v] = 从起点到 v 的最短跳数。证明一行——队列按层出队，v 第一次被发现时经过的层数最少。

图 4：n=26 随机图的 BFS 树，第 d 层画在半径 d 的同心圆上。绿边 25 条树边，红字是层号——层号 = 跳数 = 无权最短路长度。"BFS 求无权最短路"不是需要背的口诀，是层号的定义。

考试题型：“用 BFS 求单源最短路径适用于____图” → 无权（或边权相等）。带权？请等第 4 讲的 Dijkstra。

5. 连通的三种口径：无向、弱连通、强连通

无向图谈连通很单纯；有向图的"连通"有三个口径，考试和工程都极易混淆：

图 5：左：一个 8 点有向图，Tarjan 求出 3 个 SCC（同色一组）——0-1-2、3-4-5、6-7 三个环；注意 6→7 有弧但 7 回不去 6，所以 6、7 各自成 SCC。右：同一底图随机定向（n=300），三种口径的分量数随密度变化——强连通（红线）永远 ≥ 弱连通（橙）= 无向分量（蓝），平均度 0.5 时：无向 226、弱连通 226、强连通300（几乎每个点各自为政）。

两个实验细节：

• 橙蓝两线完全重合不是巧合：弱连通就是把有向图当无向图数分量，同一底图必然相等——代码里我直接assert weak == undirected_comps，300 组随机图全过；
• Tarjan vs Kosaraju 对拍：两个算法独立实现，300 组随机有向图的 SCC 划分零分歧。Tarjan 一遍 DFS + low-link（408 重点），Kosaraju 两遍 DFS + 逆图（好懂）；考试手写推 Tarjan，工程心里装 Kosaraju。

SCC 的直觉应用：网页链接图、依赖循环检测、社交网络里的"互关小圈子"——都是"能互相到达"的强连通块。

6. 遍历的应用：判环与二分图染色

DFS 的三种访问状态（白=没来过、灰=在栈上、黑=已处理）顺手解决两个经典问题。

判环：DFS 过程中遇到一条指向灰色结点的边（回边）⟺ 有环。

图 6：左：DAG，三色 DFS 无回边 → 可拓扑排序；右：加了 2→0 这条弧，DFS 摸到灰色祖先 → 判有环。第 5 讲拓扑排序的前提（“图无环”）就用这个检查兜底。

二分图判定：BFS 染色（相邻点染不同色），染不上 ⟺ 有奇圈。

图 7：左：圈图染色实测——C₃/C₅/C₇ 染不上，C₄/C₆/C₈ 可染，500 个随机图与"暴力找奇圈"判定完全一致；右：随机图是二分图的概率随 p 断崖衰减——p=0.01 时 99.5%，p=0.05 只剩 5.5%，p=0.1 归零。

"二分图 ⟺ 无奇圈"这个定理（第 1 讲系列预告里的 Konig 定理的地基），右图给了它概率版注脚：随便连边的图几乎必然含奇圈——二分图是刻意构造出来的稀缺结构，不是随机碰上的。

7. 还账：完整的连通相变图

第 1 讲图 7 只扫到 c=1.6，"几乎必然连通"的 ln n 区域留了个尾巴。这一讲遍历工具齐了，把账还上：

图 8：n=800，c 从 0 扫到 8.0，每档 30 次重复。三条曲线：最大连通分量占比（蓝）、全图连通概率（绿）、碎片率=分量数/n（橙虚线）。c=1.2 时巨分量已吞下 26.5% 的顶点；c=2.4 时 88.2%；但"全图连通"要等到 c≈ln 800≈6.7——实测 c=6.0 时连通概率仅 6.7%，c=7.2 达 43.3%，c=8.0 到 73.3%。

这张图把第 1 讲的"巨分量诞生"（c=1，平均度刚过 1 碎片瞬间合并）和"几乎必然连通"（c=ln n）两个阈值放进同一坐标系——"图连成一片"和"巨分量出现"是两个差着 ln n 量级的事件。社交网络"六度空间"的数学原型就在这里。

8. 本讲检查清单

□ 给邻接矩阵/邻接表求 DFS、BFS 序列，邻居顺序各按什么？（矩阵升序；表按插入序，题目会约定） □ BFS/DFS 复杂度（邻接表）？（O(n+e)，第 3 节图 2 的 126 倍差距就是它） □ BFS 求无权最短路的原理一句话？（层号 = 首次发现时的跳数，图 4） □ 有向图三种"连通"的关系？（SCC ≥ 弱连通 = 无向分量，图 5） □ 三色 DFS 判环的依据？（回边指向灰色祖先，图 6） □ 二分图的判定条件？（BFS 可 2-染色 ⟺ 无奇圈，图 7；C5 不行 C6 行） □ 随机图巨分量诞生和全连通的阈值？（c=1 与 c=ln n，图 8）

9. 复现指南

graph-course/ ├── course2.py # 六组实验（双存储 + Tarjan/Kosaraju + 染色 + 相变，~380 行） ├── figs2.py # 8 张配图 ├── results/course2.json └── figures/

python course2.py# → results/course2.jsonpython figs2.py# → 8 张图

正确性断言（全部通过才出图）：表内排序后遍历序列与矩阵完全一致；弱连通分量数 = 无向分量数（同底图，300 组）；Tarjan = Kosaraju 的 SCC 划分（300 组）；染色判定 = 暴力奇圈搜索（500 组）；BFS 树高 = 最远点最短跳数。种子 SEED=2026，确定性结果逐字节一致。

10. 下一讲预告

第 3 讲《欧拉图与哈密顿图》：一笔画的充要条件（连通 + 奇点 0 或 2 个）我们不只验证，还用Hierholzer 算法把回路一步步"绣"出来；然后体验图论第一次"绝望"——哈密顿回路是 NP 完全的，暴力、状压、剪枝三种打法在 n=20 面前如何排队倒下。

遍历是图论的呼吸。这一讲之后，你写 DFS 时应该能"看见"邻居的排队顺序、树的形状、和正在变灰的祖先。

系列目录：第 1 讲 基本概念与存储 · 第 2 讲 遍历与连通（本篇）· 第 3 讲 欧拉图与哈密顿图 · 第 4 讲 最短路三件套 · 第 5 讲 生成树与拓扑排序 · 第 6 讲 网络流与匹配