学步园

  这东西,写了8小时.比较慢了.实现是一步一步地完成的.方法概述如下:

  1.对原图进行一次深度优先搜索,以后序对各顶点标号.

  2.将原图反转.

  3.在新图中,按照顶点标号从大到小的顺序对所有顶点逐个检查,并进行深度优先搜索.每一次调用深度优先搜索之后,下次调用时到调用结束阶段,声场的深度优先搜索树中的所有节点是强联通的.

  这个的原理书上说得我看不懂.我理解就是,新图中能够访问到的,在原图中以反向也能够访问到.于是所构成的集合是强连通的.至于使用后序标号,是保证能够按照将图反转前的访问方向的反向访问反转后的图.

   贴代码吧,能够写出来,我很高兴了.

/* 9-27-12-23-22.26.c -- 第九章第二十七题 */<br /> #include <stdio.h><br /> #include "new_adjacenty_list.h"</p> <p>#define SIZE (7)</p> <p>int visited[SIZE], postorder[SIZE] ;<br /> int count = 0, kind = 1 ;</p> <p>int mian (void) ;<br /> void initialize_graph (Adjacenty_List * const padj, Hash_Table * const pht) ;<br /> void initialize_array (int * const array, const int size, const int value) ;<br /> void search_all (const Adjacenty_List * const padj, const Hash_Table * const pht) ;<br /> void depth_first_search (const Adjacenty_List * const padj, const Hash_Table * const pht, const int index) ;<br /> void depth_first_search_without_number (const Adjacenty_List * const padj, const Hash_Table * const pht, const int index) ;<br /> void invert_graph (Adjacenty_List * const padj, const Hash_Table * const pht) ;<br /> void find_connected (const Adjacenty_List * const padj, const Hash_Table * const pht) ;<br /> void print_result (const Adjacenty_List * const padj, const Hash_Table * const pht) ;</p> <p>int main (void)<br /> {<br /> Adjacenty_List adj ;<br /> Hash_Table ht ;<br /> int capacity = SIZE ;</p> <p> Initialize_A (&adj, capacity) ;<br /> Initialize_H (&ht, capacity * 2) ;</p> <p> initialize_array (visited, capacity, FALSE) ;<br /> /* Initialize the graph */<br /> initialize_graph (&adj, &ht) ;<br /> /* Reverse the graph */<br /> Reverse_A (&adj, &ht) ;<br /> /* Number it */<br /> search_all (&adj, &ht) ;<br /> initialize_array (visited, capacity, FALSE) ;<br /> find_connected (&adj, &ht) ;<br /> print_result (&adj, &ht) ;</p> <p> Release_A (&adj) ;<br /> Release_H (&ht) ;</p> <p> return 0 ;<br /> }</p> <p>void initialize_graph (Adjacenty_List * const padj, Hash_Table * const pht)<br /> {<br /> InitializeALine_A (padj, pht, 0, 'a', 0, 4, 'b', 0, 'c', 0) ;<br /> InitializeALine_A (padj, pht, 1, 'b', 0, 6, 'c', 0, 'e', 0, 'g', 0) ;<br /> InitializeALine_A (padj, pht, 2, 'c', 0, 4, 'd', 0, 'e', 0) ;<br /> InitializeALine_A (padj, pht, 3, 'd', 0, 4, 'a', 0, 'f', 0) ;<br /> InitializeALine_A (padj, pht, 4, 'e', 0, 4, 'd', 0, 'f', 0) ;<br /> InitializeALine_A (padj, pht, 5, 'f', 0, 0) ;<br /> InitializeALine_A (padj, pht, 6, 'g', 0, 2, 'e', 0) ;<br /> }</p> <p>void initialize_array (int * const array, const int size, const int value)<br /> {<br /> int i ;</p> <p> for (i = 0; i < size; i++)<br /> array[i] = value ;<br /> }</p> <p>void search_all (const Adjacenty_List * const padj, const Hash_Table * const pht)<br /> {<br /> int i, size ;</p> <p> for (i = 0, size = (*padj) -> capacity; i < size; i++)<br /> {<br /> if (FALSE == visited[i])<br /> depth_first_search (padj, pht, i) ;<br /> }<br /> }</p> <p>void depth_first_search (const Adjacenty_List * const padj, const Hash_Table * const pht, const int index)<br /> {<br /> Adjoin_To_Vertex * scan ;<br /> int w ;</p> <p> visited[index] = TRUE ;<br /> scan = (*padj) -> list[index].adjoin_to ;<br /> while (scan)<br /> {<br /> w = (*pht) -> lists[scan -> hash_value].index_in_adjacenty_list ;<br /> if (FALSE == visited[w])<br /> depth_first_search (padj, pht, w) ;<br /> scan = scan -> next ;<br /> }<br /> postorder[count++] = (*padj) -> list[index].hash_value ;<br /> }</p> <p>void depth_first_search_without_number (const Adjacenty_List * const padj, const Hash_Table * const pht, const int index)<br /> {<br /> Adjoin_To_Vertex * scan ;<br /> int w ;</p> <p> visited[index] = kind ;<br /> scan = (*padj) -> list[index].adjoin_to ;<br /> while (scan)<br /> {<br /> w = (*pht) -> lists[scan -> hash_value].index_in_adjacenty_list ;<br /> if (FALSE == visited[w])<br /> depth_first_search_without_number (padj, pht, w) ;<br /> scan = scan -> next ;<br /> }<br /> }</p> <p>void find_connected (const Adjacenty_List * const padj, const Hash_Table * const pht)<br /> {<br /> int i, size ;</p> <p> /* The first element in the array is visited in the end */<br /> for (i = 0, size = (*padj) -> capacity; i < size; i++)<br /> {<br /> if (FALSE == visited[(*pht) -> lists[postorder[i]].index_in_adjacenty_list])<br /> {<br /> depth_first_search_without_number (padj, pht, (*pht) -> lists[postorder[i]].index_in_adjacenty_list) ;<br /> kind++ ;<br /> }<br /> }<br /> }</p> <p>void print_result (const Adjacenty_List * const padj, const Hash_Table * const pht)<br /> {<br /> int i, size ;</p> <p> for (i = 0, size = (*padj) -> capacity; i < size; i++)<br /> printf ("%c is in gather %d./n", (*pht) -> lists[(*padj) -> list[i].hash_value].name, visited[i]) ;<br /> }