有向图的强连通分支之朴素求法---利用深搜

缘起

在【1】中我们给出了有向图强连通的定义. 因此我们对有向图的强连通分量很感兴趣. 本文就是要给出程序求出有向图的强连通分量。 本算法其实就是kosaraju算法.

分析

算法的核心基于如下事实. 从顶点v出发深搜能到达的顶点集U与从顶点v出发沿着逆图深搜能到达的顶点集V的交集就是包含v的强连通分量. 其中所谓逆图指的是顶点和原图一致，而边的方向是相反的. 这叫做逆图.

证明该事实是容易的. 因为如果还有真包含于该集合的顶点集的话, 多余的顶点就应该被v搜索到. 则与深搜矛盾. 所以貌似算法是下面的

遍历所有的点, 每个点求出原图深搜结果集与沿着逆图深搜结果集的交集.

貌似很有道理，但是槽点很多.

  1. 每个点都求交集，是不是算法复杂度高了点?
  2. 会不会算重复?

所以我们使用如下改进的算法. 可以不用求交集. 令原图为G，逆图为G’

按照常规方法, 求出有向图的深搜森林. 但是要加一个数组 finished, 一个顶点什么时候才进入该数组? 就在从它出发的所有顶点都遍历过后从它退出的时候将其加入数组. 此finished数组有如下重要性质.

finished[i]能沿着G到达finished[0,…,i-1]中任何顶点

这是一个重要性质，它直接导致了我们不需要求交集.

其次，我们按照finished[n-1,…,0]这个顺序运行G’上的深搜. 因为每个节点至少自己属于包含自己的强连通分支. 所以不难知道, 运行完finished[i] 之后删除该节点之后（即标记 isvisited[i]为true）之后，finished[i-1]沿G’深搜到的顶点一定在finished[0,…,i-2]中.记做S， 这就有趣了——根据上面说的性质，finished[i]沿G一定可以到达S, 而finished[i]沿G’也可以到达S, 所以S就是一个包含finished[i]的强连通子集. 注意，这个强连通子集不可能包含finished[i+1,…]中的顶点. 否则的话, 在finished[i+1,…]上的顶点运行深搜的时候, 就会将S中的点标记为isvisited为true. 则就不可能有运行finished[i]为入口的dfs了. 所以S是包含finished[i]的连通分支. 这样我们就不难写出如下基于深搜的求有向图的强连通分支的算法. 显然, 因为涉及逆图的使用, 所以采用十字链表法作为存储图的模型是合适的.

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
#include "stdafx.h"
#include <iostream>
#pragma warning(disable:4996) // 防止scanf 等不带_s的api报错
#include <vector>

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

struct Graph // 十字链表法
{
	int n; // 图实际的顶点个数
	vector<int> in[MAX_VERTEX_NUM]; // 入边
	vector<int> out[MAX_VERTEX_NUM]; // 出边

	vector<int> cc[MAX_VERTEX_NUM]; // 强连通分支

	Graph()
	{
		puts("输入顶点的个数");
		scanf("%d", &n);
		int start, end;
		puts("输入边的起点和终点, 起点在前, 终点在后, 不同边换行");
		while(~scanf("%d%d", &start, &end))
		{
			out[start].push_back(end);
			in[end].push_back(start);
		}
	}

	bool isvisited[MAX_VERTEX_NUM]; // 访问标志数组
	int finished[MAX_VERTEX_NUM];  // 搜索顺序
	int cnt; // 目前进入finished数组的元素的个数
	int cccount; // 强连通分支的个数

	void getcc() // 求有向图的强连通分支
	{
		memset(isvisited, 0, sizeof(isvisited));
		memset(finished, -1, sizeof(finished));
		cnt = cccount = 0;
		for (int i = 0; i<n;i++)
		{
			if (!isvisited[i])
			{
				dfs(i);
			}
		} // 此for循环结束, finished[0,..,n-1] 就会是深搜森林
		memset(isvisited, 0, sizeof(isvisited)); // 重置
		for (int i = n-1; ~i; i--)
		{
			if (!isvisited[finished[i]])
			{
				cccount++;
				dfs_reverse(finished[i]);
			}
			
		}
	}

private:

	void dfs(int cur) // 顺向dfs
	{
		isvisited[cur] = true;
		for (it x = out[cur].begin(); x!=out[cur].end(); x++)
		{
			if (!isvisited[*x])
			{
				dfs(*x);
			}
		}
		finished[cnt++] = cur; // 只有等待所有cur的孩子们遍历完. 回到cur之后，cur才进去
	}

	void dfs_reverse(int cur) // 沿逆图dfs
	{
		isvisited[cur] = true;
		cc[cccount].push_back(cur);
		for (it x = in[cur].begin(); x!=in[cur].end(); x++)
		{
			if (!isvisited[*x])
			{
				dfs_reverse(*x);
			}
		}
	}

};

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	Graph g;
	g.getcc();
	printf("一共%d个强连通分支\n", g.cccount);
	for (int i= 1; i<=g.cccount; i++)
	{
		for (it x = g.cc[i].begin(); x!=g.cc[i].end(); x++)
		{
			cout<<*x;
		}
		puts("");
	}
	return 0;
}
/*
测试数据
5
4 0
0 1
3 1
3 0
0 2
2 3
3 2
2 0
*/

关于kosaraju算法，进一步论述见【2】.

参考

【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/09/07/POJ-2186-Popular-Cows-scc%E7%9A%84%E4%B8%89%E7%A7%8D%E5%A7%BF%E5%8A%BF/