Tarjan 算法求无向图的桥（Bridges）
字数 2628 2025-12-21 06:05:06

Tarjan 算法求无向图的桥（Bridges）

算法描述

给定一个无向连通图，一条边被称为“桥”（也称为割边），如果移除这条边后，图会变得不再连通。Tarjan 算法能够在 O(V+E) 时间内找出图中的所有桥。算法的核心是基于深度优先搜索（DFS），并维护两个关键的时间戳数组：dfn[u]（顶点 u 的 DFS 访问序号）和 low[u]（从 u 出发，通过其子树中的边以及最多一条非树边（回边）能访问到的最早的祖先顶点的 dfn 值）。

解题步骤详解

  1. 基础概念准备

    • 桥的定义：在无向图中，如果删除边 (u, v) 后，图的连通分量数目增加，则 (u, v) 是一条桥。
    • DFS 生成树：从任意顶点开始进行 DFS 遍历，遍历过程中经过的边构成一棵生成树，称为 DFS 树。剩下的边（图中存在但不在 DFS 树中）称为回边（back edge），回边连接一个顶点与其在 DFS 树中的祖先。
    • 关键思想：在 DFS 树中，一条树边 (u, v)（u 是 v 的父节点）是桥，当且仅当无法通过 v 及其子树中的任何边到达 u 或 u 的祖先。用 low 值来形式化这一条件。

  2. 算法核心：dfn 与 low 数组

    • dfn[u]：顶点 u 在 DFS 中被访问的顺序编号（时间戳）。每个顶点只被赋予一次，且严格递增。
    • low[u]：初始值为 dfn[u]。在 DFS 过程中，low[u] 会被更新为以下值中的最小值：
      a) dfn[u] 自身。
      b) 所有从 u 出发的树边 (u, v) 中，low[v] 的值（即通过子树能回溯到的最早祖先）。
      c) 所有从 u 出发的回边 (u, w) 中，dfn[w] 的值（w 必须是 u 在 DFS 树中的祖先，且不是父节点，因为无向图每条边会被遍历两次，需避免直接认为回边指向父节点的情况）。
    • 更新 low[u] 的公式：low[u] = min(low[u], low[v])（对于树边 (u, v)）；low[u] = min(low[u], dfn[w])（对于回边 (u, w)）。

  3. 判断桥的条件

    • 对于一条 DFS 树边 (u, v)（其中 u 是 v 的父节点）：
      • 如果 low[v] > dfn[u]，则 (u, v) 是一条桥。
      • 解释：low[v] > dfn[u] 意味着从 v 及其子树出发，无法通过任何回边到达 u 或 u 的祖先（因为能到达的最早顶点时间戳大于 dfn[u]）。因此，删除边 (u, v) 后，v 及其子树与图的其余部分断开，图不再连通。
      • 如果 low[v] ≤ dfn[u]，则说明从 v 的子树中至少有一条边能绕回到 u 或 u 的祖先，那么 (u, v) 就不是桥。

  4. 算法步骤

    • 初始化：时间戳 time = 0，数组 dfn[] 全为 -1（表示未访问），low[] 未定义。准备一个空列表 bridges 存储结果。
    • 从图中任意未访问顶点开始进行 DFS（对每个连通分量都需进行，因为图可能不连通）。
    • 在 DFS 函数 dfs(u, parent) 中：
      1. 设置 dfn[u] = low[u] = ++time。
      2. 遍历 u 的所有邻接顶点 v：
        • 如果 v 未被访问（dfn[v] == -1）：
          • 递归调用 dfs(v, u)。
          • 递归返回后，更新 low[u] = min(low[u], low[v])。
          • 检查桥的条件：如果 low[v] > dfn[u]，则将边 (u, v) 加入 bridges。
        • 否则，如果 v 已被访问且 v ≠ parent（避免将 (u, parent) 这条刚刚来的树边误判为回边）：
          • 此时 (u, v) 是一条回边（或平行边）。更新 low[u] = min(low[u], dfn[v])。
    • 最终，bridges 中存储的就是图中所有的桥。

  5. 为什么需要 v ≠ parent 的条件？

    • 在无向图的 DFS 中，每条边 (u, v) 会被遍历两次：一次作为树边（比如 u → v），一次作为从 v 到 u 的边。当我们在处理 u 的邻接点时，如果遇到 v 恰好是 u 的父节点（即刚刚从 parent 来到 u），那么这条边是树边的反向边，不是回边，不应该用来更新 low[u]。忽略它才能正确应用桥的判断条件。

  6. 示例演示
    考虑一个简单无向图：顶点 0, 1, 2，边为 (0,1), (1,2), (0,2)。

    • DFS 从 0 开始，假设遍历顺序为 0→1→2。
    • 树边： (0,1), (1,2)。回边：从 2 到 0（因为 0 是祖先）。
    • 计算 low：
      • low[2] = min(dfn[2]=3, dfn[0]=1) = 1。
      • low[1] = min(dfn[1]=2, low[2]=1) = 1。
      • low[0] = min(dfn[0]=1, low[1]=1) = 1。
    • 判断树边：
      • (1,2): low[2]=1, dfn[1]=2，low[2] ≤ dfn[1]，不是桥。
      • (0,1): low[1]=1, dfn[0]=1，low[1] ≤ dfn[0]，不是桥。
    • 结果：该图没有桥。确实，删除任何一条边，图依然连通。

  7. 算法复杂度

    • 时间复杂度：O(V+E)，因为算法本质是 DFS 遍历所有顶点和边，每个顶点和边只处理常数次。
    • 空间复杂度：O(V)，用于存储 dfn、low 数组和 DFS 递归栈。

  8. 注意点

    • 算法假设图是无向的。对于有向图，桥的定义和算法都不同。
    • 如果图不连通，需要对每个连通分量分别运行算法。
    • 平行边（重边）的处理：如果存在多条边连接同一对顶点，那么这些边都不会是桥（因为删除一条，另一条仍保持连通）。算法中，当遇到已访问的邻居 v 且 v ≠ parent 时，我们用 dfn[v]（而不是 low[v]）更新 low[u]，这能正确处理平行边（因为对于平行边，dfn[v] 不会大于 dfn[u]，所以 low[v] 不会大于 dfn[u]，边不会被误判为桥）。

