图系列第 2 篇：路径、环与连通性

嘿，朋友，欢迎回到图系列。

在第 1 篇里，我们打下了图论的第一块地基：图由顶点和边组成，顶点是“对象”，边是“关系”；关系可能是有方向的，也可能是没方向的；边上可以挂权重，表示距离、时间或者代价；我们还认识了“度”这个描述局部结构的统计量，以及路径、环、连通这三个概念的惊鸿一瞥。第 1 篇结尾我说过，这一篇会把它们从“眼熟”变成“吃透”。

这篇就是那张承诺的兑现。我们将正式研究图里最核心的“运动学”：一个人、一辆车、一个数据包，能不能从 A 走到 B？怎么走？走多远？会不会走着走着绕回原点？整张图是不是铁板一块，还是被分成了互不相通的孤岛？哪些点、哪些边是整张图的命门，一旦被拆掉，网络就分崩离析？

这些问题合在一起，就是图的“结构语言”。你可以把本篇想象成一场完整的体检：路径是“单次行程”，环是“循环路线”，可达性是“能不能到”，连通性是“整体骨架”，桥和割点是“脆弱部位”，而二分图则是“两侧配对”的特异体质。学完这一篇，你再看任何一张图，脑子里会自动弹出这些问题，而不是傻乎乎地盯着画面发呆。

为了让你读得轻松，我先交代三条阅读建议。第一，本篇概念多、关联密，建议手里拿张纸，每遇到一张 mermaid 图，就自己用手指顺着边“走”一遍，这比盯着看十遍都管用。第二，概念之间有严格的父子关系：路径是环的基础，可达性是连通的基础，连通性是桥和割点的基础，别跳着读。第三，如果你手痒，想亲手摆弄这些概念，强烈推荐打开我们配套的图论实验室，把图拖一拖、点一点，抽象立刻变具体。

好，出发。我们从最基础、也最日常的概念开始：路径。

第 1 章 路径：从“走”到“怎么走”

1.1 路径的定义：一段连续的脚步

想象你站在一个顶点上。沿着一条边走到邻居，再沿着一条边走到下一个邻居，如此反复。你踩过的顶点序列，加上你跨过的边序列，合起来就叫一条路径（Path）。

更严格一点：给定一张图 G = (V, E)，一条路径是一个顶点序列 v₀, v₁, v₂, …, vₖ，满足对于每一个 i（0 ≤ i < k），顶点 vᵢ 和 vᵢ₊₁ 之间都有一条边。序列里一共有 k + 1 个顶点，跨过了 k 条边。我们通常说“从 v₀ 到 vₖ 有一条路径”，v₀ 叫起点，vₖ 叫终点。

这里有一个很容易被忽略的细节：路径既要写顶点，也可以写边。顶点序列告诉我们“踩了哪些点”，边序列告诉我们“跨了哪些桥”。在简单图里，相邻两个顶点之间最多一条边，顶点序列就能唯一决定路径；但在多重图里，两个顶点之间可能有多条平行的边，这时只说顶点序列就不够了，必须把边也写出来。本篇默认讨论简单图，但心里要装着这个差别。

路径的长度（Length）是它经过的边的条数，也就是 k。经过 4 个顶点的路径长度为 3，经过 1 个顶点的路径长度为 0。长度为 0 的路径合法吗？合法。它表示“原地不动”：从 v₀ 到 v₀ 总有一条不花任何代价的路径，这在数学上很方便，后面定义距离、定义可达性时，都会用到这个“零长度路径”。

下面这张图是一个小小的交通网络，我们以它为例来数路径：

graph LR
    A[A] --- B[B]
    B --- C[C]
    C --- D[D]
    D --- E[E]
    A --- C
    B --- D
    A --- E

在这张图里，从 A 到 E 有多少条路径？我们先把简单的数出来：A → B → C → D → E 是一条；A → C → D → E 是一条；A → E 直接一步到位，也是一条；A → B → D → E 是一条；A → C → B → D → E 又是一条。这五条路径的顶点都不重复，是“干净”的路径。可如果你允许绕圈子，路径就变得无穷无尽了：A → B → C → B → C → D → E 算一条，A → C → B → C → D → E 也算一条，只要你愿意，可以在 B 和 C 之间来回穿梭任意多次再离开。

所以，研究路径时必须先回答一个问题：允不允许重复？

1.2 简单路径：不重复的“干净路线”

我们把“路径上没有任何顶点重复”的路径，叫作简单路径（Simple Path）。简单路径上每个顶点恰好出现一次，因此它的顶点数等于边数加一。前面数出的五条 A 到 E 的路径，全是简单路径；而那些在 B、C 之间来回绕的，都不是简单路径。

你可能会问：绕圈的路径有没有用？在绝大多数“找最优”的问题里，答案是否定的。设想你要找一条 A 到 E 最短的路径，如果一条候选路径里某个顶点出现了两次，比如 …→ X → … → X → …，那么把两次出现 X 之间的那一整段“环”抠掉，你得到一条更短的路径，而且它仍然从 A 通到 E。换句话说，任何绕圈的路径都可以“剪环”，剪到不绕为止，而剪完之后路径只会更短、绝不会更长。因此，找最短路径、判断是否可达、计算距离这类问题，只需要考虑简单路径就够了。

这个“剪环”的思想非常深刻，后面会在无数算法里反复出现：Dijkstra 求最短路径时不用考虑绕圈，Kruskal 构造生成树时坚决不要环，都是同一句话——环只会增加成本，不会带来收益。

还有一个边界情况要交代清楚：简单路径允许“起点等于终点”吗？这要看定义。通常我们说“路径”时允许起点等于终点，但那样它会退化成一条长度为 0 的路径（原地不动），或者形成一个闭合的环。环我们下一章专门讲，这里先记住：简单路径默认指顶点互不相同的路径，起点终点相同的闭合路线不叫简单路径，而叫环。

1.3 长度的两种口径：数边数，还是加权重

“路径有多长”这句话有两种完全不同的含义，取决于图有没有权重。

第一种口径是数边数，适用于无权图。路径长度 = 经过的边数。A → B → C → D → E 经过 4 条边，长度就是 4；A → E 只经过 1 条边，长度就是 1。这种口径朴素直观，地铁换乘、转发次数、跳数（hop）说的都是它。

第二种口径是加权重，适用于带权图。路径长度 = 经过的所有边的权重之和。比如地图上每条路标着公里数，那么“家到公司这条路多长”就是把沿途每条路的公里数加起来。注意：权重口径下，路径长度甚至可以不是整数，可以很大，也可以很小；如果存在负权边，长度还可能越走越小——这个坑我们留到最短路径那几篇再填。

下面这张带权图，把两种口径的差别摆在一起给你看：

graph LR
    A[起点] -- "3" --- B[中转一]
    B -- "5" --- E[终点]
    A -- "4" --- C[中转二]
    C -- "1" --- E
    C -- "2" --- B

从 A 到 E 有三条候选路线。第一条 A → B → E：按边数口径，长度是 2；按权重口径，长度是 3 + 5 = 8。第二条 A → C → E：按边数口径也是 2；按权重口径，长度是 4 + 1 = 5。第三条 A → C → B → E：按边数口径是 3；按权重口径，长度是 4 + 2 + 5 = 11。

有趣的事情来了：按边数口径，第一条和第二条并列最短（都是 2）；按权重口径，第二条独享最短（5）。同一个“最短”，两种答案。所以在真实问题里，我们必须先问清楚：你说的“短”，是经过的站少，还是花的时间少？这就是口径的含义。以后遇到“最短路径”这个词，默认指权重口径（因为更有用），但算法题里经常特意强调“无权图上的最短路径”，那时就回到边数口径。

1.4 路径的几条基本性质

路径虽然朴素，却有几条值得写进笔记的性质。

第一，存在性。两个顶点之间可能存在多条路径，也可能一条都没有。没有任何路径连接的两个顶点，我们称为“不可达”，这是下一章的主角。

第二，拼接性。如果从 u 到 v 有一条路径，从 v 到 w 也有一条路径，那么把两条路径接起来，就得到从 u 到 w 的一条路径。这条性质叫“路径的可拼接性”，听起来像废话，但它正是“可达性具有传递性”的根基。

第三，截取性。如果 v₀ → v₁ → … → vₖ 是一条路径，那么它的任何一段连续子序列，比如 v₂ → v₃ → v₄，也自动是一条路径。一条长路径的任何片段，仍然是一条合法的路径。

第四，简单化。只要 u 和 v 之间存在路径，就一定存在简单路径。方法就是 1.2 节说的“剪环”：不断删除重复顶点之间的那段绕路，直到没有重复为止。这个性质保证了我们在讨论“可达性”时，永远可以假设路径是简单的，从而让很多证明和算法变得干净。

第五，有限性。在一张有限图（顶点数有限）里，简单路径的长度不可能超过 n − 1，因为简单路径上顶点互不重复，最多只能把 n 个顶点各踩一遍。这个上界后面会反复用到：任何可达顶点对之间，都有一条长度不超过 n − 1 的简单路径。

1.5 为什么路径是图论的“第一公民”

