【正文】 為 0的結點提取出來，然后再統(tǒng)計剩下的結點的入度，再次將入度為零的結點提取出來，以 此類推，這樣就形成了一個序列，這樣的序列就是該圖的拓撲排序序列。 。個人在寫程序時，考慮到構造圖時，會有構造成有向有環(huán)圖的情況，應該在運行程序時，提醒出來，然后重 新輸入有向無環(huán)圖，知道輸入正確為止。這樣就有多次構造鄰接表的問題，每一次構造鄰接表時，都應該 將原來錯誤的（不是無環(huán)圖的）鄰接表空間釋放掉，否則，會變得混亂。 ，還要求輸 出鄰接表數(shù)據(jù)。由于圖是用鄰接表存儲的，所以很容易將其鄰接表輸出 來。 32 第二章 圖的遍歷及拓撲排序 系統(tǒng) 概要設計 系統(tǒng)流程圖 根據(jù)程序的總的步驟，擬將整個流程分為三個模塊。三個模塊既相互獨立又相互聯(lián)系。具體分析如下： 1. 圖像輸入，根據(jù)題目要求，要能夠建立一個有向無環(huán)圖，這就要我們在程序中去建立。考慮到輸入方式要盡量 方便全面，采用輸入弧的方式，輸入每條弧的鏈接的兩個結點，當輸入 1時結束輸入。這樣再輸入的時候，與相鄰的兩個結點的鄰接矩陣對應的位置也做相應改變。 2. 判斷圖是不是有向無環(huán)圖。當圖為有向無環(huán)圖時，則挑選完畢后，隊列應該是滿的，進行后續(xù)步驟。對于結點入隊列的順序，需要借助于 visited 數(shù)組。選取入度為零的結點，入隊列，調整 visited 數(shù)組，循環(huán)進行。若隊列不滿，則輸入的圖不符合要求，應該重新輸入。在程序中應做適當提醒，然后自動轉模塊 1.，進行圖的重新編輯。 3. 拓撲排序。此時，所輸入的弧應該是有向無環(huán) 圖了，下面進行拓撲排序。在判斷它是否為無環(huán)圖的過程中已經(jīng)形成了一個滿隊列。接下來所要做 的事情就是循環(huán)出隊列，按照隊列固有的順序進行輸出即可，排序完成。系統(tǒng)的流程圖如圖 21所示。 33 否 是 否 是 圖 21 系統(tǒng)流程圖 功能模塊 圖 系統(tǒng)的功能模塊圖如圖 22 所示 .包括圖的遍歷和拓撲排序兩部分，圖的遍歷中若是有環(huán)圖則遍歷全部，若是無環(huán)圖則無法遍歷；拓撲排序模塊則實現(xiàn)拓撲排序功能。 圖 22 系統(tǒng)功能圖 開始 圖形輸入 構造鄰接表并輸出 無環(huán)圖 滿隊列 入度為零入隊列 調整 visited 循環(huán)出隊列 結束 系統(tǒng) 圖的遍歷 有環(huán)圖遍歷全部 無環(huán)圖 無法遍歷 拓撲排序 入度為零入隊 輸出隊列 34 第三章 詳細設計 系統(tǒng) 功能的實現(xiàn) 本程序的拓撲排序，必須在圖的鄰接表已知的情況下。它還有另外一個功能：判斷一個圖是不是無環(huán)圖。確切的說，不能單純的叫拓撲排序，但 考慮它主要的作用，在不引起誤解的情況下就叫拓撲排序算法。 判斷一個圖是否為有向無環(huán)圖并進行拓撲排序，判定方法有很多種，檢查一個有向圖是否存在環(huán)要比無向圖復雜。對于無向圖來說，若深度優(yōu)先遍歷過程中遇到回邊（即指向已訪問過的頂點的邊），則必存在環(huán)；而對于有向圖來說，這條回邊有可能指向深度優(yōu)先森林中另一棵生成樹上頂點的弧。但是，如果從有向圖上某個頂點 v 出發(fā)的遍歷，在 dfs(v)結束之前出現(xiàn)一條從頂點 u到頂點 v的回邊，由于 u 在生成樹上是 v 的子孫，則有向圖中必定存在包含頂點 v 和 u 的環(huán)。 另一種判斷是否有環(huán)的方法則顯得簡單的多，尤其是對于本題目來說，由于本題要求 是對有向無環(huán)圖進行拓撲排序，其主要方法是將入度為零的結點依次輸 出來，知道圖的所有定點全部輸出為止。那么若圖為有環(huán)圖，在環(huán)上的結點在其他結點都選擇出來后，入度都不為零，即無法被輸出出來。那么就可以認為按照拓撲排序的方法輸出結 點后，若不是將節(jié)點全部輸出出來的，則此圖為有環(huán)圖。 判斷好圖是否為有向圖后，考慮到題目要求，要能夠處理出現(xiàn)環(huán)的情況，若構造的圖為有環(huán)圖，則折回開始重新輸入圖的數(shù)據(jù)，重新構造圖，直到該圖為無環(huán)圖為止。若圖已經(jīng)是無環(huán)圖，則進行拓撲排序，排序方法前面已經(jīng)講過，在此主要訴說用到的輔助存儲。數(shù)組 visited[]存儲各結點的入度，對入度為零的結點，依次入隊列 queue，調整 visited[]數(shù)組，結點全部入隊列后，然后依次出隊列，拓撲排序完成。 實現(xiàn)功能的程序代碼如下： include typedef int elemtype。 const MAX=100。 bool visited[MAX]。 class link { public: elemtype data。 link *next。}。 class node { public: 35 link a[MAX]。 void creatlink3(node amp。g ,int n,int e)。void bfs2(node g,int i)。 void dfs1(node g,int i)。 void topsort (node amp。g,int n )。} 。 void node::creatlink3( node amp。g,int n,int e) //建立帶入度的鄰接表 { int i,j,k 。 link *s 。 for(i=1。 i=n。i++) //建立鄰接表頭結點 { [i].data=0。 //入度值為 0 [i].next=NULL。 } for(k=1。 k=e。k++) { cout請輸入一條弧 :。 cinij 。 //輸入一條弧 i,j coutendl。 s=new link。 //申請一個動態(tài)存儲單元 sdata=j 。 snext=[i].next 。 [i].next=s 。 [j].data++。 //入度加 1 }} void node::topsort (node amp。g,int n ) //拓撲排序 {int top=0,m=0。 for (int i=1。i=n。i++) //入度為 0 的頂點進棧 if ([i].data==0) {[i].data=top。 top=i。} while (top0) {i=top。 top=[top].data, //出棧 cout i 。 //輸出入度為 0的頂點 m++。 //輸出結點個數(shù)增 1 link *p=[i].next。 while (p!=NULL) {int k=pdata。 [k].data 。 //刪除一條邊，頂點入度值減 1 if([k].data==0) { [k].data=top。 top=k。} //入度為 0 進棧 p=pnext。} } 36 if (mn) cout網(wǎng)絡中出現(xiàn)環(huán)路 。} void node::bfs2(node g,int i) { int q[MAX] 。 int f,r 。 link *p 。 f=r=0 。 couti 。 visited[i]=true 。 r++。 q[r]=i 。 while (fr) {f++ 。 i=q[f] 。 p=[i].next 。 while (p!=NULL) { if (!visited[pdata]) { coutpdata 。 visited[pdata]=true 。 r++。q[r]=pdata 。 } p=pnext。 }} } void node::dfs1(node g,int i) { link *p。 couti 。 visited[i]=true。 p=[i].next。 while (p!=NULL) { if(!visited[pdata]) dfs1(g,pdata)。 p=pnext。}} void main() { node g。 int yn=1。 while(yn==1) {int n1,e1。 cout請輸入要建立的有向圖的元素個數(shù)： 。 cinn1。 coutendl。 37 cout請輸入要建立的有向圖的邊數(shù)： 。 cine1。 coutendl。 cout*******************************************endl。 cout*****************建立鄰接表 ****************endl。 (g,n1,e1) 。 int flag=1。 while(flag==1) {for(int i=1。i=n1。i++) visited[i]=false。 cout深度優(yōu)先搜索遍歷序列為： endl。 for(i=1。i=n1。i++) if(!visited[i]) (g,i)。 coutendl。 cout*******************************************endl。 for(i=1。i=n1。i++) visited[i]=false。 cout廣度優(yōu)先搜索遍歷序列為： endl。 for(i=1。i=n1。i++) if(!visited[i]) (g,i)。 coutendl。 cout繼續(xù)遍歷嗎 (1/2)。 cinflag。} cout************************************endl。 cout拓撲排序結果： endl。 (g,n1)。 coutendl。 cout*************************************************endl。 cout是否繼續(xù)輸入其他的圖的結構進行遍歷和拓撲排序？ (1/2)。 cinyn。}} 38 第四章 調試分析 系統(tǒng)運行 主 界面 運行此系統(tǒng)后，首先出現(xiàn)的是主窗口，如圖 41所示。 提示用戶輸入要建立的有向圖的元素個數(shù)，用戶輸入數(shù)據(jù)后，按回車鍵，系統(tǒng)會進入下一步。 圖 41 主 窗口運行界面 圖 系統(tǒng)運行結果 用戶按照系統(tǒng)的提示輸入相應的信息后，系統(tǒng)運行界面如果 42 所示。 39 圖 42系統(tǒng)運行結果圖 40 第五章 程序設計結語 此次課程設計的 總結 雖然平時對拓撲排序有一些了解，上課也學過，但真正應用到程序中，寫出算法卻一點也不簡單。拓撲排序 ，首先需要有被排序的主體，也就是有向圖，于是先要實現(xiàn)有向圖的建立及相關操作；有向圖的建立，該選取怎樣的數(shù)據(jù)結構，是鄰接矩陣還是鄰接表，本著盡量靠近實際應用的態(tài)度，我選擇了節(jié)省存儲空間的鄰接表；拓撲排序要將圖中零入度頂點先輸出，可利用?；蜿犃袑崿F(xiàn)，而本程序的一個應用是實現(xiàn)教學計劃的安排，考慮到教學計劃安排的實際情況，一般先學各門基礎課（入度為零），再學專業(yè)課（入度不為零），與隊列先進先出的特點相符，故采用隊列實現(xiàn)?？傊?，什么地方該用什么數(shù)據(jù)結構，該寫出怎樣的算法，都要經(jīng)過精心分析和仔細考慮。在完成課程設計的過 程中，我加深了對程序結構的了解程度，對各種語句理解也更透徹，學會了靈活運用。同時體會到了團隊合作的樂趣，一向慣于“獨立思考”的我們學會了積極地同團隊成員交流，取長補短，共同進步，只有和同學多交流多學習才能不斷地提高自身水平。 總之，這學期的數(shù)據(jù)結構課程設計，讓我們學到了很多，受益匪淺。 41 參考文獻 [1] 嚴蔚敏，吳偉