Tarjan算法求无向图的割点（Articulation Points）
字数 1241 2025-10-29 11:31:55

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

题目描述
给定一个无向连通图，找出所有的割点。割点是指删除该顶点及其关联边后，图不再连通（即连通分量数量增加）的顶点。例如，在通信网络中，割点代表关键节点，其失效会导致网络分裂。要求高效地找出所有割点。

解题过程

1. 核心思想
割点的判定依赖于深度优先搜索（DFS）遍历。通过DFS记录每个顶点的访问顺序（发现时间）和一个关键值（low值），low值表示该顶点能通过回溯边到达的最早祖先节点。若某个顶点满足特定条件，它就是一个割点。

关键定义：

  • disc[u]：顶点u在DFS中被访问的时间（发现时间）。
  • low[u]：顶点u通过DFS树中的子树能回溯到的最早祖先的disc值（通过后向边）。
  • 割点条件：
    • 根节点：若DFS树中有至少两个子树，则根是割点。
    • 非根节点u：存在一个子节点v，使得low[v] >= disc[u]（即v无法绕过u到达更早的祖先）。

2. 算法步骤

  • 步骤1：初始化

    • 使用DFS遍历图，维护全局时间戳time。
    • 数组disc[]和low[]初始化为-1（未访问），parent[]记录DFS树中的父节点。

  • 步骤2：DFS递归过程
    对当前顶点u：

    1. 记录disc[u] = low[u] = ++time。
    2. 遍历u的每个邻居v：
      • 若v未访问（disc[v] == -1）：
        • 设置parent[v] = u，递归处理v。
        • 回溯时更新：low[u] = min(low[u], low[v])。
        • 割点检查：
          • 若u是根且有至少两个子节点（通过递归调用次数判断），则标记u为割点。
          • 若u非根且low[v] >= disc[u]，标记u为割点。
      • 若v已访问且v不是u的父节点（处理回边）：
        low[u] = min(low[u], disc[v])（通过回边直接回溯）。

  • 步骤3：输出所有标记为割点的顶点。

3. 举例说明
考虑图：顶点0-1-2构成链，额外边1-3。

0 — 1 — 2
    |
    3
  • DFS从0开始：
    • 访问0（disc=0），子节点1未访问，递归到1。
    • 1访问（disc=1），子节点0已访问（父节点），子节点2未访问，递归到2。
    • 2访问（disc=2），邻居1已访问（父节点），回溯更新low[2]=2。因low[2]=2 >= disc[1]=1，1是割点。
    • 1继续处理子节点3，递归到3（disc=3），回溯更新low[3]=3，low[1]=min(1,3)=1。
  • 根节点0只有一个子节点1，不是割点。
  • 结果：割点为顶点1。

4. 时间复杂度

  • DFS遍历所有顶点和边，时间复杂度为O(V+E)，适用于大规模图。

5. 关键点总结

  • 利用DFS树的结构和回溯机制，通过low值判断连通性依赖。
  • 根节点需单独处理（子节点数≥2）。
  • 回边更新low值时用disc[v]而非low[v]（因为回边直接连接祖先）。
Tarjan算法求无向图的割点（Articulation Points） 题目描述 给定一个无向连通图，找出所有的割点。割点是指删除该顶点及其关联边后，图不再连通（即连通分量数量增加）的顶点。例如，在通信网络中，割点代表关键节点，其失效会导致网络分裂。要求高效地找出所有割点。 解题过程 1. 核心思想 割点的判定依赖于深度优先搜索（DFS）遍历。通过DFS记录每个顶点的访问顺序（发现时间）和一个关键值（low值），low值表示该顶点能通过回溯边到达的最早祖先节点。若某个顶点满足特定条件，它就是一个割点。 关键定义 ： disc[u] ：顶点u在DFS中被访问的时间（发现时间）。 low[u] ：顶点u通过DFS树中的子树能回溯到的最早祖先的 disc 值（通过后向边）。 割点条件 ： 根节点：若DFS树中有至少两个子树，则根是割点。 非根节点u：存在一个子节点v，使得 low[v] >= disc[u] （即v无法绕过u到达更早的祖先）。 2. 算法步骤 步骤1 ：初始化 使用DFS遍历图，维护全局时间戳 time 。 数组 disc[] 和 low[] 初始化为-1（未访问）， parent[] 记录DFS树中的父节点。 步骤2 ：DFS递归过程 对当前顶点u： 记录 disc[u] = low[u] = ++time 。 遍历u的每个邻居v： 若v未访问（ disc[v] == -1 ）： 设置 parent[v] = u ，递归处理v。 回溯时更新： low[u] = min(low[u], low[v]) 。 割点检查 ： 若u是根且有至少两个子节点（通过递归调用次数判断），则标记u为割点。 若u非根且 low[v] >= disc[u] ，标记u为割点。 若v已访问且v不是u的父节点（处理回边）： low[u] = min(low[u], disc[v]) （通过回边直接回溯）。 步骤3 ：输出所有标记为割点的顶点。 3. 举例说明 考虑图：顶点0-1-2构成链，额外边1-3。 DFS从0开始： 访问0（disc=0），子节点1未访问，递归到1。 1访问（disc=1），子节点0已访问（父节点），子节点2未访问，递归到2。 2访问（disc=2），邻居1已访问（父节点），回溯更新low[ 2]=2。因low[ 2]=2 >= disc[ 1 ]=1，1是割点。 1继续处理子节点3，递归到3（disc=3），回溯更新low[ 3]=3，low[ 1 ]=min(1,3)=1。 根节点0只有一个子节点1，不是割点。 结果：割点为顶点1。 4. 时间复杂度 DFS遍历所有顶点和边，时间复杂度为O(V+E)，适用于大规模图。 5. 关键点总结 利用DFS树的结构和回溯机制，通过 low 值判断连通性依赖。 根节点需单独处理（子节点数≥2）。 回边更新 low 值时用 disc[v] 而非 low[v] （因为回边直接连接祖先）。