图的连通分量与Tarjan算法 一、问题描述 图的连通分量是图论中的基本概念，分为无向图的连通分量和有向图的强连通分量。无向图中，若两个顶点间存在路径，则称它们连通，所有互相连通的顶点构成一个连通分量。有向图中，若两个顶点互相可达（即存在从u到v和从v到u的路径），则称它们强连通，所有互相强连通的顶点构成一个强连通分量（SCC）。Tarjan算法是Robert Tarjan提出的基于深度优先搜索（DFS）的线性时间算法，用于寻找有向图的所有强连通分量。 二、算法核心思想 DFS遍历 ：算法从任意未访问节点开始DFS，记录每个节点的访问顺序（时间戳）。 关键数组 ： dfn[u] ：节点u的DFS序（时间戳）。 low[u] ：从u出发能访问到的最小DFS序（包括通过反向边）。 stack ：保存当前DFS路径上的节点。 inStack[u] ：标记节点u是否在栈中。 强连通分量判定 ：当DFS回溯时，若某个节点的 dfn[u] == low[u] ，说明u是一个SCC的根节点，此时从栈中弹出节点直到u，这些节点构成一个SCC。 三、算法步骤详解 初始化 ： 设置全局计数器 index = 0 ，空栈 stack 。 初始化 dfn 和 low 数组为-1， inStack 数组为false。 DFS遍历每个未访问节点 ： 对节点u，设置 dfn[u] = low[u] = index++ ，将u入栈，标记 inStack[u] = true 。 遍历u的每个邻接节点v： 若v未访问（ dfn[v] == -1 ），递归访问v，然后更新 low[u] = min(low[u], low[v]) 。 若v已访问且在栈中（ inStack[v] == true ），说明(u, v)是反向边，更新 low[u] = min(low[u], dfn[v]) 。 回溯时检查 dfn[u] == low[u] ： 若是，则从栈中弹出节点直到u，这些节点形成一个SCC。 示例 （以有向图为例）： 图：边集为{(1,2), (2,3), (3,1), (3,4), (4,5), (5,6), (6,4)}。 执行过程： 从节点1开始DFS：1->2->3，此时栈为[ 1,2,3 ]，low值在反向边(3,1)时更新。 回溯到节点3时， dfn[3] == low[3] ，弹出[ 3,2,1 ]作为SCC1。 继续访问节点4->5->6，通过反向边(6,4)更新low值。 回溯到节点4时， dfn[4] == low[4] ，弹出[ 6,5,4 ]作为SCC2。 四、复杂度分析 时间复杂度：O(V + E)，每个节点和边仅被处理一次。 空间复杂度：O(V)，用于存储栈和数组。 五、应用场景 编译器优化 ：识别代码中的循环结构。 社交网络分析 ：发现紧密关联的群体。 电路设计 ：检测反馈环路。 通过以上步骤，Tarjan算法高效地将有向图分解为强连通分量，为图结构分析提供了基础工具。