你可能觉得路径的概念太显然了，不值得专门写一章。但请想一想：最短路径算法在做什么？在“所有路径中挑一条最省的”。图的遍历在做什么？系统地“枚举从起点出发的所有路径”。网络路由在做什么？“为数据包选择一条从源到目标的路径”。拓扑排序在做什么？在“任务依赖图”上找一条尊重所有箭头的线性“走法”。二分图匹配、最大流，本质上也都是在路径上做文章。

可以说，路径是图论里被提问最多、被研究最深的对象。把“路径”的定义、长度、简单性吃透，后面所有算法都会轻松一大截。这一章我们只定义了“怎么走”，下一章就要问一个更刺激的问题：“走着走着，能不能绕回原点？”

第 2 章 环：走出去，又绕回来

2.1 环的定义：起点就是终点

如果一条路径的起点和终点是同一个顶点，而且它至少跨过一条边，那么这条闭合的路径就叫一个环（Cycle），也叫回路、圈。环的长度是它经过的边的条数，也是它包含的顶点数（起点终点算同一个顶点，只数一次）。

环的关键词是“闭合”：从某个顶点出发，沿着边走，最后回到同一个顶点。长度至少为 1。长度为 0 的“原地不动”不算环，因为一条边都没走，没有形成任何循环。

在无向图里，我们通常要求环至少包含 3 个顶点。为什么？因为无向边 A—B 只有一条，从 A 走到 B 再走回 A，走的其实是同一条边的往返，并没有形成一个“圈”。为了把这种假循环排除掉，图论里约定：无向图的环，指的是简单环——顶点互不重复、只有起点和终点相同的闭合路线。按这个约定，无向图里最小的环是三角形，长度是 3。

下面这张图里有几个环？我们一起来数：

graph LR
    A --- B
    B --- C
    C --- A
    C --- D
    D --- E
    E --- A

肉眼可见的环至少有三个：A → B → C → A 是三角形；A → C → D → E → A 是四边形；A → B → C → D → E → A 是五边形。还有没有别的？比如 A → C → A？不存在，A 和 C 之间没有直接边。C → A → E → D → C 呢？它和 A → C → D → E → A 是同一个环，只是起点不同、方向相反，我们把它算作同一个环。所以在无向图里，一个环没有固定的起点，也没有固定的“走向”，旋转和镜像都算同一个环。

环的长度有名字：长度为 3 的环叫三角形，长度为 4 的叫四边形，奇数长度的环叫奇环，偶数长度的环叫偶环。奇环在后面判定二分图时会成为主角，请先把这两个词记下。

2.2 有向图的环：方向必须一致

有向图里的环，定义要严格得多：它是一条闭合的有向路径，也就是说，环上每一段都必须顺着箭头的方向走。箭头是单行道，逆着走是违法的。

看下面这张有向图：

graph LR
    A --> B
    B --> C
    C --> A
    C --> D
    D --> E
    E --> D
    A --> A

请你找找图里的环。A → B → C → A 是一个环，因为三个箭头首尾相接，方向一致。D → E → D 也是一个环，这是有向图特有的“双向环”：D 指向 E，E 指向 D，虽然只有两个顶点，但两条有向边方向相反，拼在一起就构成一个闭合回路。在无向图里这不算环，在有向图里算——这是无向与有向最重要的差别之一。

再看看 E → D 能不能和别的边拼成环。从 E 出发只能到 D，从 D 出发只能到 E，所以 D、E 之间的小环是独立的一圈。A → A 则是一个自环：从 A 出发，一条边直接回到 A，长度是 1。

所以有向图的环，长度可以是 1（自环）、2（双向箭头）、3 或更长。只要箭头首尾相接能走回原点，就是一个环。

有向图的环在现实世界里往往意味着“循环依赖”：A 需要 B，B 需要 C，C 又需要 A，谁都不敢先开工。工程里遇到循环依赖（比如两个 npm 包互相引用、数据库外键循环、编译器报循环 import），本质上就是在依赖图上发现了一个有向环。后面讲拓扑排序时你会看到，有向图能不能排出合理的先后顺序，完全取决于它有没有环。

2.3 自环与重边：两个边角料

第 1 篇我们提过自环和重边，这里把它们和环的关系彻底讲清楚。

**自环（Self-loop）**是连接顶点到它自身的边。有向图里，A → A 是一个长度为 1 的环，这个没有争议。无向图里，我们画一条从 A 出发又回到 A 的曲线，它算不算环？不同教材有不同约定：有的算长度为 1 的环，有的不算。入门阶段，我们默认讨论“简单图”：不允许自环，也不允许重边，这样环的最小长度就是 3。一旦遇到允许自环的图，只要知道“自环是最短的环”就够了。

**重边（Multiple Edge）**是两个顶点之间的多条平行边。无向图里，A 和 B 之间画两条平行线；有向图里，A → B 画两条箭头。重边会导致一个有趣的现象：无向图里 A 和 B 之间有两条平行边时，从 A 走第一条边到 B，再走第二条边回 A，似乎形成一个“长度为 2 的闭合路线”。但和前面一样，图论里通常不把这种“来回走两条平行边”算作环，因为去掉一条平行边，这个闭合路线立刻消失，它没有真正的“圈”的筋骨。所以讲环时，我们总是回到简单图：环至少 3 个顶点。

下面这张图把自环和重边一起展示，你可以对比感受一下：

graph LR
    A --> A
    A --> B
    A --> B
    B --> C
    C --> B

图中 A 有自环；A 到 B 有两条重边；B 和 C 之间是双向箭头，构成有向长度为 2 的环。要是把这张图当成现实系统：A 自环可能代表“某个任务依赖自己”（明显有 bug），A → B 的两条重边可能代表“两个渠道同时依赖”，B ↔ C 则代表“互相引用”。一张小图，三种经典问题。

2.4 无环图：没有环的世界

没有环的图叫无环图（Acyclic Graph）。无向无环图就是森林，连通的森林叫树；有向无环图有专门的缩写 DAG（Directed Acyclic Graph），它是拓扑排序、关键路径、动态规划在图上施展拳脚的主场。

无环图的重要性怎么强调都不过分。举几个例子：文件系统里目录的包含关系是一棵无向树；编译系统里的依赖关系是 DAG；工作流引擎里的任务编排是 DAG；区块链里的区块引用也是 DAG。它们共同的特点是：不会出现“先有鸡还是先有蛋”的死循环，所以总能找到一个合理的先后顺序。

这里先埋一个伏笔：判断一个图有没有环是面试常客，也是很多算法的前置步骤。无向图判环通常用并查集（树系列第 18 篇讲过）或 DFS；有向图判环通常用 DFS 或拓扑排序。这些在第 3、4 篇和第 8 篇都会正式登场，现在你只需要建立直觉：有环图“绕得回来”，无环图“回不来”。

2.5 环的两面性

环是好是坏？要看场景。在交通网络里，环意味着“多条路可选”，是冗余和韧性——一条路堵了，还可以绕另一条。在依赖系统里，环意味着死锁和矛盾，是必须消灭的缺陷。在算法里，环意味着“绕圈可能无限循环”，遍历和排序都要格外小心。同一张图，环的性质不变，变的是我们的目的。

记住一个小结论：树里没有环，图里可以有；有向图里，环的方向必须一致。 下一章我们要讨论一个更基本的问题：在图上，到底“能不能从 A 到 B”？

2.6 环的检测：算法直觉先行

既然环这么重要，怎么用程序判断一张图有没有环？完整算法要等第 4 篇（遍历）和第 8 篇（拓扑排序）才登场，但直觉现在就可以建立。

先看无向图。最经典的思路是“走一步，认一步”：从某个顶点出发做深度优先遍历，每走到一个新顶点，就记住“我是从哪条边来的”。如果遍历过程中，发现有一个顶点可以通过一条“不是自己来路”的边回到某个已经访问过的顶点，那就说明找到了一个环。为什么强调“不是来路”？因为无向图里从 A 走到 B，再从 B 顺着同一条边走回 A，只是原路返回，不是环；只有发现了“第二条路”回到已访问顶点，才说明存在闭合回路。

另一种思路是并查集：把顶点看成一个个集合，遍历每条边时，如果两个端点已经在同一个集合里，说明之前已经有一条路把它们连起来了，现在这条边又给它们搭了第二条路，环出现了；否则就把两个集合合并。这个“加边判环”的思路正是 Kruskal 最小生成树算法的核心，树系列第 18 篇已经打过照面。

再看有向图。有向图判环不能只看“回到已访问顶点”，因为 A → B 和 C → B 会让 B 被访问两次，但并没有环。正确的直觉是：只在“当前这条搜索路径上”的顶点被再次碰到，才算环——换句话说，箭头必须首尾相接，逆着走不算数。实现上通常给每个顶点记三种状态：未访问、正在访问、访问完毕；遍历时碰到“正在访问”的顶点，就说明找到了有向环。这个“三色标记”技巧是后面拓扑排序判断 DAG 的基石，第 8 篇会完整演示。

