从 DFS 到 Tarjan 算法：理解 low 数组的 3 种更新策略与 2 个关键不等式-育师

从DFS到Tarjan算法：low数组的三种更新策略与两个关键不等式

1. 深度优先搜索（DFS）的基础回顾

在探索图论算法的过程中，深度优先搜索（DFS）无疑是最基础也最重要的工具之一。这种算法以一种"不撞南墙不回头"的方式遍历图中的节点，沿着一条路径尽可能深入，直到无法继续前进才回溯。这种特性使得DFS成为许多高级图算法的基础，包括我们今天要重点讨论的Tarjan算法。

DFS的核心在于其递归性质和对访问状态的维护。每个节点在首次被访问时被标记为"已发现"，并在其所有邻居都被探索完毕后标记为"已完成"。这种遍历顺序自然地产生了一棵DFS树（或森林），其中包含了所有从起点可达的节点。

def dfs(u): visited[u] = True for v in graph[u]: if not visited[v]: dfs(v)

在DFS的执行过程中，我们可以为每个节点记录两个关键的时间戳：

发现时间（discovery time/depth-first number, dfn）：记录节点首次被访问的顺序
完成时间（finishing time）：记录节点及其所有邻居都被完全探索的顺序

这两个时间戳将帮助我们理解图中节点之间的依赖关系，并为后续的Tarjan算法奠定基础。

2. Tarjan算法与强连通分量

2.1 强连通分量的定义

在图论中，强连通分量（Strongly Connected Component, SCC）是指有向图中的一个极大子图，其中任意两个节点都互相可达。换句话说，对于子图中的任意节点u和v，都存在从u到v和从v到u的路径。

识别强连通分量对于理解有向图的结构至关重要，它在编译器优化、社交网络分析、电路设计等领域都有广泛应用。Robert Tarjan在1972年提出的算法以其优雅和高效著称，仅需一次DFS遍历就能找出所有强连通分量。

2.2 Tarjan算法的核心思想

Tarjan算法的精妙之处在于它通过DFS遍历时维护了两个关键信息：

dfn数组：记录每个节点的发现时间（DFS序号）
low数组：记录从当前节点出发，通过DFS树边和后向边能够到达的最早（dfn最小）的祖先节点

算法使用一个栈来跟踪当前DFS路径上的节点。当发现某个节点的low值等于其dfn值时，说明找到了一个强连通分量的根节点，此时将栈中该节点之上的所有节点弹出，它们构成一个强连通分量。

3. low数组的三种更新策略

理解low数组的更新策略是掌握Tarjan算法的关键。在DFS遍历过程中，low[u]的更新遵循以下三种情况：

3.1 访问未访问子节点

当遇到一个未被访问的子节点v时，递归处理该节点后，用low[v]更新low[u]：

low[u] = min(low[u], low[v])

这种情况反映了通过子树能够到达的最早祖先。

3.2 遇到后向边

当遇到一条指向栈中节点（即DFS树中的祖先节点）的边时，用该祖先的dfn值更新low[u]：

low[u] = min(low[u], dfn[v])

后向边表明图中存在环路，这是形成强连通分量的关键。

3.3 遇到横叉边或前向边

对于指向非栈中节点（即已经处理完成的节点）的边，这些边不会影响当前强连通分量的形成，因此不需要更新low值。这是Tarjan算法与Kosaraju算法的一个重要区别。

4. 割点与桥的判断不等式

Tarjan算法不仅可以用于寻找强连通分量，稍加修改后还能识别无向图中的关键节点（割点）和关键边（桥）。

4.1 割点判断（low[v] >= dfn[u]）

对于非根节点u，如果存在子节点v满足low[v] ≥ dfn[u]，则u是一个割点。这意味着v及其后代无法通过其他路径到达u的祖先，移除u将断开图的连通性。

对于根节点，只需检查它是否有至少两个子节点即可判断是否为割点。

4.2 桥判断（low[v] > dfn[u]）

对于边(u,v)，如果low[v] > dfn[u]，则该边是桥。这意味着v及其后代无法通过其他路径到达u或其祖先，移除这条边将断开图的连通性。

5. 算法实现与优化

以下是Tarjan算法的Python实现，包含了强连通分量、割点和桥的检测：

def tarjan(): global dfn, low, stack, in_stack, time_stamp, scc_count dfn = [0] * (n + 1) low = [0] * (n + 1) in_stack = [False] * (n + 1) stack = [] time_stamp = 0 scc_count = 0 for u in range(1, n + 1): if dfn[u] == 0: dfs(u) def dfs(u): global time_stamp, scc_count time_stamp += 1 dfn[u] = low[u] = time_stamp stack.append(u) in_stack[u] = True for v in graph[u]: if dfn[v] == 0: # 树边 dfs(v) low[u] = min(low[u], low[v]) # 割点判断 if low[v] >= dfn[u]: if u != root or children >= 2: cut_points.add(u) # 桥判断 if low[v] > dfn[u]: bridges.add((u, v)) elif in_stack[v]: # 后向边 low[u] = min(low[u], dfn[v]) # SCC判断 if dfn[u] == low[u]: scc_count += 1 while True: v = stack.pop() in_stack[v] = False scc[v] = scc_count if v == u: break

在实际应用中，我们可以针对不同需求对算法进行优化：