xxx 寻找割点（Articulation Points）问题

字数 2622 2025-10-28 00:29:09

xxx 寻找割点（Articulation Points）问题

题目描述：
在一个无向连通图中，如果删除某个顶点及其相关联的边后，图不再连通（即被分割成两个或更多个连通分量），那么这个顶点就被称为图的“割点”或“关节点”。我们的目标是找出给定无向连通图中的所有割点。

解题过程：

核心思路与深度优先搜索（DFS）
解决这个问题最经典的方法是使用深度优先搜索（DFS）。单纯的DFS可以遍历图，但我们需要在DFS遍历的过程中记录额外的信息，以便判断一个顶点是否是割点。
关键概念：发现时间与低链接值
为了进行判断，我们需要为每个顶点 u 维护两个重要的值：
- disc[u]（发现时间）：在DFS过程中，顶点 u 第一次被访问到的时间（顺序编号）。我们可以用一个全局变量 time 来记录这个顺序。
- low[u]（低链接值）：low[u] 定义为以下值中的最小值：
  1. u 自身的发现时间 disc[u]。
  2. 所有与 u 在DFS树中相邻的后继顶点 v 的 low[v] 值（即，通过 u 的孩子顶点能回溯到的最早的祖先）。
  3. 所有与 u 相连、但不是 u 在DFS树中父节点的顶点 w 的 disc[w] 值（即，通过一条回边能连接到的祖先的发现时间）。
low[u] 的核心意义是：从顶点 u 出发，不通过其DFS树中的父节点，所能连接到的“最早”（发现时间最小）的祖先顶点。
判断割点的规则
在DFS遍历的过程中，我们可以根据当前顶点 u 和其邻接顶点 v 的关系，应用以下规则来判断 u 是否为割点：
- 情况一：u 是DFS树的根节点。
  如果根节点在DFS树中有两个或更多的孩子（子树），那么删除根节点后，这些子树之间将无法连通，因此根节点是割点。
- 情况二：u 不是DFS树的根节点。
  如果存在一个子节点 v，使得 low[v] >= disc[u]，那么 u 就是一个割点。
  - 理解：low[v] >= disc[u] 意味着，顶点 v 以及它的所有后代，都无法通过任何一条除了经过 u 之外的路径，到达 u 的祖先（发现时间比 u 更早的顶点）。因此，如果删除 u，v 所在的子树就会与图的其余部分断开，导致图不再连通。
算法步骤详解
我们以一个图为例，逐步执行算法。假设图如下（顶点为A, B, C, D, E，边为 (A,B), (A,C), (B,C), (B,D), (D,E)）：
```
    A
   / \
  B — C
  |
  D
  |
  E
```
我们从顶点A开始DFS。
- 初始化：创建一个 disc 数组、一个 low 数组、一个 parent 数组（记录DFS树中的父节点），并将所有值初始化为-1（未访问）。设置全局时间 time = 0。
- 访问A（根节点）：
  - disc[A] = low[A] = time = 0。
  - parent[A] = -1（A是根节点）。
  - 检查A的邻接点B和C。假设先访问B。
- 访问B（A的孩子）：
  - disc[B] = low[B] = time = 1。
  - parent[B] = A。
  - 检查B的邻接点：A, C, D。
    - A是B的父节点，忽略。
    - 访问C。
- 访问C（B的孩子）：
  - disc[C] = low[C] = time = 2。
  - parent[C] = B。
  - 检查C的邻接点：A, B。
    - A不是C的父节点，且A已被访问。这是一条回边。我们用这条回边更新C的 low 值：low[C] = min(low[C], disc[A]) = min(2, 0) = 0。
    - B是C的父节点，忽略。
  - C处理完毕，返回B。B收到来自C的信息，更新自己的 low 值：low[B] = min(low[B], low[C]) = min(1, 0) = 0。
- B继续处理：
  - 检查下一个邻接点D。访问D。
