Tarjan算法

YZY Lv3
  2025-07-02 02:14:49 2025-07-02 02:14:49 Created   2025-07-02 02:14:49 2025-07-02 02:14:49 Updated      

Tarjan 算法是由计算机科学家 Robert Tarjan 提出的，用于解决图论中的一些经典问题，尤其是在有向图中的强连通分量（SCC）问题。Tarjan 算法能够在图的深度优先搜索（DFS）基础上高效地找到图的所有强连通分量。强连通分量是图中每一部分节点的集合，这些节点在有向图中相互可达。

1. 强连通分量（SCC）

在有向图中，一个强连通分量是一个节点集合，对于该集合中的每一对节点，彼此都有路径可以到达对方。换句话说，强连通分量是图中自足的、没有外部连接的子图。Tarjan 算法的主要目标就是通过 DFS 查找图中所有的强连通分量。

2. Tarjan 算法的核心思想

Tarjan 算法基于深度优先搜索（DFS）来遍历图，并通过一些辅助数据结构来找到强连通分量。其主要思想是利用 DFS 树中的回退机制，来找出图中所有的强连通分量。

3. 算法细节

3.1 关键数据结构

  1. DFS 栈：用于记录 DFS 遍历过程中节点的访问顺序。
  2. low 数组：表示当前节点能够回溯到的最早的访问节点（具有最小的DFS编号），即某个节点的 low 值是该节点及其子节点所能回溯到的最小DFS编号。
  3. index 数组：表示每个节点在 DFS 中的访问顺序编号，用来区分不同的节点。
  4. on_stack 标志数组：记录一个节点是否在 DFS 栈中，以避免重复处理。

3.2 算法流程

  1. DFS 遍历：从一个未被访问的节点出发，进行 DFS 遍历，将每个节点的 index 和 low 值初始化。
  2. 更新 low 值：在访问节点时，更新节点的 low 值。如果一个节点的邻居还在栈中，那么可以通过该邻居回溯更新当前节点的 low 值。
  3. 发现强连通分量：当一个节点的 low 值等于它的 index 值时，说明该节点是一个强连通分量的根节点，此时从栈中弹出所有节点，直到根节点，形成一个 SCC。
  4. 重复执行：对于图中每个未被访问的节点，重复上述操作，直到所有节点都被处理。

3.3 复杂度分析

Tarjan 算法的时间复杂度为 **O(V + E)**，其中 V 是图中节点的数量，E 是图中边的数量。由于每个节点和边最多只会被访问一次，所以时间复杂度是线性的。

4. Tarjan 算法的应用

Tarjan 算法有许多应用，最典型的就是在有向图中查找强连通分量。在许多领域中，强连通分量的识别有着重要的作用。例如：

  1. 拓扑排序：在有向无环图（DAG）中，SCC 可用于判定图是否是无环图，并帮助进行拓扑排序。
  2. 图的压缩：通过 Tarjan 算法，能够将图压缩为其强连通分量的集合，简化图的表示。
  3. 求解强连通问题：Tarjan 算法是解决社交网络、推荐系统中的图问题的有效工具。

5. 代码实现

  1. DFS遍历：从一个未被访问的节点开始深度优先搜索，并为每个节点赋予一个index（即DFS遍历中的访问时间戳）。同时，记录每个节点的low值，表示该节点及其子树能够回溯到的最早节点。
  2. 低链接更新：在DFS过程中，如果遍历到某个节点的邻接节点，而该邻接节点已经访问过，则更新当前节点的low值。
  3. 发现SCC：如果一个节点的low值等于它的index值，说明从该节点出发，所有的子节点都可以通过反向路径回到该节点，因此从栈中弹出所有节点，直到找到该节点为止，形成一个强连通分量。

C++实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

const int MAXN = 100000; // 最大节点数
vector<int> adj[MAXN]; // 邻接表表示图
int indexCounter = 0;  // 索引计数器
int indexArr[MAXN];    // 存储每个节点的访问顺序
int low[MAXN];         // 存储每个节点的低链接值
bool onStack[MAXN];    // 标记节点是否在栈中
stack<int> stk;        // 栈，用来存放节点
vector<vector<int>> sccs; // 用来存储所有强连通分量