现在你只需要记住两句话：无向图判环，看重边是否带来“第二条路”；有向图判环，看箭头是否顺着当前路径绕回自己。有了这两句，第 4 篇和第 8 篇的代码就只是把它们翻译成语言而已。

第 3 章 可达性：从 A 到底能不能到 B

3.1 可达的定义：有路就行

给定一张图，如果存在一条从顶点 u 到顶点 v 的路径，我们就说 v 从 u 可达（Reachable），记作 u ⇝ v，或者干脆说“u 能到达 v”。

可达性只关心“有没有路”，不关心路有多长、有几条。哪怕只有一条绕了八十圈的路径，u 到 v 也是可达的；哪怕有一百条路径，v 到 u 也可能一个箭头都没有。在无向图里，情况要简单得多：因为边不分方向，u 到 v 有路，v 到 u 就一定有路——沿着同一条路径原路返回即可。可达性在无向图里是对称的。

在有向图里，对称性消失得干干净净。u → v 存在，不代表 v → u 存在。看下面这张有向图：

graph LR
    A --> B
    B --> C
    C --> D
    D --> A
    B --> E
    F --> E

从 A 出发，能到达哪些顶点？A → B → C → D → A，一路走下去，A、B、C、D 互相都能到达：从 A 能到 B、C、D，从 B 能到 C、D、A，从 C 能到 D、A、B，从 D 能到 A、B、C。这四兄弟组成一个“互达集团”。A 还能到 E（A → B → E），但 E 不能回到 A，因为 E 没有出边。再看 F：F 能到 E，但 E 不能到 F，F 也不能到 A、B、C、D 中的任何一个，因为 F 唯一的出边指向 E。所以 F 是一个“只出不进”的孤立入口，而 E 是“只进不出”的终点。

这张小图告诉我们有向可达性的三句箴言：第一，可达关系可以不对称；第二，一群互相可达的顶点会抱成团；第三，即使整张图“看起来连成一片”，箭头方向也能把世界切成无数个单向小隔间。

3.2 可达性的传递性

可达性有一条极其重要的性质：传递性。如果 u 能到达 v，v 能到达 w，那么 u 一定能到达 w——把两条路径首尾相接就行。这条性质我们在第 1 章讲路径拼接时已经打过招呼，现在是它兑现的时候。

传递性让“可达”变成了一种关系代数：u 能到达自己的所有直接邻居；能到达邻居的邻居；能到达邻居的邻居的邻居……无限传递下去，直到把所有能走到的顶点都覆盖完。这个过程，本质上就是图遍历（BFS/DFS）在做的事：从起点出发，一层一层向外扩张，把所有可达顶点都染上色。第 4 篇我们会把 BFS、DFS 拆开细讲，这里先给你一个预告：“求 u 的所有可达顶点” = “从 u 出发做一次遍历”。

顺着传递性的思路，还可以定义传递闭包（Transitive Closure）：把所有“直接或间接可达”的关系全部补充成一条显式的边，得到的稠密图就叫原图的传递闭包。Floyd-Warshall 算法（第 6 篇）能高效算出它。现在你只需要知道这个概念的存在，知道“可达”可以像乘法一样不断复合，最终得到一个完整的“谁到得了谁”的关系表。

3.3 无向与有向：对称性就是分水岭

把无向图和有向图的可达性放在一起对比，你会得到一个非常清爽的结论：

特性	无向图	有向图
u 可达 v 时，v 是否可达 u	一定（对称）	不一定（可能不对称）
“互相可达”的集团	就是连通分量	叫强连通分量
从一点出发能到哪	整张图的一个连通分量	出边方向决定的“下游集合”
判断方法	一次遍历	一次遍历（但只沿箭头）

这张表浓缩了本章最重要的一句话：无向图的可达性是双向的，有向图的可达性是单向的。 正因为有向图丢了对称性，才引出了下一章和第 5 章那套更精细的连通理论。别急，我们一步一步来。

3.4 可达性的应用

可达性听起来抽象，应用却无处不在。

社交网络里，“我能不能通过朋友链认识某人”就是可达性问题；“我和他隔几个人”是带长度的可达性问题。网页搜索里，“从首页点击几次能到达这篇博客”是链接图上的可达性。编译系统里，“这个头文件间接包含了谁”是依赖图上的可达性。安全审计里，“这个用户能否通过一系列权限操作访问那份机密文件”是权限图上的可达性。垃圾回收器里，“哪些对象从根对象可达”决定了哪些内存可以回收——可达性直接决定生死。

所以，千万别小看“有没有路”这个朴素问题。它是整张图的信息骨架：知道了每个顶点的可达集合，你就知道信息、资源、人流在系统里能流向哪里，不能流向哪里。

第 4 章 连通：整张图是不是铁板一块

4.1 连通图：任意两点之间都有路

把可达性的镜头拉远，从“两个点”拉到“整张图”，就得到了连通性的定义：一张无向图是连通的（Connected），如果任意两个顶点之间都存在一条路径。换句话说，从任何一个顶点出发，沿着边走，都能走到任何一个其他顶点，没有死角，没有孤岛。

注意三个细节。第一，连通性只对无向图定义。有向图有自己的“强连通”“弱连通”说法，那是第 5 章的内容。第二，“任意两个顶点”包括相距很远的两个点——哪怕 A 在图的东北角，B 在西南角，也必须有一条路把它们连起来。第三，单顶点的图（n = 1，m = 0）算连通图吗？算。只有一个顶点，没有任何别的顶点要到达，“任意两个顶点之间有路”这句话空真成立，所以我们规定单点图是连通的。这是约定，记住即可。

怎么判断一张无向图连不连通？最简单的办法：任选一个顶点做一次 BFS 或 DFS，数一数访问到了多少个顶点。如果访问到的顶点数等于 n，说明从这一个点就能走到所有点，图是连通的；如果小于 n，说明有顶点从起点根本走不到，图不连通。这个办法为什么够用？因为连通的定义是“任意两点”，而判断时只需要“从一点出发到达所有点”。两者等价：只要从某个点能到所有点，那么任意 u 和 v 之间，都可以通过 u → 起点 → v 的两段路拼出一条路径。这就是可达性传递性的又一次胜利。

4.2 连通分量：图里的“王国”划分

不连通的图长什么样？它会被分割成几块互不相通的区域，每块内部四通八达，块与块之间老死不相往来。我们把每一块这样的“最大互达集团”叫作一个连通分量（Connected Component）。

正式定义：连通分量是图的一个极大顶点子集，满足子集内部任意两个顶点之间都有路径，并且不能再加入任何其他顶点而不破坏这个性质。所谓“极大”，就是“能包多大包多大”：如果你往一个分量里再塞一个顶点，要么塞不进去（它和分量内顶点之间没有路），要么塞进去之后这个分量和别的分量就连成一片了。

连通分量有几个立刻能推出来的性质：

第一，分量之间没有边。如果两个分量之间存在一条边，那么这条边的两个端点就互相可达了，两个分量应该合并成一个——这违反“极大”的定义。所以分量之间像隔着真空，一条边都飞不过去。

第二，分量覆盖所有顶点。每个顶点至少属于一个分量；事实上，每个顶点恰好属于一个分量。连通分量把顶点集合划分成若干互不重叠的“王国”，这是“等价类”思想在图上最直观的体现。

第三，每个分量本身是一张连通图。你把目光聚焦到任何一个分量内部，它完全满足连通图的定义。

下面这张图有四个连通分量，请你先自己数，再对答案：

graph LR
    A --- B
    B --- C
    C --- A
    D --- E
    E --- F
    G
    H --- I

数出来了吗？第一个分量是 {A, B, C}：三角形，内部任意两点都有路。第二个分量是 {D, E, F}：一条链，D 到 F 隔着 E，但确实有路。第三个分量是 {G}：孤零零一个顶点，没有邻居。单顶点算不算连通分量？算。一张图里没有任何边，n 个顶点就是 n 个连通分量，每个分量都是单点。第四个分量是 {H, I}：一条边连成的最小“王国”。一共四个连通分量，你数对了吗？

注意 {A, B, C} 和 {D, E, F} 之间“看起来”离得很近，但没有一条真正的边连接它们，所以它们只能是两个分量。画图时距离是视觉上的事，连通是结构上的事，两者互不相干。

4.3 孤立顶点与分量计数

分量里有一个特殊角色：孤立顶点（Isolated Vertex），指度为零、没有任何边的顶点。它在图里就是一个光杆司令，自己成一个连通分量。孤立顶点和“单点分量”是同一回事。

于是我们得到一个非常实用的计数规则：一张无向图的连通分量数，等于“从零开始，用并查集或遍历合并出来的集团数”。具体怎么做？从任意未访问顶点出发做遍历，每开启一次新的遍历，分量数加一，直到所有顶点都访问过。遍历开启的次数，就是连通分量的个数。这个“数分量”的操作是图算法里的基本功，第 4 篇讲遍历时会手把手演示，树系列第 18 篇讲的并查集则是另一种动态维护连通分量的神器。