- 访问D（B的孩子）：
  - disc[D] = low[D] = time = 3。
  - parent[D] = B。
  - 检查D的邻接点：B, E。
    - B是父节点，忽略。
    - 访问E。
- 访问E（D的孩子）：
  - disc[E] = low[E] = time = 4。
  - parent[E] = D。
  - 检查E的邻接点：D（父节点），忽略。
  - E处理完毕，返回D。D收到来自E的信息，更新 low[D] = min(low[D], low[E]) = min(3, 4) = 3。（此时E的 low 值等于其 disc 值，因为没有回边）。
- D处理完毕，返回B：
  - B收到来自D的信息，更新 low[B] = min(low[B], low[D]) = min(0, 3) = 0。
- B处理完毕，返回A：
  - A收到来自B的信息，更新 low[A] = min(low[A], low[B]) = min(0, 0) = 0。
- A继续处理：
  - 检查下一个邻接点C。
  - C已经被访问过，且C不是A在DFS树中的孩子（A的孩子是B，C是B的孩子），所以这是一条回边。我们用这条回边更新A的 low 值：low[A] = min(low[A], disc[C]) = min(0, 2) = 0。
- A处理完毕。
应用规则判断割点
- 顶点A（根节点）：在DFS树中，A只有一个孩子（B）。不满足“两个或更多孩子”的条件，所以A不是割点。
- 顶点B（非根节点）：检查B的孩子。
  - 对于孩子C：low[C] = 0，disc[B] = 1。low[C] (0) < disc[B] (1)，条件不成立。
  - 对于孩子D：low[D] = 3，disc[B] = 1。low[D] (3) >= disc[B] (1)，条件成立。因此，B是割点。
- 顶点D（非根节点）：检查D的孩子E：low[E] = 4，disc[D] = 3。low[E] (4) >= disc[D] (3)，条件成立。因此，D是割点。
- 顶点C和E没有孩子，不可能是割点。
结论：该图的割点是B和D。

通过这个循序渐进的DFS过程，并利用发现时间和低链接值，我们就能系统性地找出图中所有的割点。这个算法的时间复杂度是O(V+E)，其中V是顶点数，E是边数。