// Tarjan算法核心函数
void tarjanDFS(int u) {
    indexArr[u] = low[u] = indexCounter++; // 为当前节点分配访问顺序
    stk.push(u);  // 将节点压入栈
    onStack[u] = true; // 标记节点在栈中

    // 遍历当前节点的所有邻接节点
    for (int v : adj[u]) {
        if (indexArr[v] == -1) {
            // 如果邻接节点没有被访问过，递归DFS
            tarjanDFS(v);
            low[u] = min(low[u], low[v]);
        } else if (onStack[v]) {
            // 如果邻接节点已经在栈中（即是当前SCC的一部分）
            low[u] = min(low[u], indexArr[v]);
        }
    }

    // 如果当前节点的low值等于其索引值，说明找到了一个SCC
    if (indexArr[u] == low[u]) {
        vector<int> scc; // 存储当前强连通分量
        while (true) {
            int v = stk.top();
            stk.pop();
            onStack[v] = false;
            scc.push_back(v); // 将栈中弹出的节点加入SCC
            if (v == u) break;
        }
        sccs.push_back(scc); // 将当前SCC加入到结果中
    }
}

int main() {
    int n, m;
    cin >> n >> m; // 输入节点数和边数

    // 读取图的边信息
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
    }

    // 初始化
    fill(indexArr, indexArr + n, -1);  // 设置每个节点的index为-1，表示未访问
    fill(low, low + n, -1);             // 设置low为-1，表示没有计算low值

    // 对图进行DFS遍历
    for (int i = 0; i < n; i++) {
        if (indexArr[i] == -1) {
            tarjanDFS(i); // 对每个未访问的节点执行DFS
        }
    }

    // 输出所有的强连通分量
    cout << "Strongly Connected Components (SCCs):" << endl;
    for (const auto& scc : sccs) {
        for (int node : scc) {
            cout << node << " ";
        }
        cout << endl;
    }

    return 0;
}

代码解释

  1. 输入：

    • 代码首先从输入中读取图的节点数n和边数m。
    • 然后根据输入的边信息填充邻接表adj。

  2. 初始化：

    • indexArr[]和low[]数组用于存储每个节点的访问顺序编号和低链接值。初始化时，这两个数组的所有元素都设置为-1，表示节点尚未被访问。
    • onStack[]数组用于标记一个节点是否在当前的DFS栈中。

  3. DFS遍历：

    • 对每个未访问的节点u，调用tarjanDFS(u)开始深度优先搜索。
    • 在DFS过程中，节点u的indexArr[u]和low[u]都被赋予一个唯一的递增值。
    • 遍历u的所有邻接节点v，如果v尚未访问，则递归DFS；如果v已经在栈中，更新low[u]。

  4. 强连通分量的发现：

    • 如果当前节点u的indexArr[u]等于low[u]，则说明u是一个强连通分量的根节点。此时从栈中弹出所有节点，直到找到u，并将这些节点组成一个强连通分量。

  5. 输出：

    • 最后，将所有强连通分量打印出来，每个分量中的节点按顺序输出。

算法复杂度分析

  • 时间复杂度：Tarjan算法的时间复杂度为 **O(V + E)**，其中V是节点数，E是边数。因为每个节点和每条边都被访问一次。
  • 空间复杂度：空间复杂度为 **O(V + E)**，用于存储图的邻接表、栈以及其他辅助数组。

应用场景

  1. 图的强连通分量：此算法常用于找出图中所有的强连通分量，广泛应用于网络分析、社交网络中发现社群、推荐系统等领域。
  2. 求解有向图的拓扑排序：强连通分量可以用于图的压缩，之后可以进行拓扑排序。
  3. 求解网络流问题：在流网络中，Tarjan算法可以帮助找到强连通分量并用来分解问题。

总结

