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

字数 2715 2025-12-10 01:18:49

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

题目描述
给定一个无向连通图（可以是非连通的），图中有 $V$ 个顶点和 $E$ 条边。桥（也称为割边）是指这样一条边：如果删除这条边，会导致图的连通分量数量增加。也就是说，删除桥之后，原图会变得不再连通（或连通块数量增多）。
我们需要找出图中所有的桥。
例如，下图：

0---1---3
|  /    |
| /     |
2       4

其中，边 (1,3) 和 (3,4) 是桥，因为去掉其中任意一条，顶点 4 或 {0,1,2} 部分就会分离。
要求设计一个时间复杂度为 $O(V+E)$ 的算法。

解题过程
我们将使用 Tarjan 算法 的变种来寻找桥。与求割点的 Tarjan 算法类似，但判断条件有所不同。算法基于深度优先搜索（DFS），并记录每个顶点的两个关键值：

discovery time（发现时间，记作 disc[u]）：在 DFS 中第一次访问到顶点 $u$ 的时间戳。
lowest reachable ancestor（低连接值，记作 low[u]）：从 $u$ 出发，通过 DFS 树边以及最多一条后向边（即连接到祖先的非树边）所能到达的最早的祖先的发现时间。

核心思想：
在 DFS 树中，对于一条树边 $(u, v)$（其中 $u$ 是 $v$ 的父节点），如果 $v$ 及其后代无法通过任何后向边返回到 $u$ 或 $u$ 的祖先，那么边 $(u, v)$ 就是桥。用公式表示即：
如果 low[v] > disc[u]，则 $(u, v)$ 是桥。
如果 low[v] == disc[u] 或 low[v] < disc[u]，则 $v$ 可以绕到 $u$ 或更早的祖先，那么 $(u, v)$ 就不是桥。

步骤详解

步骤 1：初始化

用一个整数 time 记录 DFS 的访问顺序，初始为 0。
数组 disc[] 记录每个顶点的发现时间，初始化为 -1（表示未访问）。
数组 low[] 记录每个顶点的低连接值，初始化为 0。
数组 parent[] 记录 DFS 树中每个顶点的父节点，初始化为 -1。
用一个列表（或集合）存储找到的桥。

步骤 2：深度优先搜索（DFS）
从每个未访问的顶点开始 DFS（因为图可能不连通）。
在 DFS 函数 dfs(u) 中：

设置 disc[u] = low[u] = ++time。
遍历 $u$ 的所有邻接顶点 $v$：
- 如果 $v$ 未被访问过（disc[v] == -1）：
  - 设置 parent[v] = u。
  - 递归调用 dfs(v)。
  - 递归返回后，更新 low[u] = min(low[u], low[v])。
  - 检查桥的条件：如果 low[v] > disc[u]，则边 $(u, v)$ 是桥，加入结果集。
- 如果 $v$ 已被访问过，且 $v$ 不是 $u$ 的父节点（即这是一条后向边）：
  - 更新 low[u] = min(low[u], disc[v])。
    注意：这里比较的是 disc[v]，而不是 low[v]，因为一条后向边只能直接连到祖先，不能通过多条后向边跳转。

步骤 3：处理所有连通分量
对每个顶点，如果 disc[u] == -1，就调用 dfs(u)。最后输出所有找到的桥。

举例说明
考虑图：
顶点：0-1-2-0 形成一个环，再加一条边 2-3，3-4。
邻接表：
0: 1, 2
1: 0, 2
2: 0, 1, 3
3: 2, 4
4: 3

执行过程：

