学步园

  话说这个东西,写了不下12小时.我坚持写完了,并且写对了.我很高兴.

  通过写这个东西,加强了对寻找割点问题的认识,从而认识,并明白了寻找双连通分支的过程.

  我想要说明的是,深度优先搜索,深度优先.从 (v, w) 开始的深度优先搜索, 在回到调用 (v, w) 的那次调用之前, (w, v) 已经被处理过.这保证一条边不会入栈两次.同时, 也同时可以避免已被作为背向边处理的 (v, w) 入栈.这都是通过 if (!Find_L (pli, w, index))  来实现的.

  桥同样被打印出来,因为他确实是分支的一部分,有时不是分支的一部分,只是桥本身.这些是搜索知道的,现在,自己体会到了.

  好吧,希望我的代码,会给后人一些启示.

/* 9-29-12-25-21.36.c -- 第九章第二十九题 */<br /> #include <stdio.h><br /> #include "new_adjacenty_list.h"<br /> #include "stack.h"<br /> #include "linked_list.h"</p> <p>#define SIZE (10)<br /> #define START (0)</p> <p>int visited[SIZE], low[SIZE], number[SIZE], parent[SIZE] ;<br /> int counter = 1 ;</p> <p>int main (void) ;<br /> void initialize_array (int * const array, const int capacity) ;<br /> void build_graph (Adjacenty_List * const padj, const Hash_Table * const pht) ;<br /> void find_biconnected_component (const Adjacenty_List * const padj, const Hash_Table * const pht, const int index, Stack * const pst, List * const pli) ;<br /> int min (const int val1, const int val2) ;</p> <p>int main (void)<br /> {<br /> Adjacenty_List adj ;<br /> Hash_Table ht ;<br /> Stack stack ;<br /> List list ;<br /> int capacity = SIZE ;</p> <p> Initialize_A (&adj, capacity) ;<br /> Initialize_H (&ht, capacity * 2) ;<br /> Initialize_S (&stack, capacity * (capacity - 1)) ;<br /> Initialize_L (&list) ;</p> <p> initialize_array (visited, capacity) ;<br /> build_graph (&adj, &ht) ;</p> <p> find_biconnected_component (&adj, &ht, START, &stack, &list) ;</p> <p> Release_A (&adj) ;<br /> Release_H (&ht) ;<br /> Release_S (&stack) ;<br /> Release_L (&list) ;</p> <p> return 0 ;<br /> }</p> <p>void initialize_array (int * const array, const int capacity)<br /> {<br /> int i ;</p> <p> for (i = 0; i < capacity; i++)<br /> array[i] = FALSE ;<br /> }</p> <p>void build_graph (Adjacenty_List * const padj, const Hash_Table * const pht)<br /> {<br /> InitializeALine_A (padj, pht, 0, 'a', 0, 10, 'b', 0, 'c', 0, 'e', 0, 'h', 0, 'i', 0) ;<br /> InitializeALine_A (padj, pht, 1, 'b', 0, 6, 'a', 0, 'c', 0, 'd', 0) ;<br /> InitializeALine_A (padj, pht, 2, 'c', 0, 6, 'a', 0, 'b', 0, 'e', 0) ;<br /> InitializeALine_A (padj, pht, 3, 'd', 0, 2, 'b', 0) ;<br /> InitializeALine_A (padj, pht, 4, 'e', 0, 8, 'a', 0, 'c', 0, 'f', 0, 'g', 0) ;<br /> InitializeALine_A (padj, pht, 5, 'f', 0, 4, 'e', 0, 'g', 0) ;<br /> InitializeALine_A (padj, pht, 6, 'g', 0, 4, 'e', 0, 'f', 0) ;<br /> InitializeALine_A (padj, pht, 7, 'h', 0, 4, 'a', 0, 'j', 0) ;<br /> InitializeALine_A (padj, pht, 8, 'i', 0, 4, 'a', 0, 'j', 0) ;<br /> InitializeALine_A (padj, pht, 9, 'j', 0, 4, 'h', 0, 'i', 0) ;</p> <p> /*<br /> InitializeALine_A (padj, pht, 0, 'a', 0, 4, 'b', 0, 'd', 0) ;<br /> InitializeALine_A (padj, pht, 1, 'b', 0, 4, 'a', 0, 'c', 0) ;<br /> InitializeALine_A (padj, pht, 2, 'c', 0, 6, 'b', 0, 'd', 0, 'g', 0) ;<br /> InitializeALine_A (padj, pht, 3, 'd', 0, 8, 'a', 0, 'c', 0, 'e', 0, 'f', 0) ;<br /> InitializeALine_A (padj, pht, 4, 'e', 0, 4, 'd', 0, 'f', 0) ;<br /> InitializeALine_A (padj, pht, 5, 'f', 0, 4, 'd', 0, 'e', 0) ;<br /> InitializeALine_A (padj, pht, 6, 'g', 0, 2, 'c', 0) ;*/<br /> }</p> <p>void find_biconnected_component (const Adjacenty_List * const padj, const Hash_Table * const pht, const int index, Stack * const pst, List * const pli)<br /> {<br /> Adjoin_To_Vertex * scan ;<br /> Stack_Item st1, st2 ;<br /> int w ;</p> <p> visited[index] = TRUE ;<br /> number[index] = low[index] = counter++ ;<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 /> {<br /> /* If edge (w, index) was not already processed as a back edge. */<br /> if (!Find_L (pli, w, index))<br /> Push_S (pst, index, w) ;<br /> parent[w] = index ;<br /> find_biconnected_component (padj, pht, w, pst, pli) ;<br /> /* Don't processe the root! */<br /> if (low[w] >= number[index])<br /> {<br /> while (Pop_S (pst, &st1, &st2))<br /> {<br /> if (index == st1 && w == st2)<br /> {<br /> printf ("%c -> %c/n", (*pht) -> lists[(*padj) -> list[st1].hash_value].name, (*pht) -> lists[(*padj) -> list[st2].hash_value].name) ;<br /> putchar ('/n') ;<br /> break ;<br /> }<br /> else<br /> printf ("%c -> %c/n", (*pht) -> lists[(*padj) -> list[st1].hash_value].name, (*pht) -> lists[(*padj) -> list[st2].hash_value].name) ;<br /> }<br /> }<br /> low[index] = min (low[index], low[w]) ;<br /> }<br /> else if (parent[index] != w)<br /> {<br /> /* Edge (index, w) is already processed as a back edge */<br /> Insert_L (pli, index, w) ;<br /> low[index] = min (low[index], number[w]) ;<br /> }<br /> /* If edge (w, index) was not already processed as a back edge. */<br /> if (!Find_L (pli, w, index))<br /> {<br /> Push_S (pst, index, w) ;<br /> /* Edge (index, w) is already pushed into the stack. Make sure I will not push a edge into a stack twice. */<br /> Insert_L (pli, index, w) ;<br /> }<br /> scan = scan -> next ;<br /> }<br /> }</p> <p>int min (const int val1, const int val2)<br /> {<br /> return val1 < val2 ? val1 : val2 ;<br /> }