Tarjan算法通过DFS和回溯机制，能够高效地找到图中的所有强连通分量。它适用于静态图，并且在时间复杂度和空间复杂度上都非常优秀，适合用于离线查询。

6. 扩展内容

Tarjan 算法不仅限于查找强连通分量，它还可以扩展到其他图论问题中，例如：

  • 最小割问题：通过寻找图中的强连通分量，可以进一步求解图中的最小割。
  • 图的压缩与简化：将一个图简化为其强连通分量图，使得图的结构更加紧凑，便于进一步的计算。
  • 网络分析：通过计算社交网络或通信网络的强连通分量，分析网络中具有强依赖关系的节点。

7. 总结

Tarjan 算法是一个经典的图算法，具有较高的效率和广泛的应用。它通过深度优先搜索和回退机制，能够在时间复杂度为 O(V + E) 的情况下，准确地识别图中的所有强连通分量。在实际应用中，这种算法非常适用于社交网络分析、路径规划、通信网络的可靠性分析等领域。

如果你需要更详细的介绍、复杂示例或更长的篇幅，欢迎继续询问！

Tarjan与LCA问题

一、LCA问题概述

LCA问题是一个经典的树形问题，指的是在给定一棵树的情况下，给定两个节点，求其最低公共祖先（Lowest Common Ancestor）。也就是说，给定树的两个节点u和v，LCA就是距离u和v最远的公共祖先。

LCA问题在很多图算法、树形DP等问题中都有广泛的应用。解决LCA问题的常见算法包括Tarjan算法和倍增法。

二、Tarjan算法与倍增法的对比

特性 Tarjan算法 倍增法（Binary Lifting）
时间复杂度 O(V + E) O(log V)（预处理时间O(V * log V)，查询时间O(log V)）
空间复杂度 O(V + E) O(V * log V)
适用场景 动态图，离线查询 静态树，离线或在线查询
查询效率 在离线问题中非常高效 对于多个在线查询来说非常高效
优缺点 适用于图的动态变化，比较复杂 预处理耗时，查询时高效

Tarjan算法

Tarjan算法主要基于并查集（Union-Find）数据结构，用来处理树中多个节点之间的LCA问题。该算法通过DFS对树进行遍历，并使用并查集来动态地记录每个节点的祖先。它最常用于离线LCA查询，即先进行树的遍历，然后根据查询结果返回答案。

Tarjan算法工作原理：

  1. 初始化：初始化一个并查集来记录树中每个节点的祖先。
  2. DFS遍历：通过DFS遍历树，将节点加入栈，并在遍历过程中更新每个节点的祖先信息。
  3. 查询过程：对于每个查询，Tarjan算法会在DFS的过程中更新并查集的状态，并返回对应节点的LCA。

代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 100005;
int n, m;
vector<int> adj[MAXN];
int parent[MAXN], ancestor[MAXN], depth[MAXN];
int findAncestor(int x) {
    if (x != parent[x]) {
        parent[x] = findAncestor(parent[x]);
    }
    return parent[x];
}

void tarjanDFS(int u) {
    ancestor[u] = u;  // The root of this node is itself
    for (int v : adj[u]) {
        tarjanDFS(v);
        parent[v] = u;
    }
    // Perform LCA queries
    // The ancestor processing and query answers happen here
}

int main() {
    // Read the tree structure
    cin >> n >> m;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // Call DFS to start Tarjan's algorithm
    tarjanDFS(1);
    return 0;
}

倍增法（Binary Lifting）

倍增法是一种高效的LCA查询方法，特别适合树结构的静态问题。在该方法中，我们预处理树的每个节点，使得每个节点能够跳跃到它的祖先，步数从1跳到2、4、8，直到跳到根节点。这使得在查询过程中，我们能够在O(log n)的时间内找到两个节点的LCA。

倍增法工作原理：

  1. 预处理：我们对于树的每一个节点，预处理一个大小为log(n)的表，其中每个节点的表项dp[i][j]表示从节点i跳跃2^j步能到的节点。
  2. 查询：给定两个节点u和v，我们从这两个节点分别跳跃，直到它们到达同一个祖先节点，这个节点即为它们的LCA。