分量计数为什么重要？因为很多问题只有在一个分量内部才有意义：找最短路径，起点终点必须属于同一个分量，否则答案直接是“不可达”；判断图是否连通，等价于问“分量数是不是 1”；做图的可视化布局，通常也是先按分量把图拆开，再分别排列，避免节点挤成一团。

4.4 连通性与边数：一个常见的误区

一个流传很广的误区是：“边数大于等于顶点数减一，图就一定是连通的。”这句话是错的。反例很容易构造：6 个顶点分成两组三角形，每组 3 条边，总共 6 条边，而 n − 1 = 5，边数 6 > 5，图却完全不连通——两个三角形之间没有任何边。

正确的结论是单向的：如果图连通，那么 m ≥ n − 1。连通是“够多边”的充分条件之一，不是“边数多”的必然结果。边数只是必要条件，方向很重要。

反过来还有一个常见误区：“边数等于 n − 1 的图一定是树吗？”不一定。只有当它同时还连通时才是树。一个有 6 个顶点、5 条边但分成两块的图，边数也是 5，却既不是树也不是连通图。这个坑我们在第 6 章讲树与图的关系时还会踩一次，先记下来。

4.5 连通性的现实意义

连通性不是书斋里的概念，它是现实世界可靠性的第一道防线。

城市路网要连通，否则有小区永远出不去；电网要连通，否则有片区永远亮不了灯；通信网络要连通，否则有用户永远打不通电话；社交网络要连通，否则有人被隔绝在信息孤岛。反过来，生态学里的“物种栖息地是否连通”、流行病学里的“人群接触网络是否连通”、国际贸易里的“国家间贸易网是否连通”，都是同一句话的不同版本：系统内部的流动通道，有没有把所有人都串起来。

所以在分析任何真实网络时，第一个问题永远是：这张图有几个连通分量？分量是 1，万事大吉；分量大于 1，就要追问：哪些顶点被困在哪个分量里？需不需要补边把它们接起来？这种“补边接孤岛”的思维，是后面最小生成树（第 7 篇）的种子。

第 5 章 强连通：有向图自己的“铁板一块”

5.1 强连通图：箭头也要双向可达

无向图的连通性在有向图里直接照搬会出问题：A → B 存在，B 却到不了 A，那 A、B 算“连在一起”吗？直觉上它们共享一条边，但信息只能单向流动。为了精确描述有向图里的“铁板一块”，图论定义了强连通（Strongly Connected）：

一张有向图是强连通的，如果任意两个顶点 u 和 v 之间，既存在从 u 到 v 的路径，也存在从 v 到 u 的路径。

“任意两个顶点”意味着：你要能走到我，我也要能走回你，而且这不只是针对某两对顶点，而是全部顶点两两之间都必须双向可达。要求是不是很苛刻？是的，所以强连通图比无向连通图稀有得多。

看下面这张有向图，它强连通吗？

graph LR
    A --> B
    B --> C
    C --> A
    C --> D
    D --> B

先看 A、B、C 三兄弟：A → B → C → A 是一个环，所以 A 能到 B、C，B 能到 C、A，C 能到 A、B，三者两两双向可达。再看 D：D 能到 B（进而到 A、C），但 A、B、C 能到 D 吗？从 C 出发有一条 C → D，从 A 出发 A → B → C → D，从 B 出发 B → C → D，都能到 D！所以 D 也能和其余顶点双向可达。整张图强连通。关键就在于：每一个顶点都能“绕回”其他顶点，没有一个单向死胡同。

如果我把 C → D 这条边删掉，D 立刻变成孤岛：D 能到 B，但 B、C 到不了 D，强连通立刻破裂。你看，强连通对边的依赖就是这么敏感——一张图可能是“勉强强连通”，删一条边就散架。

5.2 强连通分量：有向图里的互达集团

强连通的要求太苛刻，大多数有向图都不满足。但没关系，我们可以像切连通分量那样，把有向图切成若干个内部强连通、彼此单向连接（甚至互不相连）的集团，每个集团叫一个强连通分量（Strongly Connected Component，SCC）。

定义：有向图的强连通分量是顶点的极大子集，子集内任意两个顶点互相可达，且不能再扩张。和无向连通分量相比，区别只有一个字：内部关系从“有路”升级成了“双向都有路”。

下面这张图包含多个 SCC，我们来一起拆解：

graph LR
    A --> B
    B --> C
    C --> A
    C --> D
    D --> E
    E --> D
    E --> F
    F --> G
    G --> F

这张图里有哪些强连通分量？第一块是 {A, B, C}，三角环，两两双向可达。第二块是 {D, E}，D ↔ E 双向箭头。第三块是 {F, G}，F ↔ G 双向箭头。三个分量之间怎么连接？C → D 把第一块指向第二块；E → F 把第二块指向第三块。箭头只能从前往后，回不去：从 {A,B,C} 能到 {D,E}，但 {D,E} 回不到 {A,B,C}；从 {D,E} 能到 {F,G}，但 {F,G} 回不到 {D,E}。

注意，单个顶点也是 SCC。比如上一节那张图里如果出现一个没有任何双向环的顶点，它自己就是一个“一人分量”。所以 SCC 的划分把顶点完整地、不重叠地分成若干集团，这一点和连通分量完全一样。

5.3 SCC 压缩：把图缩成一张 DAG

强连通分量最迷人的性质来了：如果把每个 SCC 看成一个“超级顶点”，把分量之间的有向边保留下来，得到的“分量图”一定是一张有向无环图（DAG）。为什么不可能有环？因为如果两个分量之间存在一个闭合的箭头回路，回路经过的所有顶点就全都互相可达了，它们早就该合并成同一个 SCC——这与“极大”矛盾。

这个“压缩”操作叫缩点（Condensation），它把一张复杂的有向图压缩成一张简洁的 DAG，结构立刻变得一目了然：谁依赖谁、谁先谁后、谁是最上游、谁是最下游，全写在缩点图里。

缩点图有什么用？三个经典场景：

第一，循环依赖检测。在一个软件工程的依赖图里，任何一个 SCC 如果包含两个以上顶点，就说明存在循环依赖；缩点之后，每个 SCC 就是一个需要人工处理的“坏包”。

第二，可达性加速。在缩点后的 DAG 上做可达性分析，比在原图上做快得多，因为超级顶点的数量远小于原顶点数量。很多编译器、构建系统的依赖分析都用这个套路。

第三，拓扑排序。缩点图是 DAG，天然存在拓扑序；按拓扑序从上游处理到下游，就是很多动态规划在图上展开的方式。

怎么高效地找出所有 SCC？最著名的算法是 Tarjan 算法和 Kosaraju 算法，两者都是线性时间 O(n + m)。它们会在图系列第 13 篇《强连通分量：Tarjan》里正面登场，到时我们会用深度优先搜索 + 时间戳 + 栈，把缩点图一步步搭出来。这一篇你只需要牢牢记住：SCC = 有向图里的互相可达集团，缩点之后必成 DAG。

5.4 弱连通：把箭头抹掉再看

有向图还有一种更宽松的连通观：把每条有向边上的箭头全部抹掉，当成无向图来看，如果这时图是连通的，就称原图弱连通（Weakly Connected）。

弱连通不要求双向可达，只要求“底层骨架”连成一片。打个比方：单向街组成的城市路网，虽然有些街道只能单向行驶，但只要你愿意绕路（或者违法逆行），所有路口还是连在一起的——这就是弱连通。强连通则要求每条街都允许你自由往返，要求高得多。

于是我们得到一个干净的关系链：

强连通 ⇒ 弱连通，但弱连通 ⇏ 强连通。

举例：A → B → C 这条链，抹掉箭头后是一条直线，弱连通；但 B 到不了 A、C 到不了 B，所以不满足强连通。再看一个极端的例子：两顶点之间只有一条有向边 A → B，抹掉箭头后 A、B 连在一起，弱连通成立，强连通不成立。所以“弱连通”只是说“底层是连通的”，信息流依然可能是单向的。

在真实系统里，这两种连通各自回答不同的问题：弱连通回答“物理上有没有被隔开”，强连通回答“信息上能不能互相到达”。一个城市路网可能是弱连通的，但某些路段单向，导致你从甲地到乙地必须绕远路；一个社交网络的“关注图”可能是弱连通的，但话题和情绪可能沿着箭头单向传播，形成回声室。

5.5 本篇连通性地图小结

到这里，连通性的完整地图已经展开，我们用一张表收束一下：

概念	适用图	定义	典型问题
连通	无向图	任意两点有路径	有几个连通分量
强连通	有向图	任意两点双向可达	是否强连通、SCC 划分
弱连通	有向图	抹掉箭头后连通	底层骨架是否完整
连通分量	无向图	极大互达集团	遍历/并查集计数
强连通分量	有向图	极大双向互达集团	Tarjan 缩点

这五个词是面试里最容易互相混淆的一堆，请务必对着这张表把“适用图”和“方向”刻进脑子里。下一章，我们把镜头拉回无向图，看一个与连通性强相关的特殊结构：树。

第 6 章 树与图：当连通遇上无环

6.1 树的图论定义：连通 + 无环

树系列里，我们一直把树当成一种层次结构：有根、有父有子、从上往下长。但从图论的视角看，树其实有一个更纯粹的定义：连通且无环的无向图，就是树。

