「笔记」Tarjan 有向图强连通分量

有向图强连通分量

几个有向图连通性的概念

强连通分量

强连通图：若对于一个有向图中任意两个节点 $x, y$，既存在从 $x$ 到 $y$ 的路径，也存在从 $y$ 到 $x$ 的路径，则称该有向图为「强连通图」。（注意是路径不是边）

强连通分量：有向图的极大（尽量最大）的强连通子图，叫做「强连通分量」

上图中，$2, 3, 5$ 三个点虽然强连通，但不是「极大」的，所以不是强连通分量。$2, 3, 4, 5, 6$ 才是强连通分量。

再来几个搜索树的概念

还是刚刚那个图，若我们采用深度优先遍历，从左往右遍历每个点的子树，则边 $(u \rightarrow v)$ 可以分为 $4$ 种：

1. 树枝边：正常遍历的边，如图中 $(1 \rightarrow 2)$、$(2 \rightarrow 3)$、$(4 \rightarrow 6)$。
2. 前向边：$u$ 曾经为 $v$ 祖先的边，如图中 $(2 \rightarrow 6)$。
3. 后向边：$v$ 曾经为 $u$ 祖先的边，如图中 $(5 \rightarrow 2)$。
4. 横叉边，插到原来遍历过的子树上的边，如图中 $(6 \rightarrow 3)$。