xxx 寻找割点（Articulation Points）问题题目描述：在一个无向连通图中，如果删除某个顶点及其相关联的边后，图不再连通（即被分割成两个或更多个连通分量），那么这个顶点就被称为图的“割点”或“关节点”。我们的目标是找出给定无向连通图中的所有割点。解题过程：核心思路与深度优先搜索（DFS）解决这个问题最经典的方法是使用深度优先搜索（DFS）。单纯的DFS可以遍历图，但我们需要在DFS遍历的过程中记录额外的信息，以便判断一个顶点是否是割点。关键概念：发现时间与低链接值为了进行判断，我们需要为每个顶点 u 维护两个重要的值： disc[u] （发现时间）：在DFS过程中，顶点 u 第一次被访问到的时间（顺序编号）。我们可以用一个全局变量 time 来记录这个顺序。 low[u] （低链接值）： low[u] 定义为以下值中的最小值： u 自身的发现时间 disc[u] 。所有与 u 在DFS树中相邻的后继顶点 v 的 low[v] 值（即，通过 u 的孩子顶点能回溯到的最早的祖先）。所有与 u 相连、但不是 u 在DFS树中父节点的顶点 w 的 disc[w] 值（即，通过一条回边能连接到的祖先的发现时间）。 low[u] 的核心意义是：从顶点 u 出发，不通过其DFS树中的父节点，所能连接到的“最早”（发现时间最小）的祖先顶点。判断割点的规则在DFS遍历的过程中，我们可以根据当前顶点 u 和其邻接顶点 v 的关系，应用以下规则来判断 u 是否为割点：情况一： u 是DFS树的根节点。如果根节点在DFS树中有两个或更多的孩子（子树），那么删除根节点后，这些子树之间将无法连通，因此根节点是割点。情况二： u 不是DFS树的根节点。如果存在一个子节点 v ，使得 low[v] >= disc[u] ，那么 u 就是一个割点。理解： low[v] >= disc[u] 意味着，顶点 v 以及它的所有后代，都无法通过任何一条除了经过 u 之外的路径，到达 u 的祖先（发现时间比 u 更早的顶点）。因此，如果删除 u ， v 所在的子树就会与图的其余部分断开，导致图不再连通。算法步骤详解我们以一个图为例，逐步执行算法。假设图如下（顶点为A, B, C, D, E，边为 (A,B), (A,C), (B,C), (B,D), (D,E)）：我们从顶点A开始DFS。初始化：创建一个 disc 数组、一个 low 数组、一个 parent 数组（记录DFS树中的父节点），并将所有值初始化为-1（未访问）。设置全局时间 time = 0 。访问A（根节点）： disc[A] = low[A] = time = 0 。 parent[A] = -1 （A是根节点）。检查A的邻接点B和C。假设先访问B。访问B（A的孩子）： disc[B] = low[B] = time = 1 。 parent[B] = A 。检查B的邻接点：A, C, D。 A是B的父节点，忽略。访问C。访问C（B的孩子）： disc[C] = low[C] = time = 2 。 parent[C] = B 。检查C的邻接点：A, B。 A不是C的父节点，且A已被访问。这是一条回边。我们用这条回边更新C的 low 值： low[C] = min(low[C], disc[A]) = min(2, 0) = 0 。 B是C的父节点，忽略。 C处理完毕，返回B。B收到来自C的信息，更新自己的 low 值： low[B] = min(low[B], low[C]) = min(1, 0) = 0 。 B继续处理：检查下一个邻接点D。访问D。访问D（B的孩子）： disc[D] = low[D] = time = 3 。 parent[D] = B 。检查D的邻接点：B, E。 B是父节点，忽略。访问E。访问E（D的孩子）： disc[E] = low[E] = time = 4 。 parent[E] = D 。检查E的邻接点：D（父节点），忽略。 E处理完毕，返回D。D收到来自E的信息，更新 low[D] = min(low[D], low[E]) = min(3, 4) = 3 。（此时E的 low 值等于其 disc 值，因为没有回边）。 D处理完毕，返回B ： B收到来自D的信息，更新 low[B] = min(low[B], low[D]) = min(0, 3) = 0 。 B处理完毕，返回A ： A收到来自B的信息，更新 low[A] = min(low[A], low[B]) = min(0, 0) = 0 。 A继续处理：检查下一个邻接点C。 C已经被访问过，且C不是A在DFS树中的孩子（A的孩子是B，C是B的孩子），所以这是一条回边。我们用这条回边更新A的 low 值： low[A] = min(low[A], disc[C]) = min(0, 2) = 0 。 A处理完毕。应用规则判断割点顶点A（根节点）：在DFS树中，A只有一个孩子（B）。不满足“两个或更多孩子”的条件，所以A 不是割点。顶点B（非根节点）：检查B的孩子。对于孩子C： low[C] = 0 ， disc[B] = 1 。 low[C] (0) < disc[B] (1) ，条件不成立。对于孩子D： low[D] = 3 ， disc[B] = 1 。 low[D] (3) >= disc[B] (1) ，条件成立。因此，B是割点。顶点D（非根节点）：检查D的孩子E： low[E] = 4 ， disc[D] = 3 。 low[E] (4) >= disc[D] (3) ，条件成立。因此，D是割点。顶点C和E没有孩子，不可能是割点。结论：该图的割点是B和D。通过这个循序渐进的DFS过程，并利用发现时间和低链接值，我们就能系统性地找出图中所有的割点。这个算法的时间复杂度是O(V+E)，其中V是顶点数，E是边数。