这个定义不需要根，不需要父子，不需要层次。只要一张无向图满足“任意两点连通”和“没有任何环”两条，它就是树。你可以从任何一个顶点出发给它“装一个根”，但根是人为选择的视角，不是树的本质。

为什么这两条就够了？我们把它们拆开看。连通性保证树“没有孤岛”：任意两个节点之间都有路。无环性保证树“没有冗余”：任意两个节点之间不仅有一条路，而且只有唯一一条路。假如存在两条不同的路径连接 u 和 v，把两条路径拼起来，中间重复的部分一消，一定得到一个环——与无环矛盾。所以树最漂亮的等价性质是：

树 ⇔ 任意两个顶点之间有且仅有一条简单路径。

这个性质是树系列一切“唯一性”论断的根源：唯一路径、唯一祖先、唯一最近公共祖先，全由它而来。

下面这张图，左半边是树，右半边不是。你能说出右半边违反了什么吗？

graph LR
    subgraph 是树
        R[根] --- A
        R --- B
        A --- C
        A --- D
        B --- E
    end
    subgraph 不是树
        P --- Q
        Q --- R2
        R2 --- P
        P --- S
        S --- T
    end

左半边有 6 个顶点、5 条边，连通且无环，是树。右半边有 5 个顶点、5 条边：P、Q、R2 围成一个三角形（有环），所以不是树。尽管它连通，但多出来一条边，把唯一的路径破坏成了多条路径。

6.2 n 个顶点，n − 1 条边：树的“身材密码”

树有一条著名的身材密码：一棵有 n 个顶点的树，恰好有 n − 1 条边。 反过来，一张连通图如果有 n − 1 条边，它也一定是树。这两句话合起来，构成“树 = 连通 + n − 1 条边”的等价判定，也是面试里最高频的树论结论之一。

这个结论怎么来的？我们给两种证明直觉，都只需要一张图。

第一种直觉叫“拆叶子法”。树一定至少有一个叶子（度为 1 的顶点，或者 n = 1 时唯一的顶点）。从树上摘掉一个叶子和它连着的那条边，剩下的还是一棵树（连通性没被破坏，无环性更不会被破坏）。每摘一次，顶点数和边数同时减一。摘到最后剩一个顶点、零条边。全程摘掉了 n − 1 个顶点和 n − 1 条边，所以原树边数 = n − 1。这个证明过程本身也是一个很棒的算法思路：反复删叶子，最后剩下的结构能揭示树的各种秘密。

第二种直觉叫“从根生长法”。任选一个顶点当根，从根出发，每添加一个新顶点，必须用一条新边把它接到已有树上（否则不连通）；要得到全部 n 个顶点，必须做 n − 1 次这样的“接新点”操作，所以边数正好是 n − 1。这个方法更直观：树是“长”出来的，每长一个点，长一条边。

注意边界情况：n = 1 时，m = 0，公式 1 − 1 = 0 依然成立；n = 2 时，m = 1，一条边连两个点，也是树。公式对所有 n ≥ 1 都成立。

还要强调一个容易踩的坑：边数等于 n − 1 但图不连通，则它不是树。 比如 6 个顶点分成两串，每串 3 个顶点 2 条边，总共 4 条边 = n − 2，不满足；但如果分成一堆 4 个点 3 条边 + 一堆 2 个点 1 条边，总共 5 条边 = n − 1，却分成两个分量，不是树。所以“边数 = n − 1”必须和“连通”搭配使用，才能推出树。严谨的完整版本是：无向图满足以下任意两条，则第三条自动成立——连通、无环、m = n − 1。三条里至少两条成立，才能确定它是树。

6.3 生成树：从一张图里“抽出”一棵树

现在把视角从“画出来的树”转到“从图里长出来的树”。给定一张连通的无向图，能不能删掉一些边，让剩下的边仍然保持所有顶点连通，而且不再有环？当然能：从任意顶点出发做遍历，每第一次到达一个新顶点，就记下“带我来的那条边”。所有顶点都访问过之后，我们恰好记下了 n − 1 条边，它们连通了全部 n 个顶点，而且没有环——正好构成一棵树。

这样得到的树叫图的生成树（Spanning Tree）：它“生成”了原图的全部顶点，因此叫生成；它是一棵树，因此叫树。正式定义：连通图 G 的生成树，是 G 的一个子图，包含 G 的全部顶点，并且是一棵树。

看下面这个例子。左边是原图，右边是它的一棵生成树（加粗的边）：

graph LR
    subgraph 原图
        A --- B
        B --- C
        C --- D
        D --- A
        A --- C
    end
    subgraph 一棵生成树
        A2[A] === B2[B]
        B2 === C2[C]
        C2 === D2[D]
        D2 === A2
    end

原图有 4 个顶点、5 条边，连通且有环。右边这棵生成树保留了 4 个顶点和 4 条边（A–B、B–C、C–D、D–A），正好 n − 1 = 3 条边？等一下，右边画了 4 条边：A–B、B–C、C–D、D–A，一共 4 条，而 4 个顶点的树只需要 3 条边。我犯了一个故意的小错误，请你来抓：如果 A–B、B–C、C–D、D–A 四条边都在，A、B、C、D 就围成了一个四边形环，那它根本不是树。正确的生成树应该删掉其中一条，比如把 D–A 删掉，保留 A–B、B–C、C–D，共 3 条边，连成一条链，无环且连通。这一抓，恰好把“树 = 连通 + 无环 + n − 1 条边”三条性质全部复习了一遍。

6.4 生成树不唯一：一个图有多棵生成树

生成树不是唯一的。同一张连通图，选择不同的边，可以长出很多棵不同的生成树。比如刚才那张图，删 D–A 得到链 A–B–C–D；删 A–B 得到 A–D–C–B（加上 A–C）；删 B–C 得到 B–A–D–C；删 A–C 则保留 A–B、B–C、C–D、D–A 吗？不对，删掉 A–C 后剩 4 条边，还是环，还得再删一条。数一数你会发现，这张 4 顶点 5 边的图，不同的生成树数量可能不止一棵。

为什么强调“不唯一”？因为现实问题的核心往往不是“有没有生成树”，而是“哪棵生成树最好”。给每条边加上权重，比如铺设光缆的成本、架设电线的造价，问题立刻变成：在所有生成树里，找总权重最小的一棵。 这就是著名的最小生成树（Minimum Spanning Tree，MST） 问题。

MST 是图论里最经典的优化问题之一：n 个村庄要通网线，任意两家之间的光缆造价已知，怎么布线总造价最低？答案一定是一棵生成树——因为如果有环，删掉环上最贵的一条边，连通性不变、总价更低，所以最优解必然无环。求解它的两大算法是 Kruskal（按边权从小到大挑，并查集判环）和 Prim（从一个点出发不断吞并最近的邻居），会在图系列第 7 篇正面交锋。这一篇先把“生成树”这个名字和它的存在性吃透，MST 就是它身上长出的果实。

6.5 树在连通性分析中的角色

树和连通性的关系还可以更深入。树系列讲过的“最近公共祖先”“树的直径”，本质都是在利用“任意两点唯一路径”这个特性；而图上的许多算法，也会先把图“约简”成一棵生成树再分析。

举个例子：网络里的广播风暴问题。如果每个路由器都把收到的包向所有邻居转发，环会让同一个包无限循环，把网络打爆。解决办法之一就是只沿着生成树转发，每个包只走一条路径，既保证所有节点都能收到，又不会绕圈。生成树协议（STP）就是这么工作的：交换机们先协商出一棵生成树，然后把环上的某些端口“堵住”，让拓扑变成一棵无环树。你看，工程里最硬核的网络协议，内核居然就是我们这章学的“生成树”。

再看连通性：一张连通图有 n 个顶点、m 条边，其中“必须保留的骨架”至少是 n − 1 条边；多出来的 m − (n − 1) 条边，全部“长在环上”，是可以临时删除的冗余。所以 m − n + 1 这个数有一个专门的名字：环数（Cyclomatic Number），它度量了一张图里“环的独立个数”，在代码复杂度度量（圈复杂度）里也是主角。一个概念从图论走到软件工程，是不是很奇妙？

第 7 章 桥与割点：网络的命门

7.1 桥：一删就断的边

假设你负责维护一座城市的电网。绝大部分线路坏了都能修，但如果某一条特定的线路坏了，整座城市立刻分成两个互不供电的片区，那这条线路就是整个网络的命门。图论里，这样的边叫桥（Bridge），也叫割边（Cut Edge）。

正式定义：在无向图中，如果删除一条边 e 之后，图的连通分量数量增加了，那么 e 就是一座桥。

“分量数量增加”是精确的判据。删掉普通边，分量数不变（图还连在一起）；删掉桥，分量数 +1（图裂成两块）；如果原图本来就有多个分量，删掉某个分量里的桥，那个分量裂成两半，总分量数同样 +1。所以判断一条边是不是桥，标准动作就是：数删除前后的连通分量数，变了就是桥。

看下面这张图，请先猜一猜哪几条边是桥，再看答案：