通过以上步骤，Tarjan 算法可以高效、准确地找出无向图中的所有桥。

Tarjan 算法求无向图的桥（Bridges） 算法描述 给定一个 无向连通图 ，一条边被称为“桥”（也称为割边），如果移除这条边后，图会变得不再连通。Tarjan 算法能够在 O(V+E) 时间内找出图中的所有桥。算法的核心是基于深度优先搜索（DFS），并维护两个关键的时间戳数组： dfn[u] （顶点 u 的 DFS 访问序号）和 low[u] （从 u 出发，通过其子树中的边以及 最多一条 非树边（回边）能访问到的最早的祖先顶点的 dfn 值）。 解题步骤详解 基础概念准备 桥的定义 ：在无向图中，如果删除边 (u, v) 后，图的连通分量数目增加，则 (u, v) 是一条桥。 DFS 生成树 ：从任意顶点开始进行 DFS 遍历，遍历过程中经过的边构成一棵生成树，称为 DFS 树。剩下的边（图中存在但不在 DFS 树中）称为 回边 （back edge），回边连接一个顶点与其在 DFS 树中的祖先。 关键思想：在 DFS 树中，一条树边 (u, v)（u 是 v 的父节点）是桥，当且仅当 无法通过 v 及其子树中的任何边 到达 u 或 u 的祖先。用 low 值来形式化这一条件。 算法核心：dfn 与 low 数组 dfn[u] ：顶点 u 在 DFS 中被访问的顺序编号（时间戳）。每个顶点只被赋予一次，且严格递增。 low[u] ：初始值为 dfn[u] 。在 DFS 过程中， low[u] 会被更新为以下值中的最小值： a) dfn[u] 自身。 b) 所有从 u 出发的树边 (u, v) 中， low[v] 的值（即通过子树能回溯到的最早祖先）。 c) 所有从 u 出发的回边 (u, w) 中， dfn[w] 的值（w 必须是 u 在 DFS 树中的祖先，且不是父节点，因为无向图每条边会被遍历两次，需避免直接认为回边指向父节点的情况）。 更新 low[u] 的公式： low[u] = min(low[u], low[v]) （对于树边 (u, v)）； low[u] = min(low[u], dfn[w]) （对于回边 (u, w)）。 判断桥的条件 对于一条 DFS 树边 (u, v)（其中 u 是 v 的父节点）： 如果 low[v] > dfn[u] ，则 (u, v) 是一条桥。 解释： low[v] > dfn[u] 意味着从 v 及其子树出发， 无法通过任何回边 到达 u 或 u 的祖先（因为能到达的最早顶点时间戳大于 dfn[u] ）。因此，删除边 (u, v) 后，v 及其子树与图的其余部分断开，图不再连通。 如果 low[v] ≤ dfn[u] ，则说明从 v 的子树中至少有一条边能绕回到 u 或 u 的祖先，那么 (u, v) 就不是桥。 算法步骤 初始化：时间戳 time = 0 ，数组 dfn[] 全为 -1（表示未访问）， low[] 未定义。准备一个空列表 bridges 存储结果。 从图中任意未访问顶点开始进行 DFS（对每个连通分量都需进行，因为图可能不连通）。 在 DFS 函数 dfs(u, parent) 中： 设置 dfn[u] = low[u] = ++time 。 遍历 u 的所有邻接顶点 v： 如果 v 未被访问 （ dfn[v] == -1 ）： 递归调用 dfs(v, u) 。 递归返回后，更新 low[u] = min(low[u], low[v]) 。 检查桥的条件：如果 low[v] > dfn[u] ，则将边 (u, v) 加入 bridges 。 否则，如果 v 已被访问 且 v ≠ parent （避免将 (u, parent) 这条刚刚来的树边误判为回边）： 此时 (u, v) 是一条回边（或平行边）。更新 low[u] = min(low[u], dfn[v]) 。 最终， bridges 中存储的就是图中所有的桥。 为什么需要 v ≠ parent 的条件？ 在无向图的 DFS 中，每条边 (u, v) 会被遍历两次：一次作为树边（比如 u → v），一次作为从 v 到 u 的边。当我们在处理 u 的邻接点时，如果遇到 v 恰好是 u 的父节点（即刚刚从 parent 来到 u），那么这条边是树边的反向边， 不是回边 ，不应该用来更新 low[u] 。忽略它才能正确应用桥的判断条件。 示例演示 考虑一个简单无向图：顶点 0, 1, 2，边为 (0,1), (1,2), (0,2)。 DFS 从 0 开始，假设遍历顺序为 0→1→2。 树边： (0,1), (1,2)。回边：从 2 到 0（因为 0 是祖先）。 计算 low ： low[2] = min(dfn[2]=3, dfn[0]=1) = 1 。 low[1] = min(dfn[1]=2, low[2]=1) = 1 。 low[0] = min(dfn[0]=1, low[1]=1) = 1 。 判断树边： (1,2): low[2]=1 , dfn[1]=2 ， low[2] ≤ dfn[1] ，不是桥。 (0,1): low[1]=1 , dfn[0]=1 ， low[1] ≤ dfn[0] ，不是桥。 结果：该图没有桥。确实，删除任何一条边，图依然连通。 算法复杂度 时间复杂度：O(V+E)，因为算法本质是 DFS 遍历所有顶点和边，每个顶点和边只处理常数次。 空间复杂度：O(V)，用于存储 dfn 、 low 数组和 DFS 递归栈。 注意点 算法假设图是无向的。对于有向图，桥的定义和算法都不同。 如果图不连通，需要对每个连通分量分别运行算法。 平行边（重边）的处理：如果存在多条边连接同一对顶点，那么这些边 都不会是桥 （因为删除一条，另一条仍保持连通）。算法中，当遇到已访问的邻居 v 且 v ≠ parent 时，我们用 dfn[v] （而不是 low[v] ）更新 low[u] ，这能正确处理平行边（因为对于平行边， dfn[v] 不会大于 dfn[u] ，所以 low[v] 不会大于 dfn[u] ，边不会被误判为桥）。 通过以上步骤，Tarjan 算法可以高效、准确地找出无向图中的所有桥。