所有文章 标签 分类

Kosaraju 算法：求解有向图的强连通分量

MartinLwx  收录于  类别 Algorithm
     约 1107 字  预计阅读 3 分钟 

在做算法题练习的时候遇到了一道有趣的题目 - 1682. Flight Routes Check。要解决这一道题需要高效确定一个有向图上有多少强连通分量。在看了一下题解之后，我发现 Kosaruju 算法可以用于解决这个问题，它可以在线性时间内找到有向图的所有强连通分量。这里说的线性时间是

$$ O(V+E) $$

其中 $V$ 为图的节点个数，$E$ 为图的边的个数

说是有趣是因为这个算法的实现很简单，但是要形成关于这个算法的直觉我发现确实需要费点功夫。在我看来，在学习算法的过程中，弄懂 Why 比知道 How 来说更有价值，因此有了这篇博客，与你分享关于我的一点看法

规定记号如下

  • $G$ 表示原始有向图
  • $G’$ 表示它的反向图。一个图的反向图就是保持节点不变，将所有的边调转方向得到的图

算法流程

  • 将 $G$ 的所有的边调转方向，得到 $G'$
  • 正向 DFS：遍历 $G$ 上的所有节点跑 DFS，并将遍历到的节点按照结束访问的顺序（后序）放入一个栈里面
  • 反向 DFS：根据上一步的栈，不断弹出栈顶的节点，在 $G’$ 上跑 DFS，相当于上一轮最后结束访问的会最先被访问到。每一轮 DFS 发现的点都在同一个强连通分量上
Tip

正向 DFS 和反向 DFS 的区别在于操作的对象不同，前者是原始图 $G$，后者是反向图 $G’$。这里用不同的名字加以区分

flowchart
    subgraph G
        SCC1(SCC1) --> SCC2(SCC2) --> n(...) --> SCC3(SCC3 )
    end

flowchart
    subgraph G'
        CCS3(SCC3) --> m(...) --> CCS2(SCC2) --> CCS1(SCC1)
    end

将有向图上的每个强连通分量压缩成一个点，那么这个有向图就变成了一个 DAG。上面我用 mermaid 画了一个图示，其中 SCC 是强连通分量（Strongly Connected Component) 的缩写

Tip

在 DAG 上，Source 的意思是没有入边的节点，Sink 的意思是没有出边的节点

正向 DFS 的时候，最后结束访问的肯定是 $G$ 构成的 DAG 上的 Source（对应 $G$ 的 $SCC1$)

反向 DFS 的时候会从 $G’$ 构成的 DAG 的 Sink（对应 $G$ 构成的 DAG 的 Source $SCC1$（对应 ）出发开始遍历。但注意，现在不同的 强连通分量 之间的边也反过来了，所以此时 DFS 没法跑出强连通分量。以上图为例，在 $G’$ 上从 $SCC1$ 开始做反向 DFS 的时候，肯定没法跑出 $SCC1$，其他的同理

正是因为这个性质，保证了在反向 DFS 的时候，每次结束一轮 DFS 都能找到一个强连通分量

当然能够这么做还依赖于下面这么一个事实：如果将一个 强连通分量 里所有节点的边反向翻过来，它依然是一个 强连通分量

下面是 1682. Flight Routes Check 的题解

c++

#include <algorithm>
#include <iostream>
#include <vector>

using std::cin;
using std::cout;
using std::fill;
using std::vector;

void dfs(int cur, const vector<vector<int>> &graph, vector<bool> &visited,
         vector<int> &stack, bool recorded) {
  if (visited[cur]) {
    return;
  }
  visited[cur] = true;
  for (const auto &out : graph[cur]) {
    dfs(out, graph, visited, stack, recorded);
  }
  if (recorded) {
    // finishing time
    stack.push_back(cur);
  }
}
int main() {
  // IO
  int N{}, M{};
  cin >> N >> M;
  vector<vector<int>> G(N + 1);
  vector<vector<int>> GT(N + 1);
  for (auto i{0}; i < M; i++) {
    int x{}, y{};
    cin >> x >> y;
    G[x].push_back(y);
    GT[y].push_back(x);
  }

  // DFS on original graph (G)
  vector<bool> visited(N + 1, false);
  vector<int> stack;
  for (auto i{1}; i <= N; i++) {
    if (!visited[i]) {
      // Set recorded to true to put nodes to a stack by finishing time
      dfs(i, G, visited, stack, true);
    }
  }

  // Reset visited
  fill(visited.begin(), visited.end(), false);

  // DFS on transpose graph (GT)
  vector<int> ans;
  while (!stack.empty()) {
    const auto node{stack.back()};
    if (!visited[node]) {
      ans.push_back(node);
      dfs(node, GT, visited, stack, false);
    }
    stack.pop_back();
  }

  if (ans.size() > 1) {
    cout << "NO\n" << ans[1] << " " << ans[0] << "\n";
  } else {
    cout << "YES\n";
  }
}
更新于 2025-04-26
 Algorithm
 | 主页