代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

const int MAXN = 100005;
const int LOG = 20;  // Log size (assuming the maximum n is 100000)
vector<int> adj[MAXN];
int parent[MAXN][LOG], depth[MAXN];

void dfs(int u, int p) {
    parent[u][0] = p;  // Set parent of u
    for (int i = 1; i < LOG; i++) {
        if (parent[u][i-1] != -1)
            parent[u][i] = parent[parent[u][i-1]][i-1];
    }
    for (int v : adj[u]) {
        if (v != p) {
            depth[v] = depth[u] + 1;
            dfs(v, u);
        }
    }
}

int lca(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);  // Ensure u is deeper than v

    // Bring u and v to the same depth
    for (int i = LOG-1; i >= 0; i--) {
        if (depth[u] - (1 << i) >= depth[v]) {
            u = parent[u][i];
        }
    }
    if (u == v) return u;

    // Binary lifting
    for (int i = LOG-1; i >= 0; i--) {
        if (parent[u][i] != parent[v][i]) {
            u = parent[u][i];
            v = parent[v][i];
        }
    }
    return parent[u][0];  // LCA is the parent of u (or v) after lifting
}

int main() {
    int n, q;
    cin >> n >> q;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // Initialize parent and depth arrays
    dfs(1, -1);

    // Process LCA queries
    while (q--) {
        int u, v;
        cin >> u >> v;
        cout << lca(u, v) << endl;
    }

    return 0;
}

三、二者对比

  1. 适用场景：

    • Tarjan算法：适用于离线查询，即所有的LCA查询都事先给定，可以在DFS中一次性求解。适用于图动态变化（例如动态添加边）。
    • 倍增法：适用于静态树，并且是在线查询的理想选择。对于大量的LCA查询，倍增法能提供高效的查询速度。

  2. 时间复杂度：

    • Tarjan算法：在处理离线LCA查询时，时间复杂度为 **O(V + E)**，其中V是节点数，E是边数。查询过程是O(1)，因为它是在树的遍历过程中进行的。
    • 倍增法：预处理阶段的时间复杂度是 **O(V * log V)**，查询阶段的时间复杂度为 **O(log V)**。对于大规模的查询，倍增法的查询效率非常高。

  3. 空间复杂度：

    • Tarjan算法：使用并查集和DFS栈，空间复杂度为 **O(V + E)**。
    • 倍增法：需要存储每个节点的多个祖先，空间复杂度为 **O(V * log V)**。

  4. 预处理和查询的效率：

    • Tarjan算法：适用于离线场景，能够高效地处理动态图中的多个LCA查询。
    • 倍增法：虽然预处理阶段较为复杂，但查询速度非常高，适合在线查询。

四、总结

  • Tarjan算法通过DFS和并查集结合，能够在离线环境下高效地解决LCA问题，尤其适合动态图的处理。
  • 倍增法（Binary Lifting）适合静态树的问题，预处理需要O(V * log V)的时间，但查询速度非常快，是在线查询的最佳选择。
  • Title: Tarjan算法
  • Author: YZY
  • Created at : 2025-07-02 02:14:49
  • Updated at : 2025-07-02 02:14:49
  • Link: https://blog.dtoj.team/2025/07/02/Tarjan/
  • License: 三金家的Y同学
On this page
Tarjan算法
  1. 1. 强连通分量（SCC）
  2. 2. Tarjan 算法的核心思想
  3. 3. 算法细节
  4. 4. Tarjan 算法的应用
  5. 5. 代码实现
  6. C++实现
  7. 代码解释
  8. 算法复杂度分析
  9. 应用场景
  10. 总结
  11. 6. 扩展内容
  12. 7. 总结
  • Tarjan与LCA问题
    1. 一、LCA问题概述
    2. 二、Tarjan算法与倍增法的对比
    3. 倍增法（Binary Lifting）
    4. 三、二者对比
    5. 四、总结