Namikawa

Tarjan算法

发布 : 2020-06-24 分类 : Tarjan 浏览 :

Tarjan 算法是一种由 Robert Tarjan 提出的求解有向图强连通分量的算法，它能做到线性时间的复杂度。

有如下定义：

如果两个顶点可以相互通达，则称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通，称G是一个强连通图。有向图的极大强连通子图，称为强连通分量(strongly connected components)。

Tarjan 算法是基于对图深度优先搜索的算法，每个强连通分量为搜索树中的一棵子树。搜索时，把当前搜索树中未处理的节点加入一个堆栈，回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。

在 Tarjan 算法中，有如下定义。

dfn[i] : 在DFS中该节点被搜索的次序(时间戳)

low[i] : 为 i 或 i 的子树能够追溯到的最早的栈中节点的次序号

当 dfn[i] == low[i] 时，为 i 或 i 的子树可以构成一个强连通分量。

另一种解释：

dfn[i]：就是一个时间戳（被搜到的次序），一旦某个点被DFS到后，这个时间戳就不再改变（且每个点只有唯一的时间戳）。所以常根据dfn的值来判断是否需要进行进一步的深搜。

low[i]：该子树中，且仍在栈中的最小时间戳，像是确立了一个关系，low[i] 相等的点在同一强连通分量中。

注意初始化时 dfn[i] = low[i] = ++cnt.

算法思路：

首先这个图不一定是一个连通图，所以跑 Tarjan 时要枚举每个点，若 dfn[i] == 0，进行深搜。

然后对于搜到的点寻找与其有边相连的点，判断这些点是否已经被搜索过，若没有，则进行搜索。若该点已经入栈，说明形成了环，则更新 low.

在不断深搜的过程中如果没有路可走了（出边遍历完了），那么就进行回溯，回溯时不断比较 low[i]，去最小的 low 值。如果dfn[x] == low[x] 则x可以看作是某一强连通分量子树的根，也说明找到了一个强连通分量，然后对栈进行弹出操作，直到 x 被弹出。

详细请看这里

如果还没懂是什么意思，再给出一种解释：

dfn[i] 表示在DFS回溯的前提下，该结点 vi 被遍历的时间先后顺序，也就是时间戳，顺序递增。

low[i] 表示在DFS回溯的前提下，该结点 vi 不通过父结点时到达 vi 这条边所能连通的顶点时间戳的最小值。初始 low[i] = dfn[i]。

DFS处理到末尾后向前回溯，同时维护：(因为可以由 father 到 children 再到 children 所能连通的顶点时间戳的最小值，并没有通过 father 的 father)

low[father] = min{ low[father], low[children] }.

dfn 和 low 都处理完毕后：

设一个父结点 vf 的所有子结点 v ci，0 <= i <= k。k 是 vf 的子结点总数。

若存在 low[ci] >= dfn[vf]，则 vf 是割点；

若存在 low[ci] > dfn[vf]，则 e f-ci 是割边。

这也正说明了一个图中割边的数量永远不会超过割点的数量。

Tarjan 算法仅用两次DFS回溯就可以得到所有割点和割边，不必暴力枚举，对于无向图 G(V, E) 的时间复杂度是 O(|V| + |E|).

两篇很详细的文章：

https://www.jianshu.com/p/844aa43b23ab

https://blog.csdn.net/qq_34374664/article/details/77488976

算法模板

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
void tarjan(int now)
{
    dfn[now] = low[now] = ++cnt;  //初始化
    stack[++t] = now;　　　　　　 //入栈操作
    v[now] = 1;　　　　　　　　    //v[i]代表该点是否已入栈
    for(int i = f[now]; i != -1; i = e[i].next)  //邻接表存图
        if(!dfn[e[i].v]) 　　　　　　　　　 //判断该点是否被搜索过，若没有
        {
            tarjan(e[i].v);
            low[now] = min(low[now], low[e[i].v]); //回溯时更新low[i]，取最小值
        }
        else if(v[e[i].v])                      //若访问过，并且还在栈里
            low[now] = min(low[now], dfn[e[i].v]); //一旦遇到已入栈的点，就将该点作为连通量的根
　　　　　　　　　　　　　　　　　　　　　　　　　　　　 //这里用dfn[e[i].v]更新的原因是：这个点可能
　　　　　　　　　　　　　　　　　　　　　　　　　　　　 //已经在另一个强连通分量中了但暂时尚未出栈，所
　　　　　　　　　　　　　　　　　　　　　　　　　　　　 //以now不一定能到达low[e[i].v]但一定能到达
　　　　　　　　　　　　　　　　　　　　　　　　　　　　 //dfn[e[i].v].
    if(dfn[now] == low[now])
    {
        int cur;
        do
        {
            cur = stack[t--];
            v[cur] = false;                       //不要忘记出栈
        }while(now != cur);
    }
}

具体实现

复杂版

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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

const int maxn = 1e3 + 10;
const int maxm = 1e6 + 10;

int tst;    // timestamp
int N, M;   // 顶点数N，边数M

struct Edge {
    int from, to;
    Edge(int f = 0, int t = 0):
        from(f), to(t) { }
    ~Edge() { }
};

// adj-list undirected graph
// idx -> even with compone idx + 1.
vector<Edge> edges;    //所有边的集合
vector<int> ver[maxn]; //记录每一个顶点出发的边在edges中的索引
int dfn[maxn];
int low[maxn];

