无向图的双连通性（Biconnectivity）与关节点（Articulation Points）检测的 Tarjan 算法
字数 3689 2025-12-22 15:07:37

无向图的双连通性（Biconnectivity）与关节点（Articulation Points）检测的 Tarjan 算法

题目描述
在无向连通图 \(G = (V, E)\) 中，一个顶点被称为“关节点”（Articulation Point，或割点），如果将其移除（连同与其相连的所有边）会导致图不再连通。类似地，一条边被称为“桥”（Bridge），如果将其移除会导致图不再连通。
本题目要求检测一个无向连通图中的所有关节点。更精确地，给定一个无向图（可能不连通），我们需要找出所有关节点。
这个问题在图论中有广泛应用，例如在网络可靠性分析、电路板布线、社交网络关键人物识别中。
我们将重点讲解使用基于深度优先搜索（DFS）的 Tarjan 算法来高效地找出所有关节点。

解题过程循序渐进讲解

1. 问题形式化与基本观察
设无向图 \(G = (V, E)\)，\(n = |V|\)，\(m = |E|\)。

  • 若 \(G\) 原本就不连通，则删除任何一个顶点可能只是让连通分量数目增加，但通常我们仍关心每个连通分量中的关节点。
  • 关节点定义：对于顶点 \(v\)，如果存在 \(G\) 中两个不同的顶点 \(u\) 和 \(w\)，使得 \(u\) 和 \(w\) 之间的所有路径都经过 \(v\)，则 \(v\) 是关节点。
    等价地，在 DFS 生成树中，\(v\) 是关节点当且仅当：
    1. \(v\) 是 DFS 树的根，且至少有两个子节点；
    2. \(v\) 不是根，且存在一个子节点 \(u\)，使得以 \(u\) 为根的子树中没有“后向边”能够到达 \(v\) 的祖先。

2. 算法核心思路
我们进行一次 DFS，为每个顶点 \(v\) 记录两个值：

  • \(\text{disc}[v]\)：DFS 首次访问 \(v\) 的时间戳（discovery time），从 1 开始递增。
  • \(\text{low}[v]\)：从 \(v\) 出发，通过 DFS 树边以及最多一条后向边（即非树边且指向祖先的边）能够到达的顶点的最小 \(\text{disc}\) 值。

\[ \text{low}[v] = \min \begin{cases} \text{disc}[v] \\ \text{disc}[u] & \text{对于每条后向边 } (v, u) \\ \text{low}[c] & \text{对于每个子节点 } c \text{ 的树边 } (v, c) \end{cases} \]

关节点的判定条件（在 DFS 过程中）：

  • 根节点：如果根在 DFS 树中有多于 1 个子节点（注意：是 DFS 树中的子节点，不是原图中度的大小），则根是关节点。
  • 非根节点 \(v\)：如果存在一个子节点 \(u\) 满足 \(\text{low}[u] \ge \text{disc}[v]\)，则 \(v\) 是关节点。
    解释：条件 \(\text{low}[u] \ge \text{disc}[v]\) 意味着以 \(u\) 为根的子树中，没有任何后向边能够“绕开” \(v\) 到达 \(v\) 的祖先，因此删除 \(v\) 后，\(u\) 所在的子树就会与图的其余部分断开。

3. 算法详细步骤
我们用递归 DFS 实现，同时用一个栈来处理双连通分量（本题只需求关节点，但 low 值的定义与双连通分量计算一致）。

初始化：

  • 数组 \(\text{disc}[v] = 0\) 表示未访问。
  • 数组 \(\text{low}[v]\) 在访问时初始化。
  • 数组 \(\text{parent}[v]\) 记录 DFS 树中的父节点。
  • 全局变量 \(\text{time} = 0\) 用于时间戳。
  • 列表 \(\text{articulationPoints}\) 存储结果。

