有向图的强连通分支之Gabow算法

缘起

【1】中介绍了scc算法. 【2】和【3】分别给出了scc算法的两种实现. 即kosaraju和tarjan. 这里介绍一下最后一种常用的scc算法实现，即gabow算法.

分析

这里有必要提及一下

三种scc算法的思想都是

有向图可以剖分成深搜树（深搜树不交地组成深度优先生成森林），而深搜树剖分成强连通分支

Gabow算法和Tarjan算法的思想是一样的。每个强连通分量都有一个“根”，根是强连通分量中最先被检查的顶点。在一个强连通分量中，沿着根不断DFS，最终将会回到根，路上经过的顶点则属于这个强连通分量。

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
#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#pragma warning(disable:4996)

#define LOCAL
using namespace std;
const int MAX_NUM = 20;
typedef vector<int>::iterator it;

struct Graph
{
	int n;
	vector<int> vertex[MAX_NUM];
	vector<int> scc[MAX_NUM];
	int sccnum;
	stack<int> s,t; // 和tarjan算法的区别在于gabow使用了一个栈代替了low数组，不涉及数组的更新，而只涉及栈操作，所以gabow是三种scc算法中最快的,但是流程基本和tarjan类似
	bool isInstack[MAX_NUM];
	int timestamp[MAX_NUM];
	int index;

	Graph()
	{
		sccnum = index = 0;
		memset(isInstack,0,sizeof(isInstack));
		memset(timestamp,0,sizeof(timestamp));
		puts("输入顶点的个数");
		scanf("%d",&n);
		puts("输入各边的起点和终点, 起点在前, 终点在后");
		int start, end;
		while(~scanf("%d%d", &start, &end)) vertex[start].push_back(end);
	}

	void getscc() {for (int i = 0; i<n;i++) if (!timestamp[i]) gabow(i);}

private:

	void gabow(int i)
	{
		s.push(i);
		t.push(i);
		isInstack[i] =true;
		timestamp[i] = ++index;
		for (it x = vertex[i].begin(); x!=vertex[i].end(); x++)
		{
			if (!timestamp[*x]) gabow(*x);
			else if (isInstack[*x]) // *x 可能在t中, 也可能不在, 但是一定在s中
			{
				while(timestamp[t.top()]>timestamp[*x]) // 将t中后面的弹出去.
				{
					t.pop();
				}
			}// 如果已经搜过，但是尚在栈中, 表明出现了环, 则就要弹栈, 但是*x不会出栈
		}
		if (i==t.top()) // 退回到i本身, 如果t的栈顶就是i的话, 表明已经出现了一个scc
		{
			t.pop();
			while(s.top()!=i)  // 注意, 这里不能使用do... while, 否则的话, 如果i就是s的栈顶的话, 先pop出去了,后面就和i再也不等了，则就有问题了
			{
				scc[sccnum].push_back(s.top());
				isInstack[s.top()] = false;
				s.pop();
			}
			scc[sccnum].push_back(i);
			isInstack[i] = false;
			s.pop();
			sccnum++;
		}
	}
};

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in","r",stdin);
#endif
	Graph g;
	g.getscc();
	return 0;
}
/*
测试数据
5
4 0
0 1
3 1
3 0
0 2
2 3
3 2
2 0
*/

参考

【1】https://yfsyfs.github.io/2019/05/22/%E6%9C%89%E5%90%91%E5%9B%BE%E7%9A%84%E5%BC%BA%E8%BF%9E%E9%80%9A%E5%88%86%E6%94%AF/

【2】

https://yfsyfs.github.io/2019/05/22/%E6%9C%89%E5%90%91%E5%9B%BE%E7%9A%84%E5%BC%BA%E8%BF%9E%E9%80%9A%E5%88%86%E6%94%AF%E4%B9%8BKosaraju%E7%AE%97%E6%B3%95/

【3】https://yfsyfs.github.io/2019/05/22/%E6%9C%89%E5%90%91%E5%9B%BE%E7%9A%84%E5%BC%BA%E8%BF%9E%E9%80%9A%E5%88%86%E6%94%AF%E4%B9%8BTarjan%E7%AE%97%E6%B3%95/