从顶点 0 开始 DFS。
- 访问顺序：disc[0]=1, low[0]=1。
- 访问邻居 1（未访问），递归进入 1。
  - disc[1]=2, low[1]=2。
  - 从 1 访问邻居 0（已访问，是父节点吗？父节点是 0，但这里 0 是父节点，跳过），访问邻居 2（未访问），递归进入 2。
    - disc[2]=3, low[2]=3。
    - 从 2 访问邻居 0（已访问，不是父节点 1），更新 low[2]=min(3, disc[0]=1) → low[2]=1。
    - 从 2 访问邻居 1（已访问，是父节点吗？父节点是 1，跳过）。
    - 从 2 访问邻居 3（未访问），递归进入 3。
      - disc[3]=4, low[3]=4。
      - 从 3 访问邻居 2（已访问，是父节点），跳过。
      - 从 3 访问邻居 4（未访问），递归进入 4。
        
        disc[4]=5, low[4]=5。
        
        从 4 访问邻居 3（已访问，是父节点），跳过。
        
        递归返回 3，更新 low[3]=min(4, low[4]=5) → low[3]=4。
        
        检查边 (3,4)：low[4]=5 > disc[3]=4 → 是桥，记录 (3,4)。
      - 递归返回 2，更新 low[2]=min(1, low[3]=4) → low[2]=1。
      - 检查边 (2,3)：low[3]=4 > disc[2]=3 → 是桥，记录 (2,3)。
    - 递归返回 1，更新 low[1]=min(2, low[2]=1) → low[1]=1。
    - 检查边 (1,2)：low[2]=1 > disc[1]=2？不成立（1>2 假），所以不是桥。
  - 递归返回 0，更新 low[0]=min(1, low[1]=1) → low[0]=1。
  - 检查边 (0,1)：low[1]=1 > disc[0]=1？不成立（1>1 假），不是桥。
- 从 0 访问邻居 2（已访问，不是父节点），更新 low[0]=min(1, disc[2]=3) → low[0]=1。

结果桥集：{(2,3), (3,4)}。
这与直观一致：去掉 (2,3) 或 (3,4) 都会增加连通块。

复杂度分析

时间复杂度：$O(V+E)$，因为每个顶点和边在 DFS 中只被访问常数次。
空间复杂度：$O(V)$，用于存储 disc、low、parent 数组和递归栈。

关键点总结

桥的判断条件是对于树边 $(u,v)$ 有 low[v] > disc[u]。
在更新 low[u] 时，对后向边用 disc[v] 更新。
需要处理不连通图，所以要从每个未访问的顶点开始 DFS。
这个算法是 Tarjan 算法在无向图桥检测上的经典应用，与求割点的区别在于判断条件（割点是 low[v] >= disc[u] 且需特殊处理根节点）。