递归函数 \(\text{DFS}(v)\)：

  1. 设置 \(\text{disc}[v] = \text{low}[v] = ++\text{time}\)。
  2. 初始化子节点计数 \(\text{children} = 0\)。
  3. 对于 \(v\) 的每个邻居 \(u\)：
    • 如果 \(u\) 未被访问（即 \(\text{disc}[u] == 0\)）：
      • 设置 \(\text{parent}[u] = v\)。
      • \(\text{children} = \text{children} + 1\)。
      • 递归调用 \(\text{DFS}(u)\)。
      • 递归返回后，更新 \(\text{low}[v] = \min(\text{low}[v], \text{low}[u])\)。
      • 关节点检查：
        • 如果 \(v\) 不是根（即 \(\text{parent}[v] \neq -1\)）且 \(\text{low}[u] \ge \text{disc}[v]\)，则 \(v\) 是关节点。
    • 否则如果 \(u\) 不是 \(v\) 的父节点（即已访问且 \(u \neq \text{parent}[v]\)）：
      • 这是一条后向边（指向祖先或兄弟），更新 \(\text{low}[v] = \min(\text{low}[v], \text{disc}[u])\)。
  4. 在递归返回后，检查根节点：如果 \(v\) 是根（即 \(\text{parent}[v] == -1\)）且 \(\text{children} \ge 2\)，则 \(v\) 是关节点。

注意：为了避免将父节点误认为后向边，我们需判断 \(u \neq \text{parent}[v]\)。

4. 举例说明
考虑一个简单无向图：
顶点：0, 1, 2, 3, 4
边：(0,1), (1,2), (2,0), (1,3), (3,4)

我们从顶点 0 开始 DFS：

  • 访问 0（disc=1, low=1），邻居 1 未访问，递归到 1。
  • 访问 1（disc=2, low=2），邻居 0 已访问但为父节点，忽略；邻居 2 未访问，递归到 2。
  • 访问 2（disc=3, low=3），邻居 0 已访问且不是父节点（0 是祖先），后向边，更新 low[2] = min(3, disc[0]=1) = 1；邻居 1 已访问且是父节点，忽略。返回时，low[1] = min(2, low[2]=1) = 1。
  • 回到 1，邻居 3 未访问，递归到 3。
  • 访问 3（disc=4, low=4），邻居 1 是父节点，忽略；邻居 4 未访问，递归到 4。
  • 访问 4（disc=5, low=5），邻居 3 是父节点，忽略。返回时，检查 4 无其他邻居，返回 3。
  • 在 3 处，子节点 4 的 low[4]=5，检查 low[4] >= disc[3]? 5 >= 4 成立，因此 3 是关节点。
  • 回到 1，检查子节点 2 的 low[2]=1，low[2] < disc[1] 不成立，所以此时不标记 1；子节点 3 的 low[3]=4，low[3] >= disc[1]? 4 >= 2 成立，因此 1 是关节点。
  • 最后检查根节点 0：children = 1（只有 1 一个子节点），所以 0 不是关节点。

结果：关节点是 1 和 3。

5. 算法复杂度分析

  • 时间复杂度：\(O(n + m)\)，因为每个顶点和边只被访问常数次（标准 DFS）。
  • 空间复杂度：\(O(n)\) 用于存储 disc、low、parent 数组以及递归栈。

6. 注意事项与边界情况

  • 图可能不连通：需要对每个未访问的顶点作为根分别进行 DFS。
  • 自环与重边：自环不影响关节点判定（因为自环不算后向边）；重边在无向图中通常作为两条相同的边，但算法中处理时，如果遇到一条边 (v,u) 且 u 是父节点，忽略它，但若还有另一条 (v,u)，则这条重边应视为后向边（因为 u 已被访问且不是当前递归的父节点？实际上在无向图中，每条边会被遍历两次，所以第一次是树边，第二次时 u 是父节点，应忽略。但若存在多条平行边，则需要额外处理，通常可记录访问次数或对邻接表去重）。
  • 实践中，我们通常在无向图中忽略指向父节点的边即可正确处理。

7. 总结
本算法是 Tarjan 基于 DFS 的经典应用，一次 DFS 即可求出所有关节点，高效且易于实现。掌握这个算法不仅能够解决关节点检测，也为学习双连通分量、桥检测等更深入的图论问题打下基础。

