浅谈 Tarjan 求连通分量中的 low 与 dfn

lalaji2010 · 2025-05-24 11:34:15 · 算法·理论

这篇文章能够帮助你什么

首先，你需要基本掌握 DFS 树的性质，Tarjan 求三个连通分量（强连通、边双、点双）的算法原理。而这篇文章仅针对其中一个常常令初学者困惑的点，也就是下面这行代码：

low[u]=min(low[u],dfn[v]);

为什么写 dfn[v] 而不是 low[v]，就是这篇文章的主题。

在 Tarjan 算法中，我们定义 dfn[u] 表示 u 在 dfs 树中通过树边第几个被遍历到。low[u] 表示以 u 为根节点的子树（包括 u）中的结点,走一次返祖边能够到达的最先遍历的点的 dfn 值。

注：无向图 DFS 树无横叉边，而有向图强连通分量由当前子树走到横叉边指向的子树（该子树先前一定遍历过，这是横叉边的定义）一定无法走回（若能走回，则一定早在横叉边指向的子树时走到当前子树）。

并且若 u 子树中存在点走回 u 的祖先（或 u 本身），则必定存在一个点 v 一步走回 u 的祖先（或 u 本身）。

由这个定义，我们可以理解 low[u]=min(low[u],dfn[v]); 的正确性。

再看这个式子：low[u]=min(low[u],dfn[v]);。我们理解 ta 是正确的，但是我们质疑 ta 是不是唯一正确的。其中最有迷惑性的疑惑就是：我们将 dfn[v] 改为 low[v]，是否正确？

先说结论：上述改写在点双连通分量求解中是错误的，而在强连通分量和边双连通分量求解中是正确的。

我们来研究一下原理。

我们对于有向图 G 求解强连通分量。

在原算法中，当我们遍历结点 u，考虑其孩子 w 的子树中是否存在 v 能够一步走到 u 的祖先结点来判定 u->v 是否可能构成强连通分量的一部分。

当我们改换写法后，v 结点走多步（途径的都是遍历过的点，且只走返祖边）回到 u 的祖先结点也是被允许的（即 low 的定义从走 1 步变成了走若干步）。我们分类讨论正确性。

若 v 走一步先到 w->v 上另一点 vv，做代换 v'=vv，再讨论 v' 走法，等价于讨论 v。我们只需证明在其他分类中的正确性即可。
若 v 走一步先到 u，再通过 u 走上 u 的祖先，则显然 u 向 v 的链上的点都能够走到 v 上面。这样写没有问题。而原写法是只标记 low[u] 防止弹出链 u->v。两个写法实现同样的目的。
若 v 走一步直接到 u 的祖先，该写法完全能够包含。

综上，强连通分量正确。

我们对于无向图 G 求解点双连通分量,本质是求割点。

在原算法中，当我们遍历结点 u，我们考虑其孩子 w 的子树中是否有结点 v 能够一步走到 u 的祖先，来判断 u 是否割开子树 w 和图的其他部分。

综上，点双错误。

我们对于无向图 G 求解边双连通分量,本质是求割边。

在原算法中，当我们遍历结点 u，我们考虑其孩子 w 的子树中是否有结点 v 能够一步走到 u 的祖先（或 u 本身），且不走边 (w,u)，来判断边 (u,w) 是否割开子树 w 和图的其他部分。

当我们改换写法后，v 结点走多步（途径的都是遍历过的点，且只走返祖边）回到 u 的祖先结点（或 u 本身）也是被允许的（即 low 的定义从走 1 步变成了走若干步）。我们分类讨论正确性。

综上，边双正确。