Tarjan算法求无向图的割点（Articulation Points）

字数 1083 2025-10-30 21:15:36

Tarjan算法求无向图的割点（Articulation Points）

题目描述
给定一个无向连通图，找出所有的割点（Articulation Points）。割点是指删除该顶点及其关联边后，图不再连通（即连通分量数量增加）的顶点。例如，在计算机网络中，割点可能代表关键节点，其故障会导致网络分裂。

解题过程
Tarjan算法通过深度优先搜索（DFS）遍历图，利用以下关键变量判断割点：

disc[u]：顶点u在DFS中被访问的时间（发现时间）。
low[u]：从u出发通过DFS树边和后向边能到达的最小disc值（包括自身）。
核心思想：若顶点u不是根节点，且存在子节点v满足low[v] >= disc[u]，则u是割点（因为v无法绕过u访问更早的祖先）。对于根节点，需至少两个子节点才为割点。

步骤详解

初始化
- 全局计时器time = 0，记录DFS访问顺序。
- 数组disc[]和low[]初始化为-1（未访问）。
- 数组parent[]记录DFS树中的父节点。
- 布尔数组ap[]标记割点。
DFS遍历
从任意顶点开始DFS。对于当前顶点u：
- 设置disc[u] = low[u] = ++time。
- 统计子节点数children（仅对根节点判断割点时需要）。
- 遍历u的每个邻居v：
  - 若v未访问（disc[v] == -1）：
    - 设置parent[v] = u，递归处理v。
    - 回溯后更新low[u] = min(low[u], low[v])。
    - 割点判断：
      - 如果u是根节点且children >= 2，则u是割点。
      - 如果u非根节点且low[v] >= disc[u]，则u是割点。
  - 若v已访问且v != parent[u]（避免直接父节点），说明(u, v)是后向边，更新low[u] = min(low[u], disc[v])。
复杂度分析
- 时间复杂度：O(V + E)，每个顶点和边仅处理一次。
- 空间复杂度：O(V)，存储DFS栈和数组。

示例
考虑无向图：

0 — 1 — 2
| /     |
3       4

从顶点0开始DFS：

顶点1的子节点2满足low[2] >= disc[1]，故顶点1是割点。
顶点0是根节点，但仅有一个子节点（顶点1），不是割点。
最终割点为顶点1。

关键点

后向边更新low[u]时使用disc[v]（非low[v]），确保不跨过后向边指向的祖先。
根节点的割点判断独立于low值，仅依赖子节点数。

Tarjan算法求无向图的割点（Articulation Points）题目描述给定一个无向连通图，找出所有的割点（Articulation Points）。割点是指删除该顶点及其关联边后，图不再连通（即连通分量数量增加）的顶点。例如，在计算机网络中，割点可能代表关键节点，其故障会导致网络分裂。解题过程 Tarjan算法通过深度优先搜索（DFS）遍历图，利用以下关键变量判断割点： disc[u] ：顶点 u 在DFS中被访问的时间（发现时间）。 low[u] ：从 u 出发通过DFS树边和后向边能到达的最小 disc 值（包括自身）。核心思想：若顶点 u 不是根节点，且存在子节点 v 满足 low[v] >= disc[u] ，则 u 是割点（因为 v 无法绕过 u 访问更早的祖先）。对于根节点，需至少两个子节点才为割点。步骤详解初始化全局计时器 time = 0 ，记录DFS访问顺序。数组 disc[] 和 low[] 初始化为 -1 （未访问）。数组 parent[] 记录DFS树中的父节点。布尔数组 ap[] 标记割点。 DFS遍历从任意顶点开始DFS。对于当前顶点 u ：设置 disc[u] = low[u] = ++time 。统计子节点数 children （仅对根节点判断割点时需要）。遍历 u 的每个邻居 v ：若 v 未访问（ disc[v] == -1 ）：设置 parent[v] = u ，递归处理 v 。回溯后更新 low[u] = min(low[u], low[v]) 。割点判断：如果 u 是根节点且 children >= 2 ，则 u 是割点。如果 u 非根节点且 low[v] >= disc[u] ，则 u 是割点。若 v 已访问且 v != parent[u] （避免直接父节点），说明 (u, v) 是后向边，更新 low[u] = min(low[u], disc[v]) 。复杂度分析时间复杂度：O(V + E)，每个顶点和边仅处理一次。空间复杂度：O(V)，存储DFS栈和数组。示例考虑无向图：从顶点0开始DFS：顶点1的子节点2满足 low[2] >= disc[1] ，故顶点1是割点。顶点0是根节点，但仅有一个子节点（顶点1），不是割点。最终割点为顶点1。关键点后向边更新 low[u] 时使用 disc[v] （非 low[v] ），确保不跨过后向边指向的祖先。根节点的割点判断独立于 low 值，仅依赖子节点数。