无向图的双连通性（Biconnectivity）与关节点（Articulation Points）检测的 Tarjan 算法 题目描述 在无向连通图 \( G = (V, E) \) 中，一个顶点被称为“关节点”（Articulation Point，或割点），如果将其移除（连同与其相连的所有边）会导致图不再连通。类似地，一条边被称为“桥”（Bridge），如果将其移除会导致图不再连通。 本题目要求检测一个无向连通图中的所有关节点。更精确地，给定一个无向图（可能不连通），我们需要找出所有关节点。 这个问题在图论中有广泛应用，例如在网络可靠性分析、电路板布线、社交网络关键人物识别中。 我们将重点讲解使用基于深度优先搜索（DFS）的 Tarjan 算法来高效地找出所有关节点。 解题过程循序渐进讲解 1. 问题形式化与基本观察 设无向图 \( G = (V, E) \)，\( n = |V| \)，\( m = |E| \)。 若 \( G \) 原本就不连通，则删除任何一个顶点可能只是让连通分量数目增加，但通常我们仍关心每个连通分量中的关节点。 关节点定义：对于顶点 \( v \)，如果存在 \( G \) 中两个不同的顶点 \( u \) 和 \( w \)，使得 \( u \) 和 \( w \) 之间的所有路径都经过 \( v \)，则 \( v \) 是关节点。 等价地，在 DFS 生成树中，\( v \) 是关节点当且仅当： \( v \) 是 DFS 树的根，且至少有两个子节点； \( v \) 不是根，且存在一个子节点 \( u \)，使得以 \( u \) 为根的子树中没有“后向边”能够到达 \( v \) 的祖先。 2. 算法核心思路 我们进行一次 DFS，为每个顶点 \( v \) 记录两个值： \( \text{disc}[ v ] \)：DFS 首次访问 \( v \) 的时间戳（discovery time），从 1 开始递增。 \( \text{low}[ v ] \)：从 \( v \) 出发，通过 DFS 树边以及最多一条后向边（即非树边且指向祖先的边）能够到达的顶点的最小 \( \text{disc} \) 值。 \[ \text{low}[ v ] = \min \begin{cases} \text{disc}[ v ] \\ \text{disc}[ u ] & \text{对于每条后向边 } (v, u) \\ \text{low}[ c ] & \text{对于每个子节点 } c \text{ 的树边 } (v, c) \end{cases} \] 关节点的判定条件 （在 DFS 过程中）： 根节点 ：如果根在 DFS 树中有多于 1 个子节点（注意：是 DFS 树中的子节点，不是原图中度的大小），则根是关节点。 非根节点 \( v \)：如果存在一个子节点 \( u \) 满足 \( \text{low}[ u] \ge \text{disc}[ v ] \)，则 \( v \) 是关节点。 解释：条件 \( \text{low}[ u] \ge \text{disc}[ v ] \) 意味着以 \( u \) 为根的子树中，没有任何后向边能够“绕开” \( v \) 到达 \( v \) 的祖先，因此删除 \( v \) 后，\( u \) 所在的子树就会与图的其余部分断开。 3. 算法详细步骤 我们用递归 DFS 实现，同时用一个栈来处理双连通分量（本题只需求关节点，但 low 值的定义与双连通分量计算一致）。 初始化： 数组 \( \text{disc}[ v ] = 0 \) 表示未访问。 数组 \( \text{low}[ v ] \) 在访问时初始化。 数组 \( \text{parent}[ v ] \) 记录 DFS 树中的父节点。 全局变量 \( \text{time} = 0 \) 用于时间戳。 列表 \( \text{articulationPoints} \) 存储结果。 递归函数 \( \text{DFS}(v) \)： 设置 \( \text{disc}[ v] = \text{low}[ v ] = ++\text{time} \)。 初始化子节点计数 \( \text{children} = 0 \)。 对于 \( v \) 的每个邻居 \( u \)： 如果 \( u \) 未被访问（即 \( \text{disc}[ u ] == 0 \)）： 设置 \( \text{parent}[ u ] = v \)。 \( \text{children} = \text{children} + 1 \)。 递归调用 \( \text{DFS}(u) \)。 递归返回后，更新 \( \text{low}[ v] = \min(\text{low}[ v], \text{low}[ u ]) \)。 关节点检查 ： 如果 \( v \) 不是根（即 \( \text{parent}[ v] \neq -1 \)）且 \( \text{low}[ u] \ge \text{disc}[ v ] \)，则 \( v \) 是关节点。 否则如果 \( u \) 不是 \( v \) 的父节点（即已访问且 \( u \neq \text{parent}[ v ] \)）： 这是一条后向边（指向祖先或兄弟），更新 \( \text{low}[ v] = \min(\text{low}[ v], \text{disc}[ u ]) \)。 在递归返回后，检查根节点：如果 \( v \) 是根（即 \( \text{parent}[ v ] == -1 \)）且 \( \text{children} \ge 2 \)，则 \( v \) 是关节点。 注意 ：为了避免将父节点误认为后向边，我们需判断 \( u \neq \text{parent}[ v ] \)。 4. 举例说明 考虑一个简单无向图： 顶点：0, 1, 2, 3, 4 边：(0,1), (1,2), (2,0), (1,3), (3,4) 我们从顶点 0 开始 DFS： 访问 0（disc=1, low=1），邻居 1 未访问，递归到 1。 访问 1（disc=2, low=2），邻居 0 已访问但为父节点，忽略；邻居 2 未访问，递归到 2。 访问 2（disc=3, low=3），邻居 0 已访问且不是父节点（0 是祖先），后向边，更新 low[ 2] = min(3, disc[ 0]=1) = 1；邻居 1 已访问且是父节点，忽略。返回时，low[ 1] = min(2, low[ 2 ]=1) = 1。 回到 1，邻居 3 未访问，递归到 3。 访问 3（disc=4, low=4），邻居 1 是父节点，忽略；邻居 4 未访问，递归到 4。 访问 4（disc=5, low=5），邻居 3 是父节点，忽略。返回时，检查 4 无其他邻居，返回 3。 在 3 处，子节点 4 的 low[ 4]=5，检查 low[ 4] >= disc[ 3 ]? 5 >= 4 成立，因此 3 是关节点。 回到 1，检查子节点 2 的 low[ 2]=1，low[ 2] < disc[ 1] 不成立，所以此时不标记 1；子节点 3 的 low[ 3]=4，low[ 3] >= disc[ 1 ]? 4 >= 2 成立，因此 1 是关节点。 最后检查根节点 0：children = 1（只有 1 一个子节点），所以 0 不是关节点。 结果：关节点是 1 和 3。 5. 算法复杂度分析 时间复杂度：\( O(n + m) \)，因为每个顶点和边只被访问常数次（标准 DFS）。 空间复杂度：\( O(n) \) 用于存储 disc、low、parent 数组以及递归栈。 6. 注意事项与边界情况 图可能不连通：需要对每个未访问的顶点作为根分别进行 DFS。 自环与重边：自环不影响关节点判定（因为自环不算后向边）；重边在无向图中通常作为两条相同的边，但算法中处理时，如果遇到一条边 (v,u) 且 u 是父节点，忽略它，但若还有另一条 (v,u)，则这条重边应视为后向边（因为 u 已被访问且不是当前递归的父节点？实际上在无向图中，每条边会被遍历两次，所以第一次是树边，第二次时 u 是父节点，应忽略。但若存在多条平行边，则需要额外处理，通常可记录访问次数或对邻接表去重）。 实践中，我们通常在无向图中忽略指向父节点的边即可正确处理。 7. 总结 本算法是 Tarjan 基于 DFS 的经典应用，一次 DFS 即可求出所有关节点，高效且易于实现。掌握这个算法不仅能够解决关节点检测，也为学习双连通分量、桥检测等更深入的图论问题打下基础。