Tarjan算法求无向图的桥（Bridges）问题题目描述给定一个无向连通图（可以是非连通的），图中有 $V$ 个顶点和 $E$ 条边。桥（也称为割边）是指这样一条边：如果删除这条边，会导致图的连通分量数量增加。也就是说，删除桥之后，原图会变得不再连通（或连通块数量增多）。我们需要找出图中所有的桥。例如，下图：其中，边 (1,3) 和 (3,4) 是桥，因为去掉其中任意一条，顶点 4 或 {0,1,2} 部分就会分离。要求设计一个时间复杂度为 $O(V+E)$ 的算法。解题过程我们将使用 Tarjan 算法的变种来寻找桥。与求割点的 Tarjan 算法类似，但判断条件有所不同。算法基于深度优先搜索（DFS），并记录每个顶点的两个关键值： discovery time （发现时间，记作 disc[u] ）：在 DFS 中第一次访问到顶点 $u$ 的时间戳。 lowest reachable ancestor （低连接值，记作 low[u] ）：从 $u$ 出发，通过 DFS 树边以及最多一条后向边（即连接到祖先的非树边）所能到达的最早的祖先的发现时间。核心思想：在 DFS 树中，对于一条树边 $(u, v)$（其中 $u$ 是 $v$ 的父节点），如果 $v$ 及其后代无法通过任何后向边返回到 $u$ 或 $u$ 的祖先，那么边 $(u, v)$ 就是桥。用公式表示即：如果 low[v] > disc[u] ，则 $(u, v)$ 是桥。如果 low[v] == disc[u] 或 low[v] < disc[u] ，则 $v$ 可以绕到 $u$ 或更早的祖先，那么 $(u, v)$ 就不是桥。步骤详解步骤 1：初始化用一个整数 time 记录 DFS 的访问顺序，初始为 0。数组 disc[] 记录每个顶点的发现时间，初始化为 -1（表示未访问）。数组 low[] 记录每个顶点的低连接值，初始化为 0。数组 parent[] 记录 DFS 树中每个顶点的父节点，初始化为 -1。用一个列表（或集合）存储找到的桥。步骤 2：深度优先搜索（DFS）从每个未访问的顶点开始 DFS（因为图可能不连通）。在 DFS 函数 dfs(u) 中：设置 disc[u] = low[u] = ++time 。遍历 $u$ 的所有邻接顶点 $v$：如果 $v$ 未被访问过（ disc[v] == -1 ）：设置 parent[v] = u 。递归调用 dfs(v) 。递归返回后，更新 low[u] = min(low[u], low[v]) 。检查桥的条件：如果 low[v] > disc[u] ，则边 $(u, v)$ 是桥，加入结果集。如果 $v$ 已被访问过，且 $v$ 不是 $u$ 的父节点（即这是一条后向边）：更新 low[u] = min(low[u], disc[v]) 。注意：这里比较的是 disc[v] ，而不是 low[v] ，因为一条后向边只能直接连到祖先，不能通过多条后向边跳转。步骤 3：处理所有连通分量对每个顶点，如果 disc[u] == -1 ，就调用 dfs(u) 。最后输出所有找到的桥。举例说明考虑图：顶点：0-1-2-0 形成一个环，再加一条边 2-3，3-4。邻接表： 0: 1, 2 1: 0, 2 2: 0, 1, 3 3: 2, 4 4: 3 执行过程：从顶点 0 开始 DFS。访问顺序：disc[ 0]=1, low[ 0 ]=1。访问邻居 1（未访问），递归进入 1。 disc[ 1]=2, low[ 1 ]=2。从 1 访问邻居 0（已访问，是父节点吗？父节点是 0，但这里 0 是父节点，跳过），访问邻居 2（未访问），递归进入 2。 disc[ 2]=3, low[ 2 ]=3。从 2 访问邻居 0（已访问，不是父节点 1），更新 low[ 2]=min(3, disc[ 0]=1) → low[ 2 ]=1。从 2 访问邻居 1（已访问，是父节点吗？父节点是 1，跳过）。从 2 访问邻居 3（未访问），递归进入 3。 disc[ 3]=4, low[ 3 ]=4。从 3 访问邻居 2（已访问，是父节点），跳过。从 3 访问邻居 4（未访问），递归进入 4。 disc[ 4]=5, low[ 4 ]=5。从 4 访问邻居 3（已访问，是父节点），跳过。递归返回 3，更新 low[ 3]=min(4, low[ 4]=5) → low[ 3 ]=4。检查边 (3,4)：low[ 4]=5 > disc[ 3 ]=4 → 是桥，记录 (3,4)。递归返回 2，更新 low[ 2]=min(1, low[ 3]=4) → low[ 2 ]=1。检查边 (2,3)：low[ 3]=4 > disc[ 2 ]=3 → 是桥，记录 (2,3)。递归返回 1，更新 low[ 1]=min(2, low[ 2]=1) → low[ 1 ]=1。检查边 (1,2)：low[ 2]=1 > disc[ 1 ]=2？不成立（1>2 假），所以不是桥。递归返回 0，更新 low[ 0]=min(1, low[ 1]=1) → low[ 0 ]=1。检查边 (0,1)：low[ 1]=1 > disc[ 0 ]=1？不成立（1>1 假），不是桥。从 0 访问邻居 2（已访问，不是父节点），更新 low[ 0]=min(1, disc[ 2]=3) → low[ 0 ]=1。结果桥集：{(2,3), (3,4)}。这与直观一致：去掉 (2,3) 或 (3,4) 都会增加连通块。复杂度分析时间复杂度：$O(V+E)$，因为每个顶点和边在 DFS 中只被访问常数次。空间复杂度：$O(V)$，用于存储 disc 、 low 、 parent 数组和递归栈。关键点总结桥的判断条件是对于树边 $(u,v)$ 有 low[v] > disc[u] 。在更新 low[u] 时，对后向边用 disc[v] 更新。需要处理不连通图，所以要从每个未访问的顶点开始 DFS。这个算法是 Tarjan 算法在无向图桥检测上的经典应用，与求割点的区别在于判断条件（割点是 low[v] >= disc[u] 且需特殊处理根节点）。