寻找无向图中的所有桥（Bridges）问题

问题描述
在无向连通图中，桥是指这样的一条边：如果移除它，图的连通分量数量会增加。换句话说，桥是连接两个连通部分的关键边，删除后图会变得不连通。我们需要设计一个算法，找出给定无向图中的所有桥。

基础概念

1. 连通图：图中任意两个顶点之间都存在路径。
2. 桥：一条边 (u, v) 是桥，当且仅当删除它后，原图分裂成两个或多个连通分量。
3. DFS 生成树：通过深度优先搜索遍历图时形成的树结构，包含树边（遍历路径）和回边（连接祖先节点的边）。

解题思路
我们使用基于 DFS 的 Tarjan 算法变种来检测桥。核心思想是利用 DFS 遍历顺序和“最低可达祖先”的概念。

关键定义

• disc[u]：顶点 u 在 DFS 中被访问的时间（发现时间）。
• low[u]：顶点 u 通过其子树中的边或一条回边能够到达的最早被访问的祖先的 disc 值。

桥的判定条件
对于边 (u, v)，如果 low[v] > disc[u]，则 (u, v) 是桥。这意味着 v 无法通过其他路径回到 u 或其祖先，因此删除 (u, v) 会使 v 及其后代与图的其他部分分离。

详细步骤

1. 初始化

   • 创建数组 disc[] 和 low[]，初始化为 -1（未访问）。
   • 使用变量 time 记录 DFS 的访问顺序。
   • 使用父节点数组 parent[] 避免重复处理无向边。

2. DFS 遍历
   从任意未访问顶点开始 DFS，对每个顶点 u：

   • 设置 disc[u] = low[u] = ++time。
   • 遍历 u 的每个邻居 v：
     • 如果 v 未被访问（disc[v] == -1）：
       • 设置 parent[v] = u。
       • 递归处理 v。
       • 回溯时更新：low[u] = min(low[u], low[v])。
       • 检查桥：若 low[v] > disc[u]，则 (u, v) 是桥。
     • 如果 v 已被访问且 v ≠ parent[u]（避免直接父节点）：
       • 更新 low[u] = min(low[u], disc[v])（通过回边更新）。

3. 注意事项

   • 根节点（无父节点）需要特殊处理，但根节点不会形成桥（因为无父边）。
   • 确保每条无向边只处理一次。

实例演示
考虑无向图：

0 — 1 — 2
|    |    |
3 — 4 — 5 — 6

顶点 0~6，边如所示。

执行过程（从顶点 0 开始 DFS）：

1. 访问 0 (disc=0, low=0) → 邻居 1、3。
2. 访问 1 (disc=1, low=1) → 邻居 0（父节点，跳过）、2、4。
3. 访问 2 (disc=2, low=2) → 邻居 1（父节点）、5。
4. 访问 5 (disc=3, low=3) → 邻居 2（父节点）、4、6。
5. 访问 4 (disc=4, low=4) → 邻居 1（父节点）、3、5。
   • 发现回边 4→3（disc[3] 未访问？等待后续）。
6. 回溯更新 low 值：
   • 顶点 4 通过回边 4→3 更新 low[4] = min(4, disc[3])。
   • 检查边 (1,4)：low[4] = 0（假设 3 的 disc=0）> disc[1]=1？不成立，非桥。
7. 继续遍历至顶点 3（从 0→3），更新 low[3] 等。
8. 最终识别桥：例如边 (5,6) 满足 low[6] > disc[5]。

结果：桥为 (5,6) 等（具体取决于遍历顺序，但算法确保正确找出所有桥）。

总结

• 算法时间复杂度：O(V + E)，每个顶点和边只处理一次。
• 关键在 low 值的更新和桥条件判断。
• 此方法高效且易于实现，是解决无向图桥检测的标准算法。