Tarjan 算法求强连通分量
813 字
4 分钟
Tarjan 算法求强连通分量
Tarjan 算法是一种用于 求强连通分量（SCC, Strongly Connected Components） 的高效算法，时间复杂度 O(n + m)，其中 是顶点数， 是边数。它基于 深度优先搜索（DFS），使用回溯的思想来判断一个点是否属于同一个 SCC。
1. Tarjan 算法核心思路
- 时间戳（dfn）：记录每个节点的 DFS 访问次序，每个点的 dfn[u] 值是其访问顺序（从 1 开始递增）。
- 最小可达值（low）：记录 当前节点能通过 DFS 访问到的最早的节点。
- 如果 low[u] == dfn[u]，说明 u 是一个 SCC 的根，栈中 u 及其上方的所有点属于同一 SCC。
- 栈（stack）：维护 SCC，确保 SCC 内的点按拓扑顺序排列。
- 入栈标记（in_stack）：用于判断当前节点是否在栈中，避免重复计算。
2. Tarjan 代码框架
#include <bits/stdc++.h>using namespace std;
const int N = 1e5 + 5; // 最大节点数vector<int> graph[N]; // 邻接表存储图int dfn[N], low[N], scc_id[N], ts = 0, scc_cnt = 0;bool in_stack[N];stack<int> stk;
void tarjan(int u) { dfn[u] = low[u] = ++ts; // 设置访问次序 stk.push(u); in_stack[u] = true;
for (int v : graph[u]) { if (!dfn[v]) { // 递归访问 tarjan(v); low[u] = min(low[u], low[v]); // 回溯更新 low 值 } else if (in_stack[v]) { // 发现回边 low[u] = min(low[u], dfn[v]); } }
if (dfn[u] == low[u]) { // 发现 SCC 根 ++scc_cnt; while (true) { int v = stk.top(); stk.pop(); in_stack[v] = false; scc_id[v] = scc_cnt; // 给 SCC 赋编号 if (v == u) break; } }}
void find_scc(int n) { for (int i = 1; i <= n; i++) { if (!dfn[i]) tarjan(i); }}3. Tarjan SCC 代码详解
(1) dfn[u] 和 low[u]
- dfn[u]：表示 访问次序，用递增的时间戳标记。
- low[u]：表示 回溯能到的最早访问点。
- 更新规则：
low[u] = min(low[u], low[v])（如果 v 是 u 的子节点）。 low[u] = min(low[u], dfn[v])（如果 v 已访问，且 v 在栈中）。
(2) SCC 识别
- 如果 dfn[u] == low[u]，说明 u 是 SCC 根，栈中 u 及其上方的所有点属于同一 SCC。
- SCC 出栈的顺序即拓扑序，可以用于 缩点（Condensation Graph）。
4. SCC 相关应用
(1) 求缩点 DAG
SCC 形成后，我们可以 建立一个新的 DAG（有向无环图），以 SCC 为点，SCC 之间有向边：
vector<int> scc_graph[N]; // SCC 缩点后的图vector<int> scc_in_degree(N, 0); // SCC 入度
void build_scc_graph(int n) { for (int u = 1; u <= n; u++) { for (int v : graph[u]) { if (scc_id[u] != scc_id[v]) { // 仅当 u, v 属于不同 SCC 时建边 scc_graph[scc_id[u]].push_back(scc_id[v]); scc_in_degree[scc_id[v]]++; } } }}(2) 统计有向图中的「强连通块」
Tarjan 算法可以用于求解 一个图最多能划分成多少个强连通块：
cout << "图的强连通分量个数: " << scc_cnt << endl;(3) 计算入度为 0 的 SCC 数量
入度为 0 的 SCC 在缩点 DAG 中没有前驱，可用于拓扑排序：
int zero_in_degree_scc = 0;for (int i = 1; i <= scc_cnt; i++) { if (scc_in_degree[i] == 0) { zero_in_degree_scc++; }}(4) 计算强连通分量中的最小代价
有时 SCC 内有一些数值（如贿赂代价、最小值等），可以用 SCC 合并后取最小值：
vector<int> scc_min_cost(scc_cnt + 1, INF);for (int i = 1; i <= n; i++) { scc_min_cost[scc_id[i]] = min(scc_min_cost[scc_id[i]], cost[i]);}5. 复杂度分析
- Tarjan 的时间复杂度：
每个点 被访问 1 次（O(n)）。 每条边 被遍历 1 次（O(m)）。 总时间复杂度 O(n + m)，适用于 大规模数据（如 ）。
文章分享
如果这篇文章对你有帮助，欢迎分享给更多人！
相关文章智能推荐
1
Grafana 可视化与监控
云原生与运维Grafana 的定位、常见数据源与 Grafana + Prometheus 经典监控链路。
2
微服务之间如何传递 trace
后端开发跨服务传递的是 trace 上下文而非 tracer：HTTP header、gRPC metadata 与 MQ 消息头的标准做法。
3
kubectl port-forward 端口转发
云原生与运维kubectl port-forward 转发 Pod/Service、让局域网访问以及常用排查命令。
4
Wooden Toy Festival 题解：二分答案与贪心验证
数据结构与算法三个雕刻师制作 n 个玩具的最小等待时间：二分答案 + 排序后贪心分配验证，附完整 C++ 代码。
5
kubectl 常用命令速查
云原生与运维kubectl 查看集群/资源/日志、进入容器、本地访问服务与部署删除的常用命令。
随机文章随机推荐