有向图强连通分量（Tarjan算法）

题目描述

给定一个有向图 \(G = (V, E)\)，其强连通分量（Strongly Connected Component, SCC）定义为图的一个最大子图，其中任意两个顶点 \(u\) 和 \(v\) 都互相可达（即存在从 \(u\) 到 \(v\) 的路径，也存在从 \(v\) 到 \(u\) 的路径）。要求设计一个算法，找出该有向图的所有强连通分量。

注意：已讲过使用 Kosaraju算法 求解 SCC，本题聚焦于另一种经典算法——Tarjan算法，它仅需一次深度优先搜索（DFS），时间复杂度为 \(O(|V| + |E|)\)，空间复杂度为 \(O(|V|)\)。

解题过程

1. 核心思想

Tarjan算法通过一次DFS遍历图，在遍历过程中维护两个关键数组：

• dfn[u]：顶点 \(u\) 的DFS序（即DFS访问到该顶点的时间戳）。
• low[u]：从 \(u\) 出发，通过有向边及其DFS树边、后向边（指向祖先的边）或横叉边（指向已访问但非祖先的顶点）所能到达的最早（dfn值最小）的祖先顶点。

如果一个顶点 \(u\) 满足 dfn[u] == low[u]，则 \(u\) 是一个强连通分量的“根”，此时可以从栈中弹出顶点，直到弹出 \(u\) 为止，这些顶点构成一个强连通分量。

2. 算法步骤

步骤 1：初始化

• 定义全局变量：
  • index：当前DFS序计数器，初始为0。
  • stack：一个栈，用于存储当前DFS路径上的顶点。
  • in_stack：布尔数组，标记顶点是否在栈中。
• 为每个顶点 \(u\) 初始化：
  • dfn[u] = 0（表示未访问）。
  • low[u] = 0。

步骤 2：深度优先搜索（DFS）
对每个未访问的顶点 \(u\) 调用DFS函数 dfs(u)：

1. 设置 dfn[u] = low[u] = ++index。
2. 将 \(u\) 入栈，并标记 in_stack[u] = true。
3. 遍历 \(u\) 的每个邻接顶点 \(v\)：
   • 若 \(v\) 未访问（dfn[v] == 0）：
     • 递归调用 dfs(v)。
     • 更新 low[u] = min(low[u], low[v])。
   • 若 \(v\) 已访问且在栈中（in_stack[v] == true）：
     • 更新 low[u] = min(low[u], dfn[v])。注意这里用 dfn[v] 而非 low[v]，因为横叉边不能跨越不同SCC。
4. 回溯时检查：若 dfn[u] == low[u]，则 \(u\) 是一个SCC的根：
   • 不断从栈中弹出顶点，直到弹出 \(u\)。
   • 弹出的所有顶点构成一个强连通分量。
   • 将这些顶点的 in_stack 标记设为 false。

步骤 3：遍历所有顶点
对图中所有顶点，若其 dfn 值为0（未访问），则调用 dfs(u)。

3. 示例演示

考虑有向图：

顶点：0, 1, 2, 3, 4
边：(0→1), (1→2), (2→0), (1→3), (3→4), (4→3)

执行Tarjan算法：

• 从顶点0开始DFS：
  • 访问0 → 访问1 → 访问2（边2→0指向已访问且在栈中的0，更新low[2]=1）→ 回溯更新low[1]=1。
  • 从1访问3 → 访问4（边4→3指向已访问且在栈中的3，更新low[4]=4）→ 回溯时low[3]=4，dfn[3]!=low[3]。
  • 回溯到1时，发现边1→3已处理。
• 当DFS回到顶点0时，dfn[0]==low[0]==1，弹出栈中{0,2,1}作为一个SCC。
• 继续从顶点3开始（若未访问），但实际上3已在栈中，当递归返回到3时，dfn[3]==low[3]==4，弹出{3,4}作为另一个SCC。

结果：两个强连通分量：{0,1,2} 和 {3,4}。

4. 正确性分析

• low[u] 的定义：保证了它始终指向 \(u\) 能到达的最早祖先。若 dfn[u] == low[u]，说明从 \(u\) 出发无法到达比 \(u\) 更早的祖先，因此 \(u\) 是其所在SCC中最早被访问的顶点（根）。
• 栈的作用：栈中存储当前DFS路径上的顶点，这些顶点可能属于同一个SCC。当发现一个根时，栈中从根到栈顶的顶点都在同一个SCC中，因为DFS确保了它们互相可达。
• 横叉边的处理：若边 \(u \to v\) 是横叉边且 \(v\) 在另一个已完成的SCC中，则 in_stack[v] 为false，该边被忽略，不会错误合并SCC。

5. 复杂度分析

• 时间：每个顶点和边被访问一次，因此为 \(O(|V| + |E|)\)。
• 空间：栈和数组需要 \(O(|V|)\) 空间。

6. 代码实现（伪代码）

TarjanSCC(G):
    index = 0
    stack = empty
    for each vertex u in G:
        if dfn[u] == 0:
            dfs(u)

dfs(u):
    dfn[u] = low[u] = ++index
    stack.push(u)
    in_stack[u] = true
    for each edge (u, v):
        if dfn[v] == 0:
            dfs(v)
            low[u] = min(low[u], low[v])
        else if in_stack[v]:
            low[u] = min(low[u], dfn[v])
    if dfn[u] == low[u]:
        // u 是一个SCC的根
        repeat:
            v = stack.pop()
            in_stack[v] = false
            print v
        until v == u
        print "---"  // 分隔SCC

7. 扩展与应用

• 缩点（Condensation）：将每个SCC缩成一个超级顶点，得到的有向无环图（DAG）可用于解决许多问题（如最长路径、拓扑排序）。
• 2-SAT问题：Tarjan算法常用于求解2-SAT，通过判断每个布尔变量及其否定是否在同一个SCC中来判定可满足性。

总结

Tarjan算法通过一次DFS高效求解有向图的强连通分量，核心在于利用 dfn 和 low 数组以及栈来识别SCC的根。它比Kosaraju算法更节省空间（无需反向图），且常数更小，是实践中常用的SCC算法。