vector<int> verCut;    //割点集
vector<Edge> edgeCut;  //割边集

/**
 * @brief 读取数据，以邻接表方式储存，因为是无向图需要一条边存两次
 *        第1行输入N和M表示图的顶点数和边数
 *        接下来第2到第M + 1行输入from和to表示无向图的一条边的两个顶点.
 */
void readData() {
    cin >> N >> M;
    for (int inc = 0; inc < M; inc ++) {
        int from = 0, to = 0;
        cin >> from >> to;
        ver[from].push_back(edges.size());
        edges.push_back(Edge(from, to));
        ver[to].push_back(edges.size());
        edges.push_back(Edge(to, from));
    }
}

/**
 * @brief DFS回溯上标签
 * @param curr_ver 当前顶点的编号
 * @param fa_ver   当前顶点的父亲编号，根节点父亲设为-1
 */
void labelling(int curr_ver = 0, int fa_ver = -1) {
    dfn[curr_ver] = low[curr_ver] = ++tst;  //初始化dfn和low
    for (vector<int>::iterator iter = ver[curr_ver].begin();
        iter != ver[curr_ver].end(); iter ++) {
        if (edges[*iter].to == fa_ver)
            continue;
        if (!low[edges[*iter].to]) {
            labelling(edges[*iter].to, curr_ver);
        }
        low[curr_ver] = min(low[curr_ver], low[edges[*iter].to]);
    }
}

/**
 * @brief 收集统计割点及割边
 */
void collect(int curr_ver = 0, int fa_ver = -1) {
    tst++;
    bool is_vercut = false;
    for (vector<int>::iterator iter = ver[curr_ver].begin();
         iter != ver[curr_ver].end(); iter++) {
        if (edges[*iter].to == fa_ver || dfn[edges[*iter].to] != tst + 1)
            continue;
        collect(edges[*iter].to, curr_ver);
        int sub = low[edges[*iter].to] - dfn[curr_ver];
        is_vercut = (sub >= 0);
        if (sub > 0) {
            edgeCut.push_back(Edge(curr_ver, edges[*iter].to));
        }
    }
    if (is_vercut) {
        verCut.push_back(curr_ver);
    }
}

/**
 * @brief tarjan算法，包含两个子函数，调用函数前需要将时间戳重置
 */
void tarjan() {
    tst = 0;
    labelling();

    tst = 0;
    collect();
}

void show() {
    cout << "vertex cut(s):" << endl;
    cout << "total: " << verCut.size() << endl;
    for (vector<int>::iterator iter = verCut.begin();
        iter != verCut.end(); iter ++) {
        cout << (*iter) << endl;
    }

    cout << "edge cut(s):" << endl;
    cout << "total: " << edgeCut.size() << endl;
    for (vector<Edge>::iterator iter = edgeCut.begin();
         iter != edgeCut.end(); iter ++) {
        cout << (*iter).from << " to " << (*iter).to << endl;
    }
}

int main() {
    //freopen("Tarjan.txt", "r", stdin);

    readData();

    tarjan();

    show();

    return 0;
}

/*****测试数据******
6 6
0 1
1 3
3 4
4 5
1 4
1 2
*******************/

简易版

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
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int maxn = 1001;

struct node{
    int c;
    int next;
}edge[maxn];

int low[maxn], dfn[maxn];
int stack[maxn], heads[maxn], visit[maxn]; //head配合结构体前向星
int cnt, dep, idx;

void addEdge(int x, int y){
    edge[++cnt].next = heads[x];
    edge[cnt].c = y;
    heads[x] = cnt;
}

void Tarjan(int u){  //代表第几个点在处理,递归的是点
    dfn[u] = low[u] = ++dep;  //新进点的初始化
    stack[++idx] = u;
    visit[u] = 1;
    for(int i = heads[u]; i != -1; i = edge[i].next){
        if(!dfn[edge[i].c]){
            Tarjan(edge[i].c);
            low[u] = min(low[u], low[edge[i].c]);  //递归出来，比较谁是谁的儿子／父亲，就是树的对应关系，涉及到强连通分量子树最小根的事情
        }
        else if(visit[edge[i].c]){
            low[u] = min(low[u], dfn[edge[i].c]);   //比较谁是谁的儿子／父亲,就是链接对应关系
        }
    }
    if(low[u] == dfn[u]){  //发现是整个强连通分量子树里的最小根
        do{
            cout << stack[idx] << " ";
            visit[stack[idx]] = 0;
            idx--;
        }while(u != stack[idx + 1]);
        cout << endl;
    }
}

int main(){
    memset(heads, -1, sizeof(heads));
    int n, m;
    cin >> n >> m;
    int x, y;
    for(int i = 0; i < m; i++){
        cin >> x >> y;
        addEdge(x, y);
    }
    for(int i = 1; i <= n; i++){
        if(!dfn[i])
            Tarjan(i);
    }
    return 0;
}

/*
Input:
6 8
1 3
1 2
2 4
3 4
3 5
4 6
4 1
5 6
Output:
6
5
3 4 2 1
*/

本文作者 : preccrep
原文链接 : https://preccrep.github.io/2020/06/24/Tarjan%E7%AE%97%E6%B3%95/
版权声明 : 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处！
留下足迹

博客已萌萌哒运行(●'◡'●)ﾉ♥
Theme - BMW | Made With 💗 | Powered by GodBMW