强连通分量

强连通分量（strongly connected component，SCC）是有向图中按“互相可达”划分出的极大顶点集合。在同一分量内，从任意一个顶点都能沿有向边到达另一个；不同分量之间即使有边，也无法同时存在往返的有向路线。将每个分量缩成一个顶点，会得到一个有向无环图。

例如，设有向边为 $a\to b,b\to c,c\to a,c\to d,d\to e,e\to d,e\to f$。前三个顶点组成有向三环，$d,e$ 可以相互到达，$f$ 没有出边。因此强连通分量为 $\{a,b,c\}$、$\{d,e\}$、$\{f\}$，而不是把忽略箭头后连成一片的六个顶点算作一个分量。

单向的分量间连接允许向右到达，却不提供回路。d到e与e到d均有边。

互达关系产生一个划分

设 $G=(V,E)$ 是有限有向图。写 $u{\to }^{\ast }v$ 表示存在从 $u$ 到 $v$ 的有向路径；允许零长度路径，故每点均可达自身。定义 $$u\sim v⟺u{\to }^{\ast }v\text{且}v{\to }^{\ast }u.$$ 这个关系是等价关系。自反性来自零长度路径；对称性直接来自定义；若 $u\sim v$ 且 $v\sim w$，将 $u{\to }^{\ast }v{\to }^{\ast }w$ 及反方向的两段路线分别连接，就有 $u\sim w$。连接后如出现重复顶点，可删去中间的闭合段，保留一条路径，因此不影响可达性。

等价类覆盖所有顶点且两两不交。一个等价类中的路径还可以取在类内：若从 $u$ 到 $v$ 的某条路径经过 $x$，且 $u\sim v$，则 $u{\to }^{\ast }x$，又有 $x{\to }^{\ast }v{\to }^{\ast }u$，故 $x\sim u$。所以该类诱导的子图确实强连通，而不仅是借助类外顶点才能互达。若再加入类外点后仍强连通，它便应与类内点等价，产生矛盾。因此等价类也正是极大的强连通顶点集。

这里“极大”表示不能再加入顶点而保留强连通性，不表示只选顶点数最多的一个强连通子图。小的分量与大的分量都属于划分；单顶点即便没有自环，也由零长度路径构成强连通分量。

缩点图没有有向环

缩点图或凝聚图以各强连通分量为顶点。若原图有一条边从分量 $C$ 指向不同分量 $D$，就在缩点图中画 $C\to D$；内部边不画成自环，重复的分量间边可合并。

定理。 凝聚图是有向无环图。

证明。 假设有不同分量构成有向环 $C_1\to C_2\to \cdots \to C_k\to C_1$。分量内部任意点互达，所以从 $C_1$ 内任一点，都可先到跨边起点，再依环上的跨边及各分量内部路线，到达任意 $C_i$ 内的点；沿环余下部分又能返回。于是各分量中的点全部互达，按上一节的等价关系应属同一分量。这与它们不同矛盾。

主例的凝聚图是一条三顶点链 $$\{a,b,c\}⟶\{d,e\}⟶\{f\}.$$ 原图含两个循环区域，而缩点后留下的是区域之间的依赖顺序。这使“有向图含环”与“分量之间无环”两件事同时成立。

完整算例与边的变化

对顶点 $c$，沿出边可到达六个顶点；但能到达 $c$ 的只有 $a,b,c$。二者取交正是其强连通分量。对 $d$，可达集合为 $\{d,e,f\}$，能到达它的集合为 $\{a,b,c,d,e\}$，交集为 $\{d,e\}$。这给出逐点核对分量的方法，虽未声称是大图上的高效实现。

变式。 给主例增加边 $f\to b$。现在每个点可沿原有边先走到 $f$，再到 $b$；从 $b$ 又可依原有边到达任何点。故全部六点合成一个强连通分量。新增一条边可能合并多个分量，但不会将一个原分量拆开，因为原有的互达路线仍存在。

反过来，删边可能拆分而不会合并分量。只删 $c\to a$ 后，$a,b,c$ 之间只剩向前路线，三者变为三个单点分量；$d,e$ 的双向关系保持。整个图的分量数由三变为五。

强连通与弱连通

忽略所有方向后得到的无向图若连通，称原图弱连通。强连通必然弱连通，因为有向路径忽略方向后仍是无向路径；逆命题不成立，最小例子是仅有边 $u\to v$ 的两点图。主例也弱连通，却分成三个强连通分量。

凝聚图能描述哪些循环块先于哪些块，但不能单独计算块内距离或原图两点间最短路：缩点舍去了内部路线长度。对于循环依赖分析，它回答的是互达范围；对于路径成本，仍需保留边权和分量内部的信息。