关于Tarjan算法桥判定条件的疑问：为何不能用low[node]<low[child]？

背景与实现代码 #

我正在研究用于寻找网络中关键连接的Tarjan算法，具体应用于LeetCode上的「Critical Connections in a Network」问题。以下是我的实现代码：

class Solution:
    timer=0
    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
        graph=defaultdict(list)
        for a,b in connections:
            graph[a].append(b)
            graph[b].append(a)

        result=[]
        tin=[0]*n
        low=[0]*n
        visited=[False]*n
        def dfs(node,parent):
            self.timer+=1
            visited[node]=True
            tin[node]=self.timer
            low[node]=self.timer
            for child in graph[node]:
                if child==parent: continue
                if visited[child]:
                    low[node]=min(low[node],tin[child])
                else:
                    dfs(child,node)
                    low[node]=min(low[node],low[child])
                    if tin[node]<low[child]:
                        result.append([node,child])
        dfs(0,-1)
        return result

疑问 #

为何不能用条件if low[node]<low[child]:来替代if tin[node]<low[child]:判断桥是否存在？我原理解为：若子节点low值大于父节点low值，说明子节点无法在父节点前被访问，该边是桥。

解答 #

要搞懂这个问题，得先明确tin和low的核心定义：

• tin[node]：节点node被首次访问的时间戳，全局唯一且严格递增，代表节点在遍历顺序中的“初始位置”。
• low[node]：节点node能通过非父节点的边，回溯到的最早时间戳（也就是最小的tin值），可以理解为节点能触及的“最早历史位置”。

桥的本质是：去掉这条边后，图会被拆成两个不连通的部分。对应到Tarjan算法里，就是子节点child没有任何其他路径（除了当前的node-child边）能回到node或者node之前被访问的节点。

为什么tin[node] < low[child]是正确的判定条件？ #

当low[child] > tin[node]时，说明child能回溯到的最早时间戳，比node的首次访问时间还晚——这意味着child完全没法回到node或者更早的节点，只能通过当前的node-child边和node连通。一旦去掉这条边，child所在的子树就会和node所在的部分断开，所以这条边是桥。

为什么low[node] < low[child]不能替代？ #

核心问题在于，low[node]可能因为其他路径（比如node所在的环）被更新成了更早的时间戳，这时候low[node]已经不能代表node自身的首次访问位置了。

举个典型的错误场景：
假设node的tin是10（首次访问时间），但因为node在一个环里，它的low被更新为5（环中更早节点的时间戳）；而child的low是7。此时low[node]=5 < low[child]=7，但low[child]=7 <= tin[node]=10，说明child能回到node的初始访问位置，这条边并不是桥。但如果用low[node]<low[child]的条件，会错误地把它判定为桥。

而tin[node]<low[child]的条件，直接对比child能触及的最早位置和node的初始位置，只要child的最早位置比node的初始位置晚，就说明child完全依赖当前边才能连通，这才是桥的正确判定逻辑。

内容的提问来源于stack exchange，提问作者umeshbhat