graph LR
    A --- B
    B --- C
    C --- A
    C --- D
    D --- E
    E --- F
    F --- D

答案：A–B、B–C、C–A 都不是桥，因为删掉任意一条，剩下的两条还让 A、B、C 保持连通，图整体依然是一个分量。D–E 呢？删掉它，D 和 F 还在一个分量（D–F 直接相连），E 和 F 也相连，所以 D–F–E 让 D、E 仍然连通，D–E 也不是桥。等等，那这座图的桥到底在哪里？让我再检查一遍：D–F 边存在，F–D 是同一条边，所以 D、E、F 组成三角形，删 D–E 后 D–F–E 仍然连通。整张图没有任何桥。这提醒我们：环上的边不是桥。删掉环上任意一条边，环还能从另一侧绕回去，连通性不破。

我重新设计一张真正有桥的图：

graph LR
    A --- B
    B --- C
    C --- A
    C --- D
    D --- E
    E --- F
    F --- G
    G --- E
    D --- H

现在找桥：左边三角形 {A,B,C} 内部没有桥；右边 {E,F,G} 三角形内部也没有桥；连接两个三角形的唯一通道是 C–D 和 D–E 之间的 D……等等，D 连着 C、E、H 三条边。C–D 是桥吗？删掉 C–D，左边三角形和右边 {D,E,F,G} + H 分成两个分量，分量数 +1，所以 C–D 是桥。D–E 是桥吗？删掉 D–E，D 这边还连着 C 和 H，E 那边连着 F、G，两边不再连通，所以 D–E 也是桥。D–H 呢？H 是叶子，删掉 D–H，H 变成孤立顶点，分量数 +1，所以 D–H 也是桥——连接叶子的那条边永远是一座桥。

现在你看出规律了吗？一条边是桥，当且仅当它不在任何一个环上。 三角形内部的边都在环上，不是桥；C–D、D–E 不在任何环上，是桥；D–H 更不在环上，是桥。这个规律可以直接当判定口诀用。

7.2 割点：一拔就散的点

边的命门说完了，点的命门呢？割点（Articulation Point / Cut Vertex） 的定义和桥完全对称：在无向图中，如果删除顶点 v 以及它关联的所有边之后，连通分量数量增加，那么 v 就是一个割点。

注意删除顶点时，它身上的所有边会一起消失——点没了，它连出去的线自然全断。判断标准依然是：删除前后分量数是否变化。

看下面这张图，请找出割点：

graph LR
    A --- B
    B --- C
    C --- A
    C --- D
    D --- E
    E --- F
    F --- D
    D --- G

我们来逐个检查。删掉 A：剩下的 B–C–D–E–F–G 依然连成一个分量（B 通过 C 连到 D），分量数不变，A 不是割点。删掉 B：A 通过 A–C 还连着 C，分量数不变，B 不是割点。删掉 C：左边 {A, B} 和右边 {D, E, F, G} 立刻分成两个分量，分量数从 1 变 2，C 是割点！它像一个咽喉，掐住它，左侧和右侧彻底失联。删掉 D：左边 {A,B,C} 和右边 {E,F} 以及 {G} 会怎样？E–F 连着，G 孤立，分量数从 1 变 3，D 也是割点。删掉 E：D–F–G 还连着一整块，分量数不变，E 不是割点。删掉 G：G 是叶子，删掉它，剩下的还是一整个分量吗？原图 1 个分量，删掉叶子后剩下的 D–E–F 等仍然连通，分量数还是 1，所以 G 不是割点。等等，删掉叶子本身后，图还剩下 6 个顶点、一个分量；分量数没变，所以叶子不是割点。这和桥不一样：叶子边 D–G 是桥，但叶子顶点 G 不是割点。

所以割点的判定有一个反直觉之处：桥的两端不一定都是割点。 比如桥 D–G 的端点 G 不是割点（删掉 G，剩下的图依然连通）；端点 D 却是割点（因为 D 还连接着更大的一块）。只有“拔掉这个点会让图裂开”的点才是割点，单纯拔掉一个“树梢”不算。

7.3 桥与割点的关系：一对表亲

桥和割点像一对表亲：概念对称，规则却各有各的脾气。我们把关系整理成三条：

第一，桥不在任何环上，割点也不一定在任何环上。 C–D 这座桥连接的两个端点 C、D 都是割点吗？上面例子中 C 是割点，D 也是。但更一般地说，桥的端点可能不是割点（叶子端），也可能都是割点。

第二，环上的点不一定不是割点。 前面例子中 C 同时在三角形 {A,B,C} 上，但它依然是割点，因为它还兼任“连接右侧的咽喉”。所以“在环上”不能豁免割点身份。

第三，割点必是某些桥的端点吗？ 也不一定。考虑两个三角形共享一个顶点 C（像一个“8”字）：C 连接左右两个三角形，删掉 C，左右两个三角形分成两个分量，C 是割点；但整张图里没有任何桥（每个三角形内部是环，两个三角形之间唯一的连接点没有“边”可删）。所以割点可以存在，而桥一个都没有。

下面这张“8 字形”图，正好演示第三种情况：

graph LR
    A --- B
    B --- C
    C --- A
    C --- D
    D --- E
    E --- C

删掉 C，左边 {A,B} 和右边 {D,E} 分离，C 是割点。但每条边都在某个三角形上：A–B 在左三角，B–C 在左三角，C–A 在左三角，C–D 在右三角，D–E 在右三角，E–C 在右三角。没有一条边是桥。完美的“有割点无桥”反例。

7.4 为什么桥和割点重要：网络脆弱性

桥和割点是“网络脆弱性分析”的主角，因为它们直接对应现实中的单点故障（Single Point of Failure）。

一座桥对应的可能是：连接两个城市群的唯一一座跨江大桥、连接两个机房的一根海底光缆、连接两个电网片区的一条高压线。它坏了，整个世界分两半。一个割点对应的可能是：连接多个社区的唯一变电站、承担所有流量转发的核心路由器、供应链上垄断某种零件的唯一工厂。它宕了，无数下游瞬间失联。

正因为单点故障的代价如此高昂，工程上的应对策略几乎都围绕“消灭桥和割点”展开：建第二条跨江大桥、铺双路光缆、给核心路由器做热备、为关键零件找第二供应商。这些动作翻译成图论语言，就是加边：在桥的两侧各找一个顶点，连上一条新边，桥立刻掉进一个环里，不再是桥。加的这条边还有个专门名字，叫回边（Back Edge）。

这一思想还有一个更炫酷的应用：在一个连通图里，最少加几条边，能让它变成“没有桥的图”（边双连通）？答案是约等于“叶子数加一再除以二”，著名的“桥接”结论。等你读完第 13 篇 Tarjan，甚至可以亲手实现“找桥 → 缩点 → 加边”的完整流程。

7.5 怎么找桥和割点：算法预告

找桥和割点的朴素方法是：对每条边/每个顶点，删掉它，重数一次连通分量。复杂度是 O(m × (n + m))，图一大就爆炸。真正的线性算法是 Tarjan 的 DFS 树方法：对图做一次深度优先遍历，记录每个顶点的“发现时间”和“通过非树边能回溯到的最早祖先”，然后一条边是桥当且仅当它连接的两个顶点中，子顶点无法回溯到父顶点或更早；一个顶点是割点当且仅当它存在一个孩子，无法回溯到它或更早（根节点还要特判孩子数量）。

这套“low 值”技巧会在图系列第 13 篇（连同强连通分量）一起详细展开。本篇你的任务是建立几何直觉：桥是“独木桥”，割点是“咽喉要道”，它们都意味着删掉就裂开。 有了直觉，第 13 篇的代码就不会显得像天书。

第 8 章 二分图：把世界分成两组

8.1 二分图的定义：边永远跨组

这一章介绍一种特殊但极其常见的图：二分图（Bipartite Graph）。

定义：一张无向图的顶点可以分成两个集合 X 和 Y，满足以下两条：第一，X 和 Y 不相交，并且它们的并集就是全部顶点；第二，每条边的一端在 X 里，另一端在 Y 里，X 内部没有边，Y 内部也没有边。

换句话说，二分图的世界里只有两种角色，所有关系都发生在“两种角色之间”，同类之间绝不直接相连。把 X 涂成蓝色、Y 涂成红色，你会看到：每条边的两端颜色都不同，同色顶点之间没有任何边。

下面这张图是一个典型的二分图，X 组三个人、Y 组三个人：

graph LR
    subgraph X 组
        X1[学生 1]
        X2[学生 2]
        X3[学生 3]
    end
    subgraph Y 组
        Y1[课程 A]
        Y2[课程 B]
        Y3[课程 C]
    end
    X1 --- Y1
    X1 --- Y2
    X2 --- Y1
    X2 --- Y3
    X3 --- Y2
    X3 --- Y3

左边三个学生、右边三门课程，边表示“这个学生选了这门课”。学生之间不直接连接，课程之间也不直接连接，一切关系都发生在学生和课程之间。这就是二分图的典型长相：两组顶点，边只跨组。

