强连通分量（Tarjan算法）
字数 1220 2025-11-04 22:27:03

强连通分量（Tarjan算法）

题目描述
给定一个有向图，找出图中所有的强连通分量（Strongly Connected Components, SCC）。强连通分量是指一个最大的子图，其中任意两个顶点都互相可达。Tarjan算法是一种基于深度优先搜索（DFS）的高效算法，能在O(V+E)时间内解决问题，其中V是顶点数，E是边数。

解题过程

  1. 核心思想
    Tarjan算法通过一次DFS遍历，利用两个关键数组disc（发现时间）和low（最早可达祖先的发现时间），以及一个栈来跟踪当前DFS路径上的顶点。当某个顶点的low值等于其disc值时，说明它是一个强连通分量的根节点，此时从栈中弹出顶点直到该根节点，这些顶点构成一个SCC。

  2. 算法步骤

    • 初始化：
      定义全局变量：

      • disc[]：记录每个顶点的发现时间（DFS访问顺序）。
      • low[]：记录顶点通过树边或回边能到达的最早祖先的disc值。
      • stack：临时存储当前DFS路径上的顶点。
      • inStack[]：标记顶点是否在栈中。
      • 全局计数器time，用于分配disc值。

    • DFS遍历：
      对每个未访问的顶点调用DFS：

      1. 设置disc[u] = low[u] = ++time，将u入栈，标记inStack[u] = true。
      2. 遍历u的每个邻接顶点v：
        • 如果v未访问（disc[v] == -1），递归访问v，并更新low[u] = min(low[u], low[v])。
        • 如果v已访问且在栈中（inStack[v] == true），说明(u,v)是回边，更新low[u] = min(low[u], disc[v])。
      3. 回溯时，若low[u] == disc[u]，则u是一个SCC的根。不断从栈中弹出顶点直到u，这些顶点形成一个SCC。

    • 示例：
      考虑有向图：边集为{0→1, 1→2, 2→0, 1→3, 3→4}。

      • 从顶点0开始DFS：
        顶点0、1、2依次入栈，形成环（0→1→2→0）。回溯到顶点2时，low[2] = disc[0] = 1；回溯到顶点1时，low[1] = 1；回溯到顶点0时，low[0] = disc[0] = 1，弹出{0,1,2}作为一个SCC。
      • 继续访问顶点3、4：顶点3的邻接点4未形成环，回溯时low[3] = disc[3] = 4，弹出{3}；最后顶点4单独成SCC{4}。

  3. 复杂度分析

    • 时间复杂度：O(V+E)，每个顶点和边仅被处理一次。
    • 空间复杂度：O(V)，用于栈和数组存储。

  4. 关键点

    • low[u]的更新需区分树边（递归更新）和回边（直接比较disc[v]）。
    • 仅当low[u] == disc[u]时，说明u无法到达更早的祖先，当前栈顶到u之间的顶点构成SCC。

通过以上步骤，Tarjan算法能高效且直观地分解有向图的强连通分量。

强连通分量（Tarjan算法） 题目描述 给定一个有向图，找出图中所有的强连通分量（Strongly Connected Components, SCC）。强连通分量是指一个最大的子图，其中任意两个顶点都互相可达。Tarjan算法是一种基于深度优先搜索（DFS）的高效算法，能在O(V+E)时间内解决问题，其中V是顶点数，E是边数。 解题过程 核心思想 Tarjan算法通过一次DFS遍历，利用两个关键数组 disc （发现时间）和 low （最早可达祖先的发现时间），以及一个栈来跟踪当前DFS路径上的顶点。当某个顶点的 low 值等于其 disc 值时，说明它是一个强连通分量的根节点，此时从栈中弹出顶点直到该根节点，这些顶点构成一个SCC。 算法步骤 初始化 ： 定义全局变量： disc[] ：记录每个顶点的发现时间（DFS访问顺序）。 low[] ：记录顶点通过树边或回边能到达的最早祖先的 disc 值。 stack ：临时存储当前DFS路径上的顶点。 inStack[] ：标记顶点是否在栈中。 全局计数器 time ，用于分配 disc 值。 DFS遍历 ： 对每个未访问的顶点调用DFS： 设置 disc[u] = low[u] = ++time ，将u入栈，标记 inStack[u] = true 。 遍历u的每个邻接顶点v： 如果v未访问（ disc[v] == -1 ），递归访问v，并更新 low[u] = min(low[u], low[v]) 。 如果v已访问且在栈中（ inStack[v] == true ），说明(u,v)是回边，更新 low[u] = min(low[u], disc[v]) 。 回溯时，若 low[u] == disc[u] ，则u是一个SCC的根。不断从栈中弹出顶点直到u，这些顶点形成一个SCC。 示例 ： 考虑有向图：边集为{0→1, 1→2, 2→0, 1→3, 3→4}。 从顶点0开始DFS： 顶点0、1、2依次入栈，形成环（0→1→2→0）。回溯到顶点2时， low[2] = disc[0] = 1 ；回溯到顶点1时， low[1] = 1 ；回溯到顶点0时， low[0] = disc[0] = 1 ，弹出{0,1,2}作为一个SCC。 继续访问顶点3、4：顶点3的邻接点4未形成环，回溯时 low[3] = disc[3] = 4 ，弹出{3}；最后顶点4单独成SCC{4}。 复杂度分析 时间复杂度：O(V+E)，每个顶点和边仅被处理一次。 空间复杂度：O(V)，用于栈和数组存储。 关键点 low[u] 的更新需区分树边（递归更新）和回边（直接比较 disc[v] ）。 仅当 low[u] == disc[u] 时，说明u无法到达更早的祖先，当前栈顶到u之间的顶点构成SCC。 通过以上步骤，Tarjan算法能高效且直观地分解有向图的强连通分量。