有向圖強(qiáng)連通分支就是這樣一個最大的頂點(diǎn)集合C，其中的任意一對頂點(diǎn)u和v，u可達(dá)v，并且v可達(dá)u。
kosaraju算法是求有向圖強(qiáng)連通分支的有效算法。起基本思想就是兩次DFS，說起來簡單，但是如何證明其兩次DFS是能成功求出強(qiáng)連通分支的呢？
1、對圖G第一次DFS遍歷完成之后，會形成若干個DFS樹，它們組成森林，假設(shè)有C1，C2，C3...Ck棵DFS樹，而且遍歷完成時間C1<C2<C3<...<Ck，這樣，可知必然不存在從Ci到Cj的邊（其中i<j），因?yàn)槿绻嬖贑i->Cj則假設(shè)這條邊是從Ci的x節(jié)點(diǎn)到Cj的y節(jié)點(diǎn)，則由白色路徑定理可知，必然存在一條從Ci到Cj的白色路徑，則Cj會是Ci的一棵子樹！所以不存在從Ci到Cj的邊（其中i<j）。
2、當(dāng)把圖G的所有邊逆向之后，設(shè)形成圖F，則由1可知不存在從Cj到Ci的路徑，這樣，對圖F按照第一次DFS遍歷時各個節(jié)點(diǎn)的完成時間由大到小進(jìn)行DFS遍歷，即從Ck的樹根r開始遍歷：首先根據(jù)前面的論證需要明確一個事實(shí)，r所在的強(qiáng)連通分支的點(diǎn)集必然屬于樹Ck，因?yàn)椴淮嬖趶腃k到Ca（a<k）的邊，另外就是r到Ck中所有節(jié)點(diǎn)都是可達(dá)的，這樣當(dāng)對圖G的逆圖F從r點(diǎn)開始遍歷的時候，所有可到達(dá)的點(diǎn)在圖G中都是可到達(dá)r的！這樣遍歷結(jié)果就是r所在的強(qiáng)連通分支！然后在從剩下沒有遍歷過的所有節(jié)點(diǎn)中第一次DFS的完成時間最大的點(diǎn)開始遍歷，因?yàn)槭Ｏ碌狞c(diǎn)都為白色（可能會存在白色點(diǎn)指向從r形成的強(qiáng)連通分支的反向邊），所以與Ck的根r類似，同樣能形成一個強(qiáng)連通分支，這樣就能把Ck中的所有強(qiáng)連通分支找出，同樣可以找出Ck-1...C1中的強(qiáng)連通分支。
證畢！
證明如果能看懂的話那代碼就非常簡單了，下面是示例代碼：
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()。這里利用一個棧來保存每個節(jié)點(diǎn)的完成先后順序，第二次遍歷的時候就按照最后完成的節(jié)點(diǎn)開始向前遍歷。
posted on 2012-08-22 21:28
myjfm 閱讀(1140)
評論(0) 編輯 收藏 引用 所屬分類:
算法基礎(chǔ)