一个立刻要澄清的直觉误区：“两组”不是画出来的，而是图本身的性质。 顶点没有事先标注“我是 X 组”的标签，判断一张图是不是二分图，要做的是：尝试把顶点分成两组，使得所有边都跨组。能分成，就是二分图；怎么都分不成，就不是。

8.2 身边的二分图：不止“男生女生”

二分图最常见的三个现实模型：

第一，选课关系。学生是一组，课程是另一组，边表示选课。同为学生之间没有边（除非你考虑同学关系，那就变成另一张图了），所以天然二分。

第二，演员与电影。演员一组、电影一组，边表示“这位演员出演了这部电影”。任何一条边都连接一个演员和一部电影，同类之间没有边——除非你重新定义顶点，比如“演员之间合过戏”就变成了普通图。

第三，工作岗位与求职者。求职者一组、职位一组，边表示“求职者可以胜任这个职位”。招聘平台的核心算法——职位推荐、简历匹配、面试官分配——统统建立在这张二分图上。

你有没有发现规律？二分图描述的是两类不同实体之间的配对关系。它天然适合“谁和谁可以搭在一起”的问题。也正是因为只有两类，很多在一般图上困难的问题，在二分图上会突然变简单。

8.3 怎么判定：染色法与奇环

判断一张图是不是二分图，有一个简单漂亮的算法：染色法。

任选一个顶点染成红色，然后沿着边 BFS/DFS 扩散：邻居必须染成蓝色，蓝色顶点的邻居必须染成红色，规则只有一条——相邻顶点的颜色必须不同。如果整张图都能顺利染完，它就是二分图；如果某个顶点在染色时发现“邻居已经染过色，而且颜色和自己相同”，说明矛盾发生，图不是二分图。

为什么染色会矛盾？因为矛盾意味着存在一条长度为奇数的闭合回路：你从红色出发，每走一条边颜色翻转一次，走偶数条边回到原色，走奇数条边颜色翻转。如果绕了一个“奇数环”，回到起点时颜色要求和自己相反，就产生了矛盾。所以二分图有一个等价的几何特征：

一张图是二分图，当且仅当它不含奇环（奇数长度的环）。

这个结论漂亮极了：把“能不能染色”翻译成了“有没有奇环”。任何三角形（长度为 3）都让图立刻失去二分性；任何长度为 5 的五角星环也一样。反之，只要所有环的长度都是偶数（或者根本没有环），图就是二分图。

下面这张图，左边是二分图，右边不是。你能用染色法找出右边的“病灶”吗？

graph LR
    subgraph 二分图
        A1 --- B1
        A1 --- B2
        A2 --- B1
        A2 --- B2
        A3 --- B1
    end
    subgraph 含奇环的图
        P1 --- P2
        P2 --- P3
        P3 --- P1
        P3 --- P4
        P4 --- P5
    end

左边：顶点 A1、A2、A3 一组，B1、B2 一组，所有边都跨组，是二分图。右边：P1–P2–P3–P1 围成一个三角形，长度为 3 的奇环，所以整个图不是二分图。哪怕 P4、P5 加得再多，一个奇环就足以宣判“非二分”。

特别注意：二分图允许“分组方式不唯一”吗？在一张连通二分图里，一旦固定任意一个顶点的颜色，整张图所有顶点的颜色都被唯一确定（因为每条边都在强制翻转颜色）。如果图不连通，每个连通分量可以独立选择“哪边叫 X、哪边叫 Y”，所以整体分组会有 2^k 种（k 是分量数）。这个细节在写判定代码时很容易踩坑，提前打个预防针。

8.4 为什么现在就要认识二分图

二分图不是孤立概念，它是后面两个重要主题的“地基”。

第一，应用。第 6 篇讲最短路径时，会看到二分图在“任务分配、时间表调度”里的应用；很多看起来复杂的调度问题，画成二分图后立刻变得清晰：一边是任务、一边是时段，边表示“该任务可以安排在该时段”，问题瞬间变成“能不能给每个任务找到互不冲突的时段”。

第二，匹配。第 15 篇讲匹配时，二分图是绝对主角：一边是求职者、一边是职位，求“最多能安排多少对不冲突的配对”，就是二分图最大匹配问题。匈牙利算法、增广路、完美匹配……这些听起来很高级的词，全都长在二分图这棵树上。

所以你不用现在就把二分图研究透，但必须建立第一印象：两类顶点、边只跨组、无奇环、适合配对。 等第 6 篇和第 15 篇再相遇时，你会像见到老朋友一样自然。

第 9 章 综合演练：一张图看尽本篇所有概念

学了这么多概念，是时候把它们放到同一张图里，看看它们如何协同工作。假设我们要分析一座城市的“校园网络”：顶点是教学楼、宿舍、图书馆、机房等建筑，边是光缆，箭头表示数据流方向（部分链路是单向的）。

9.1 从抽象回现实：一次断网事故的图论复盘

在动手分析之前，我们先讲一个真实感十足的小事故，你会看到这些概念是如何救场的。

某天凌晨，校园网监控突然报警：食堂和体育馆同时掉线。运维工程师打开拓扑图，一眼就锁定问题：连接实验楼和食堂的那段光缆断了。为什么判断得这么快？因为拓扑图上清清楚楚画着一条“独木桥链”：机房 → 宿舍一 → 实验楼 → 食堂 → 体育馆，中间没有任何备用链路。这段光缆就是一座桥，它一断，食堂和体育馆立刻从主网络里被切出去，形成一个新的连通分量。

工程师立刻查台账，发现这条链路恰好是去年“省钱方案”的产物：当时为了降低造价，把宿舍一到食堂的备用光缆砍了，只保留一条主链路。用本篇的语言说，那次“省钱”把一条原本在环上的边变成了桥——环被拆掉，冗余随之消失。从那天起，食堂和体育馆就成了全网络最脆弱的两个点。

更巧的是，一个月前安全巡检曾报告：机房到宿舍一的光缆利用率接近上限，建议加一条机房直连体育馆的备用线路。如果当时采纳，桥的两侧就会被一条新边连起来，桥落进新环里，这次断网根本不会发生。你看，“加边消桥”不只是理论，而是网络可靠性的日常功课。

这个故事里，路径（数据怎么走）、环（冗余从哪来）、桥（哪里一断就裂）、割点（机房是核心咽喉）、连通分量（断网后裂成几块）全部登场。概念不是躺在教科书里的名词，而是运维工程师看一张图时脑内自动弹出的检查清单。下面我们就带着这张清单，把校园网的每一处结构都体检一遍。

graph LR
    A[教学楼] --- B[图书馆]
    B --- C[机房]
    C --- A
    C --- D[宿舍一]
    D --- E[宿舍二]
    E --- F[礼堂]
    F --- D
    D --- G[实验楼]
    G --- H[食堂]
    H --- I[体育馆]
    I --- H

我们按本篇的顺序，把这张图“体检”一遍。

第一项：路径。从教学楼 A 到食堂 H，有路吗？有，A → C → D → G → H 就是一条简单路径，长度按边数算是 4。如果光缆上标着带宽延迟权重，我们还可以计算权重口径的长度，为第 5 篇的最短路径做准备。

第二项：环。图中至少有四个环：A–B–C 三角形；D–E–F 三角形；H–I 之间的双向环（如果 H 和 I 是两条方向相反的光缆，这就是有向 2-环；画成无向图则只是一条边，不算环）；以及更长的 A–C–D–G–H–I–H–D–C–A？不对，这条路线里 H 重复了，去掉重复段后得到 A–C–D–G–H–I–H 并不闭合。实际上大环有 A–B–C–A 和 D–E–F–D，还有 C–D–G–H–I–H–D–C 这种“带尾巴”的闭合路线，但简单环里最典型的就是那两个三角形。环的存在说明网络有冗余：三角形里任何一条光缆断了，数据都能绕另一侧走。

第三项：连通性与连通分量。从 A 出发能不能到达所有顶点？能，A → B → C → D → E → F → G → H → I，一路畅通。所以整张无向图是连通的，连通分量数恰好是 1。若把 H–I 之间那条双向链路删掉再单独看，H 和 I 仍然通过 H–I 边相连，无向图依旧连通——等等，删掉的是唯一的 H–I 边的话，H 和 I 就断了，分量数变成 2。这正是桥的判定练习。

第四项：桥与割点。先找桥：A–B 在三角形里，不是桥；B–C 在三角形里，不是桥；C–A 在三角形里，不是桥；D–E 在三角形里，不是桥；E–F 在三角形里，不是桥；F–D 在三角形里，不是桥；C–D 呢？删掉 C–D，左边 {A,B,C} 和右边 {D,E,F,G,H,I} 分成两个分量，所以 C–D 是桥；D–G 呢？删掉 D–G，G–H–I 与左边断开，是桥；G–H 呢？删掉 G–H，H–I 与 G 断开，是桥；H–I 呢？删掉 H–I，H 与 I 断开（注意 H–I 只有一条边），也是桥。所以这张图有四座桥：C–D、D–G、G–H、H–I。它们连成一条“独木桥链”，任何一个环节断掉，后面的建筑全部失联。割点呢？D 删掉后 {A,B,C}、{E,F}、{G,H,I} 分成三个分量，D 是割点；G、H 同理是割点；C 删掉后左右分离，C 也是割点。A、B、E、F、I 不是割点。

