有向图tarjan算法一个不理解的地方

Question

为什么是low[x]=min(low[x],dfn[y])而不是low[x]=min(low[x],low[y])

Answer 1

算法完整步骤如下：

• 数组初始化：当首次搜索到点u时，dfn和low数组的值都为到该点的时间。
• 堆栈：每遍历到一个未被标记的点，将它入栈。
• 当点u可以到达点v时，如果点v不在栈中，那么low[u] = min{low[u],low[v]}；如果点v在栈中，那么low[u] = min{low[u],dfn[v]}。
• 每当搜索到一个点并经过以上步骤后，其low值等于dfn值，则将它以及在它之上的元素弹出栈。这些出栈元素组成一个强连通分量。
• 继续搜索（因为有向图可能有多个连通子图组成，而这些子图没有交集），直到所有点被遍历。

---

下面解释为什么公式是那样：

• low[u] 和 dfn[u] 都是用来记录每个节点的遍历时间戳。
• low[u] 表示当前点 u 可追溯到的最早时间戳。
• dfn[u] 则是当前点 u 第一次被遍历时的时间戳。
• 在遍历到点 u 时，low[u] 初始值就等于 dfn[u]。
• 如果点 u 可以到达点 v，且点 v 已经被遍历过，但没有被弹出栈，那么说明点 v 是在点 u 所在的强连通分量之内的。
  • 此时应该取 min{low[u],dfn[v]} 作为 low[u]的值。因为点 v 是在点 u 所在的强连通分量之内的，所以点 v 的时间戳 dfn[v] 一定是比点 u 早的，如果 low[u] 取 min{low[u], dfn[v]}，那么就能保证这个强连通分量中能追溯到的最早时间戳是在该强连通分量中的。
  • 而如果点 v 在栈中，说明点 v 没有被遍历过。如果点 v 在栈中，点 v 部分的深搜还没有结束，可能会继续找到更早的节点，所以点 v 的 low 值不能确定，所以我们采用 dfn[v]来更新 low[u]