专栏文章

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

llalaji2010
算法·理论参与者 6已保存评论 5

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
5 条
当前快照
1 份
快照标识符
@mip7yf6v
此快照首次捕获于
2025/12/03 07:38
3 个月前
此快照最后确认于
2025/12/03 07:38
3 个月前
查看原文

这篇文章能够帮助你什么

首先，你需要基本掌握 DFS 树的性质，Tarjan 求三个连通分量（强连通、边双、点双）的算法原理。而这篇文章仅针对其中一个常常令初学者困惑的点，也就是下面这行代码：
low[u]=min(low[u],dfn[v]);
为什么写 dfn[v]dfn[v] 而不是 low[v]low[v]，就是这篇文章的主题。

1.在 Tarjan 算法中的定义

在 Tarjan 算法中，我们定义 dfn[u]dfn[u] 表示 uu 在 dfs 树中通过树边第几个被遍历到。low[u]low[u] 表示以 uu 为根节点的子树（包括 uu）中的结点,走一次返祖边能够到达的最先遍历的点的 dfndfn 值。
注：无向图 DFS 树无横叉边，而有向图强连通分量由当前子树走到横叉边指向的子树（该子树先前一定遍历过，这是横叉边的定义）一定无法走回（若能走回，则一定早在横叉边指向的子树时走到当前子树）。
并且若 uu 子树中存在点走回 uu 的祖先（或 uu 本身），则必定存在一个点 vv 一步走回 uu 的祖先（或 uu 本身）。
由这个定义，我们可以理解 low[u]=min(low[u],dfn[v]); 的正确性。

2.疑惑点

再看这个式子：low[u]=min(low[u],dfn[v]);。我们理解 ta 是正确的，但是我们质疑 ta 是不是唯一正确的。其中最有迷惑性的疑惑就是：我们将 dfn[v]dfn[v] 改为 low[v]low[v]，是否正确？
先说结论：上述改写在点双连通分量求解中是错误的，而在强连通分量和边双连通分量求解中是正确的。
我们来研究一下原理。

Ⅰ 强连通分量

我们对于有向图 GG 求解强连通分量。
在原算法中，当我们遍历结点 uu，考虑其孩子 ww 的子树中是否存在 vv 能够一步走到 uu 的祖先结点来判定 u−>vu->v 是否可能构成强连通分量的一部分。
当我们改换写法后，vv 结点走多步（途径的都是遍历过的点，且只走返祖边）回到 uu 的祖先结点也是被允许的（即 lowlow 的定义从走 11 步变成了走若干步）。我们分类讨论正确性。
  1. 若 vv 走一步先到 w−>vw->v 上另一点 vvvv，做代换 v′=vvv'=vv，再讨论 v′v' 走法，等价于讨论 vv。我们只需证明在其他分类中的正确性即可。
  2. 若 vv 走一步先到 uu，再通过 uu 走上 uu 的祖先，则显然 uu 向 vv 的链上的点都能够走到 vv 上面。这样写没有问题。而原写法是只标记 low[u]low[u] 防止弹出链 u−>vu->v。两个写法实现同样的目的。
  3. 若 vv 走一步直接到 uu 的祖先，该写法完全能够包含。
综上，强连通分量正确。

Ⅱ 点双连通分量

我们对于无向图 GG 求解点双连通分量,本质是求割点。
在原算法中，当我们遍历结点 uu，我们考虑其孩子 ww 的子树中是否有结点 vv 能够一步走到 uu 的祖先，来判断 uu 是否割开子树 ww 和图的其他部分。
当我们改换写法后，vv 结点走多步（途径的都是遍历过的点，且只走返祖边）回到 uu 的祖先结点也是被允许的（即 lowlow 的定义从走 11 步变成了走若干步）。我们分类讨论正确性。
  1. 若 vv 走一步先到 ww 子树内另一点 vvvv，做代换 v′=vvv'=vv，再讨论 v′v' 走法，等价于讨论 vv。我们只需证明在其他分类中的正确性即可。
  2. 若 vv 走一步先到 uu，再通过 uu 走上 uu 的祖先。原写法只能走到 uu。若 uu 是割点，原写法正确，而改后的写法却会认为 vv 可以走出去，错误。
  3. 若 vv 走一步直接到 uu 的祖先，该写法没有影响。
综上，点双错误。

Ⅲ 边双连通分量

我们对于无向图 GG 求解边双连通分量,本质是求割边。
在原算法中，当我们遍历结点 uu，我们考虑其孩子 ww 的子树中是否有结点 vv 能够一步走到 uu 的祖先（或 uu 本身），且不走边 (w,u)(w,u)，来判断边 (u,w)(u,w) 是否割开子树 ww 和图的其他部分。
当我们改换写法后，vv 结点走多步（途径的都是遍历过的点，且只走返祖边）回到 uu 的祖先结点（或 uu 本身）也是被允许的（即 lowlow 的定义从走 11 步变成了走若干步）。我们分类讨论正确性。
  1. 若 vv 走一步先到 ww 子树内另一点 vvvv，做代换 v′=vvv'=vv，再讨论 v′v' 走法，等价于讨论 vv。我们只需证明在其他分类中的正确性即可。
  2. 若 vv 走一步先到 uu，再通过 uu 走上 uu 的祖先。原写法只是走到 uu。考虑删掉边 (u,w)(u,w)，这个操作并不会影响我们走到 uu，不影响正确性。
  3. 若 vv 走一步直接到 uu 的祖先，该写法没有影响。
综上，边双正确。

Thanks

评论

共 5 条评论，欢迎与作者交流。

正在加载评论...