Tarjan算法求有向图的强连通分量 题目描述 给定一个有向图，其强连通分量（Strongly Connected Component, SCC）是一个最大的顶点子集，使得该子集中任意两个顶点u和v都互相可达（即存在从u到v的路径，也存在从v到u的路径）。题目要求你找出这个有向图中所有的强连通分量。Tarjan算法是一种基于深度优先搜索（DFS）的高效算法，它可以在线性时间O(V+E)内解决此问题。 解题过程 核心概念与准备工作 强连通分量（SCC） ： 这是我们要寻找的目标。一个有向图可以被唯一地分解为若干个强连通分量，这些分量之间可能存在连接，但每个分量内部是“紧密相连”的”。 DFS生成树 ： Tarjan算法建立在DFS的基础上。当我们从某个起点开始对图进行DFS时，会形成一棵DFS树（或森林）。算法会利用DFS遍历的特性来识别SCC。 关键数组 ： 算法为每个顶点维护两个重要的值： index[u] （或常写作 dfn[u] ）： 顶点u被DFS访问到的顺序编号（时间戳）。 lowLink[u] （或常写作 low[u] ）： 从顶点u出发，通过有向边、以及 最多一条 指向DFS树中祖先的回边（后文会解释），所能到达的顶点中最小的 index 值。这个概念是算法的核心。 算法核心思想 算法的目标是找出哪些顶点属于同一个SCC。一个关键观察是： 在一个SCC中，必然存在一个顶点，它是该SCC中第一个被DFS访问到的顶点，我们称其为该SCC的“根”。对于这个根顶点，它的 lowLink 值将等于它自己的 index 值。 在DFS过程中，我们用一个栈来辅助记录当前搜索路径上可能属于同一个SCC的顶点。 算法步骤详解 让我们一步步模拟算法的执行过程。假设我们有一个有向图，顶点为A, B, C, D, E, F, G。边的连接关系我们将在遍历中体现。 步骤1：初始化 我们初始化一个 index 计数器 time = 0 ，一个栈 stack ，以及 index 和 lowLink 数组，初始值都为-1（表示未访问）。同时需要一个数组来记录顶点是否在栈中。 步骤2：开始DFS遍历 我们从一个未访问的顶点开始DFS。假设从顶点A开始（index=0）。 访问顶点A ： 将A的 index 和 lowLink 都设为当前时间戳 time=0 。将A压入栈中，并标记A在栈内。 index = [A:0, B:-, C:-, D:-, F:-, G:-] lowLink = [A:0, ...] stack = [A] time = 1 从A探索到B ： A有边指向B。B未被访问，我们递归DFS(B)。 访问顶点B ： 设置B的 index 和 lowLink 为 time=1 。B入栈。 index = [A:0, B:1, C:-, D:-, F:-, G:-] lowLink = [A:0, B:1, ...] stack = [A, B] time = 2 从B探索到C ： B有边指向C。C未被访问，递归DFS(C)。 访问顶点C ： 设置C的 index 和 lowLink 为 time=2 。C入栈。 index = [A:0, B:1, C:2, D:-, F:-, G:-] lowLink = [A:0, B:1, C:2, ...] stack = [A, B, C] time = 3 从C探索到A ： C有边指回A。A已经被访问过， 并且A在当前的栈中 。这是一个关键发现！这意味着我们发现了一条从当前DFS路径（A->B->C）回到祖先A的边，这条边叫做 回边 。这条边的存在说明A、B、C是连通的。 因此，我们需要更新C的 lowLink 值。因为A的 index=0 比C当前的 lowLink=2 要小，所以我们更新 lowLink[C] = min(lowLink[C], index[A]) = min(2, 0) = 0 。 lowLink = [A:0, B:1, C:0, ...] C的邻接边处理完毕，返回到B。 从B探索到D ： B有边指向D。D未被访问，递归DFS(D)。 访问顶点D ： 设置D的 index 和 lowLink 为 time=3 。D入栈。 index = [A:0, B:1, C:2, D:3, F:-, G:-] lowLink = [A:0, B:1, C:0, D:3, ...] stack = [A, B, C, D] time = 4 从D探索到E ： D有边指向E。E未被访问，递归DFS(E)。 访问顶点E ： 设置E的 index 和 lowLink 为 time=4 。E入栈。 index = [A:0, B:1, C:2, D:3, E:4, F:-, G:-] lowLink = [A:0, B:1, C:0, D:3, E:4, ...] stack = [A, B, C, D, E] time = 5 从E探索到F ： E有边指向F。F未被访问，递归DFS(F)。 访问顶点F ： 设置F的 index 和 lowLink 为 time=5 。F入栈。 index = [A:0, B:1, C:2, D:3, E:4, F:5, G:-] lowLink = [A:0, B:1, C:0, D:3, E:4, F:5, ...] stack = [A, B, C, D, E, F] time = 6 F没有出边。F的DFS结束。 在回溯时，检查F的 lowLink 。此时， index[F] = 5 等于 lowLink[F] = 5 。这说明F是一个SCC的“根”（因为没有任何路径能通到更早的节点）。于是，我们将栈中从F到F的元素弹出，形成一个SCC： {F} 。 stack 弹出F后变为 [A, B, C, D, E] 。 E的DFS结束，回溯到E。 回溯时，检查E。E的邻接点F已经处理完。E的 lowLink 没有变化（ index[E]=4 ）。因为 index[E] == lowLink[E] ，所以E也是一个SCC的根。弹出栈顶元素直到E，得到SCC： {E} 。 stack 变为 [A, B, C, D] 。 D的DFS结束，回溯到D。 回溯时，检查D。D的 index=3 等于 lowLink=3 ，所以D是根。弹出D，得到SCC： {D} 。 stack 变为 [A, B, C] 。 B的DFS结束，回溯到B。 关键步骤：回溯更新 lowLink 。在从D返回到B后，我们需要用D的 lowLink 来更新B的 lowLink 吗？ 不，这里有一个重要规则：我们只通过“在栈中”的邻接点或者DFS树中的子节点来更新 lowLink 。 当我们从子节点C回溯到B时，我们会用C的 lowLink 来更新B的 lowLink ： lowLink[B] = min(lowLink[B], lowLink[C]) = min(1, 0) = 0 。 当我们从子节点D回溯到B时，D已经不在栈中了（因为刚才已经被弹出了），所以我们 不会 用D的 lowLink 来更新B。D属于另一个独立的SCC，它与B不在同一个连通分量里。 因此，B的 lowLink 被更新为0。 lowLink = [A:0, B:0, C:0, D:3, E:4, F:5, ...] A的DFS结束，回溯到A。 同样，在从B回溯到A时，我们用B的 lowLink 来更新A的 lowLink ： lowLink[A] = min(lowLink[A], lowLink[B]) = min(0, 0) = 0 。 处理A ： 现在A的DFS也结束了。我们检查A，发现 index[A] = 0 等于 lowLink[A] = 0 。这说明A是它所在SCC的根。于是，我们将栈中从A到栈顶的元素全部弹出（直到弹出A为止），这些顶点构成一个SCC： {A, B, C} 。 stack 变为空 [] 。 步骤3：处理未访问的顶点 图中还有顶点G未被访问。我们从一个新的DFS起点G开始，重复上述过程。假设G是孤立点或形成一个小环，最终也会被识别为一个SCC，例如 {G} 。 总结与算法伪代码 算法核心操作： DFS访问顶点u时 ： 初始化 index[u] 和 lowLink[u] 为当前时间戳，入栈。 遍历u的邻居v ： 如果v 未访问 ：递归DFS(v)，然后用 lowLink[v] 更新 lowLink[u] 。 如果v 已访问且在栈中 ：用 index[v] 更新 lowLink[u] 。（注意这里是 index[v] ，不是 lowLink[v] ） DFS回溯到u时 ： 检查如果 lowLink[u] 仍然等于 index[u] ，则u是一个SCC的根。开始弹栈，直到u被弹出，弹出的所有顶点形成一个SCC。 通过这个过程，我们成功地找到了示例图中的所有强连通分量： {A, B, C} ， {D} ， {E} ， {F} ， {G} 。Tarjan算法通过DFS的一次遍历，巧妙地利用 index 和 lowLink 以及栈，高效地完成了SCC的分解。