Tarjan算法求无向图的桥（Bridges）问题 题目描述 给定一个无向连通图（若图非连通，算法也可处理每个连通分量），求出图中所有的“桥”。桥（Bridges），也称割边（Cut Edges），是指这样一条边：如果移除这条边，图的连通分量数量会增加。换句话说，桥是连接两个不同双连通分量的唯一关键边，移除它会导致原图不再连通。 算法核心思想 Tarjan算法通过一次深度优先搜索（DFS）遍历，在遍历过程中为每个节点维护两个关键时间戳： dfs_num （发现时间）和 low （通过后向边能回溯到的最早祖先发现时间）。通过比较一条边两端节点的 low 值，可以判断该边是否为桥。 具体步骤详解 数据表示 假设图有 n 个节点（编号 0 至 n-1），使用邻接表存储。我们需要定义： vector<int> dfs_num(n, -1) ：记录每个节点的DFS发现次序（时间戳），未访问为 -1。 vector<int> low(n, 0) ：记录每个节点通过其子树中的后向边能回溯到的 最早祖先 的 dfs_num 值。 int timer = 0 ：全局时间戳，每访问一个新节点就递增。 vector<pair<int, int>> bridges ：存储所有找到的桥（边的两个端点）。 深度优先搜索（DFS） 从任意未访问节点开始DFS。对于当前节点 u ： a. 初始化 dfs_num[u] = low[u] = timer++ 。 b. 遍历 u 的每一个邻居 v 。 如果 v 未被访问（ dfs_num[v] == -1 ）： 递归访问 v 。 递归返回后，更新 low[u] = min(low[u], low[v]) 。 关键判断 ：如果 low[v] > dfs_num[u] ，则边 (u, v) 是一个桥。因为 v 及其子树无法通过任何后向边回到 u 或其祖先，这意味着移除 (u, v) 后 v 所在的子图将与 u 分离。 如果 v 已被访问 且不是 u 在DFS树中的父节点 （即 v != parent ），则 (u, v) 是一条后向边。更新 low[u] = min(low[u], dfs_num[v]) 。 注意：这里使用 dfs_num[v] 而不是 low[v] ，因为后向边直接连接到 v 这个已访问节点本身。 处理非连通图 若图有多个连通分量，则对每个未访问节点执行上述DFS过程。 算法示例 考虑一个简单无向图： 节点：0, 1, 2, 3 边： (0,1), (1,2), (2,3), (3,1) 这是一个有环的连通图。 执行过程（假设从节点0开始）： 访问0（dfs_ num=0, low=0），递归访问邻居1。 访问1（dfs_ num=1, low=1），递归访问邻居2（因为0已访问且是父节点，跳过）。 访问2（dfs_ num=2, low=2），递归访问邻居3（邻居1已访问但非父节点，记录后向边）。 访问3（dfs_ num=3, low=3）。邻居1已访问且非父节点， low[3] = min(3, dfs_num[1]=1) = 1 。 递归返回到节点2：更新 low[2] = min(2, low[3]=1) = 1 。检查边(2,3)： low[3]=1 <= dfs_num[2]=2 ，不是桥。 递归返回到节点1：更新 low[1] = min(1, low[2]=1) = 1 。检查边(1,2)： low[2]=1 <= dfs_num[1]=1 ，不是桥。 递归返回到节点0：更新 low[0] = min(0, low[1]=1) = 0 。检查边(0,1)： low[1]=1 > dfs_num[0]=0 ， 所以边(0,1)是桥 。 最终结果：桥是 (0,1) 。移除这条边，节点0将与其他部分断开。 时间复杂度与空间复杂度 时间复杂度 ：O(V + E)，其中 V 是顶点数，E 是边数。因为算法本质是一次DFS遍历。 空间复杂度 ：O(V)，用于存储 dfs_num 、 low 数组和递归栈（最坏情况为 O(V)）。 算法实现要点 使用递归或显式栈实现DFS。 必须避免将父节点误判为后向边，因此DFS函数需传入父节点参数。 对于无向图，每条边会被访问两次（两个方向），但判断桥时只需记录一次。 这就是利用Tarjan算法求解无向图中所有桥的完整过程。它高效且直观，是图论中双连通性分析的基础算法之一。