有向图强连通分支就是这样一个最大的顶点集合C，其中的任意一对顶点u和v，u可达v，并且v可达u。
kosaraju算法是求有向图强连通分支的有效算法。起基本思想就是两次DFS，说起来简单，但是如何证明其两次DFS是能成功求出强连通分支的呢？
1、对图G第一次DFS遍历完成之后，会形成若干个DFS树，它们组成森林，假设有C1，C2，C3...Ck棵DFS树，而且遍历完成时间C1<C2<C3<...<Ck，这样，可知必然不存在从Ci到Cj的边（其中i<j），因为如果存在Ci->Cj则假设这条边是从Ci的x节点到Cj的y节点，则由白色路径定理可知，必然存在一条从Ci到Cj的白色路径，则Cj会是Ci的一棵子树！所以不存在从Ci到Cj的边（其中i<j）。
2、当把图G的所有边逆向之后，设形成图F，则由1可知不存在从Cj到Ci的路径，这样，对图F按照第一次DFS遍历时各个节点的完成时间由大到小进行DFS遍历，即从Ck的树根r开始遍历：首先根据前面的论证需要明确一个事实，r所在的强连通分支的点集必然属于树Ck，因为不存在从Ck到Ca（a<k）的边，另外就是r到Ck中所有节点都是可达的，这样当对图G的逆图F从r点开始遍历的时候，所有可到达的点在图G中都是可到达r的！这样遍历结果就是r所在的强连通分支！然后在从剩下没有遍历过的所有节点中第一次DFS的完成时间最大的点开始遍历，因为剩下的点都为白色（可能会存在白色点指向从r形成的强连通分支的反向边），所以与Ck的根r类似，同样能形成一个强连通分支，这样就能把Ck中的所有强连通分支找出，同样可以找出Ck-1...C1中的强连通分支。
证毕！
证明如果能看懂的话那代码就非常简单了，下面是示例代码：
1 #include <cstdio>
2 #include <vector>
3
4 #define MAXN 105
5 #define ROOT 0
6
7 typedef struct {
8 std::vector<int> adj_list;
9 #define WHITE 0
10 #define GREY 1
11 #define BLACK 2
12 int color;
13 } GRAPH;
14
15 GRAPH graph[MAXN];
16 GRAPH rgraph[MAXN];
17 int nr_of_nodes = 0;
18 int nr_of_edges = 0;
19
20 static void init() {
21 int i;
22 for (i = 0; i < MAXN; ++i) {
23 graph[i].adj_list.clear();
24 graph[i].color = WHITE;
25 rgraph[i].adj_list.clear();
26 rgraph[i].color = WHITE;
27 }
28 nr_of_nodes = 0;
29 nr_of_edges = 0;
30 }
31
32 static void input() {
33 int i, u, v;
34 freopen("input", "r", stdin);
35 scanf("%d%d", &nr_of_nodes, &nr_of_edges);
36 for (i = 0; i < nr_of_edges; ++i) {
37 scanf("%d%d", &u, &v);
38 graph[u].adj_list.push_back(v);
39 rgraph[v].adj_list.push_back(u);
40 }
41 }
42
43 static void DFS(GRAPH* g, int x, std::vector<int>* list) {
44 int i;
45 g[x].color = GREY;
46 for (i = 0; i < g[x].adj_list.size(); ++i) {
47 if (g[g[x].adj_list[i]].color == WHITE) {
48 DFS(g, g[x].adj_list[i], list);
49 }
50 }
51 g[x].color = BLACK;
52 list->push_back(x);
53 }
54
55 static void strong_connected_components() {
56 int i, j;
57 std::vector<int> vertexes
58 std::vector<int> scc;
59 std::vector<std::vector<int> > sccs;
60
61 for (i = 0; i < nr_of_nodes; ++i) {
62 if (graph[i].color == WHITE) {
63 DFS(graph, i, &vertexes);
64 }
65 }
66
67 for (i = vertexes.size() - 1; i >= 0; --i) {
68 if (rgraph[vertexes[i]].color == WHITE) {
69 DFS(rgraph, vertexes[i], &scc);
70 sccs.push_back(scc);
71 scc.clear();
72 }
73 }
74
75 for (i = 0; i < sccs.size(); ++i) {
76 printf("strong connected component %d: ", i);
77 for (j = 0; j < sccs[i].size(); ++j) {
78 printf("%d ", sccs[i][j]);
79 }
80 printf("\n");
81 }
82 }
83
84 int main(int argc, const char **argv) {
85 init();
86 input();
87 strong_connected_components();
88 return 0;
89 }
90
91
核心部分代码就是strong_connected_components()和DFS()。这里利用一个栈来保存每个节点的完成先后顺序，第二次遍历的时候就按照最后完成的节点开始向前遍历。
posted on 2012-08-22 21:28
myjfm 阅读(1074)
评论(0) 编辑 收藏 引用 所属分类:
算法基础