第五项：生成树。这张连通图有 9 个顶点、11 条边。它的生成树需要 8 条边：把两个三角形各删一条边、把四座桥保留，或者把桥链里保留一部分、把环上删掉一部分，都能得到不同的生成树。如果每条光缆有铺设成本，求“成本最低的连通方案”就是最小生成树，Kruskal 和 Prim 会在第 7 篇出手。

第六项：二分图。这张校园网络是二分图吗？它含有三角形 A–B–C，也就是奇环，所以不是二分图。如果哪天你给校园网加一台“汇聚交换机”，把建筑全部接到交换机上、建筑之间不直接互联，拓扑就变成星形：中心一个顶点，其余全是叶子，星形图是二分图（中心一组、叶子一组）。你看，同一批建筑，布线方式一变，图的“体质”就变了。

第七项：强连通与弱连通。如果光缆全变成单向箭头，问题就复杂了：A → B → C → A 组成强连通分量，D–E–F 三角环也组成一个强连通分量，H ↔ I 是第三个强连通分量，而 G 夹在 D 和 H 之间，如果只有 D → G → H 的单向箭头，G 只能从 D 收到数据、往 H 发数据，自己无法回到 D，所以 G 是一个“一人分量”。缩点之后，整个网络变成 DAG：三角形一 → C/D 方向 → 三角形二 → G → 三角形三，一目了然。

这一遍综合演练，把本篇所有概念都串起来了：路径、环、连通分量、桥、割点、生成树、二分图、强连通分量、缩点。如果你能独立把上面每一项都重新推一遍，这篇就算真正吃透了。

第 10 章 常见误区与易错点

概念越多，坑越多。这一章把初学者最容易踩的八个坑集中排一遍雷，每一坑都配一句“正确姿势”。读的时候请对照自己刚才的理解，看看中了几枪。

误区一：把“路径长度”两种口径混着用。 无权图里路径长度是边数，带权图里路径长度是权重和。有人在地图上数站点个数，却宣称“这是最短路径”，有人在做无权图 BFS 时却想着累加边权。正确姿势：先问图有没有权重，再决定用哪种口径；算法题里“无权图最短路径”和“带权图最短路径”是两个世界。

误区二：认为无向图里 A—B—A 是环。 无向图中，两个顶点之间只有一条边，走过去再走回来只是同一条边的往返，不是真正的环。无向图的简单环至少三个顶点。正确姿势：无向图找环，从三角形起步；要形成“回路”，至少需要三条不同的边。

误区三：把有向图的可达性当成对称的。 “A 能到 B，B 应该也能到 A 吧？”不，有向边是单行道。A → B 存在，只代表 A 能到 B；B 能不能到 A，要看 B 有没有别的路绕回 A。正确姿势：有向图里每一条可达关系都要单独验证两个方向。

误区四：把“连通”和“强连通”混为一谈。 连通只适用于无向图，强连通只适用于有向图。有人说“这张有向图是连通的”，严格说应该叫弱连通或强连通。正确姿势：看见有向图，先问“强”还是“弱”；看见无向图，直接说连通。

误区五：把“m ≥ n − 1”当成连通性的充分条件。 边数足够多不代表图连通，两个互不相连的三角形加起来，边数可以超过 n − 1，却有两个分量。正确姿势：连通性必须靠遍历或并查集实测；边数只能提供必要条件。

误区六：判定树时漏掉“连通”条件。 “n 个顶点 n − 1 条边，所以是树”这句话在图上不成立——还得加上连通。一个 6 顶点图分成一个三角形（3 点 3 边）和一个单边（2 点 1 边）加孤立点（1 点 0 边），总共 6 点 4 边，不等于 n − 1；但另一张 6 点 5 边分成两块的图，边数等于 n − 1 却依然不是树。正确姿势：树的完整判定是连通且无环，或连通且边数 n − 1；三者中至少满足两条才能推出第三条。

误区七：以为“桥的端点都是割点”。 叶子边一定是桥，但叶子顶点不是割点——删掉叶子，剩下的图照样连通。反之，“8 字形”图有割点却没有桥。正确姿势：桥和割点要分别验证“删除后分量数是否增加”，不能互相推导。

误区八：以为“画成两组就是二分图”。 顶点不会自带“我是 X 组”的标签，判断二分图靠的是能不能染色成功，而不是看起来像不像。看起来交错的星形图是二分图，看起来整齐的六边形如果是六边形环（长度 6，偶环）也是二分图，而任何三角形都直接判死刑。正确姿势：用染色法，或者等价地检查“有没有奇环”。

这些误区几乎每个都对应一道经典面试陷阱题。如果你能把这八条都讲给别人听，说明你已经不是“记住概念”，而是“理解了概念”。恭喜。

第 11 章 小结：连接结构的完整语言

在收尾之前，我们把这一篇的知识做一次总装，你会看到它们不是零散名词，而是一套层层递进的语言。

起点是路径：一段连续的脚步，长度有两种口径——无权图数边数，带权图加权重；简单路径不重复顶点，而任何绕圈的路径都能“剪环”变成简单路径。然后是环：闭合的路径，无向图至少三个顶点，有向图可以短到长度 1（自环）或 2（双向箭头）；环的有无把图分成有环图与无环图，无环图里最著名的两位是树和 DAG。接着是可达性：有路就行，无向对称、有向不对称、关系传递。再把镜头拉远，就得到连通性：无向图的连通分量是有向图的强连通分量的“无向版”；强连通分量内部双向可达，缩点后必成 DAG。树是连通无环的特例，n 个顶点 n − 1 条边，连通图的生成树是“最小连通骨架”，MST 是它的优化版。最后是两个“脆弱性”概念：桥和割点，一删就裂，它们是现实网络里单点故障的数学模型；以及一个“体质”概念：二分图，两类顶点、边只跨组、无奇环，专为配对问题而生。

这一套语言足够你读懂绝大多数图论文章和面试题了。下次拿到一张图，请按这个顺序问自己：有没有路径？有没有环？谁到得了谁？图连不连通？有几个分量？哪些边是桥？哪些点是割点？能不能染成两组？问完这七个问题，这张图在你眼里就不再是一团乱线，而是一份完整的结构体检报告。

术语速查表

术语	英文	一句话解释
路径	Path	沿边走出的顶点序列，长度 = 经过的边数或权重和
简单路径	Simple Path	顶点互不重复的路径
环 / 回路	Cycle	起点等于终点且至少走一条边的闭合路径
自环	Self-loop	顶点出发直接回到自身的边，长度为 1 的环
重边	Multiple Edge	两个顶点之间的多条平行边
无环图	Acyclic Graph	不含任何环的图
DAG	Directed Acyclic Graph	有向无环图，可拓扑排序
可达	Reachable	存在路径从 u 到 v
传递闭包	Transitive Closure	把间接可达也显式表达出来的关系表
连通图	Connected Graph	无向图，任意两点之间有路径
连通分量	Connected Component	无向图里的极大互达集团
孤立顶点	Isolated Vertex	度为零、自成一分量的顶点
强连通	Strongly Connected	有向图，任意两点双向可达
强连通分量	SCC	有向图里的极大双向互达集团
缩点	Condensation	把每个 SCC 压缩成一个超级顶点，得到 DAG
弱连通	Weakly Connected	抹掉箭头后无向图连通
树	Tree	连通且无环的无向图
生成树	Spanning Tree	包含全部顶点且构成树的子图
最小生成树	MST	权重和最小的生成树
桥 / 割边	Bridge / Cut Edge	删除后连通分量数增加的边
割点	Articulation Point	删除后连通分量数增加的顶点
奇环 / 偶环	Odd / Even Cycle	长度分别为奇数、偶数的环
二分图	Bipartite Graph	顶点分两组，边只在组间，不含奇环
染色法	Coloring	相邻顶点染不同色，判断二分图的算法
匹配	Matching	互不共享顶点的边集，二分图的核心问题

这张表可以当你的“随身词典”，遇到忘了的词就回来翻一翻。特别提醒：强连通、弱连通、连通这三个词是面试高频混淆点，务必按“适用图 + 方向要求”来区分。

自测题：看看你掌握了多少

下一篇预告

这一篇我们把图的结构语言学全了：路径、环、可达性、连通分量、强连通、树与生成树、桥、割点、二分图。概念有了，接下来的问题很现实：这些概念在计算机里到底怎么存？

下一篇《图系列第 3 篇：图的存储》将回答这个问题。我们会把邻接矩阵和邻接表这两种主流存储结构摊开来比较：各自的查询速度、空间开销、适用场景，以及带权图、有向图分别怎么存。看完那篇，你就能亲手把这一篇的“连通分量”“桥”“割点”用代码跑出来了。

在下一篇见面之前，送你一句本篇的总结：图论里最深的智慧，往往藏在最朴素的问题里——有没有路，绕不绕圈，连不连得通。 把这三个问题问清楚，你已经赢了一半。