實現(xiàn)有向圖強連通分量的算法 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告

1、課課 程程 設(shè)設(shè) 計計 報報 告告 課程設(shè)計名稱：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 課程設(shè)計題目：實現(xiàn)求有向圖強連通分量的算法實現(xiàn)求有向圖強連通分量的算法 院（系）： 專 業(yè)： 班 級： 學(xué) 號： 姓 名： 指導(dǎo)教師： 目目 錄錄 1 系統(tǒng)分析系統(tǒng)分析.1 1.1 題目介紹 .1 1.2 功能要求 .1 2 概要設(shè)計概要設(shè)計.2 2.1 流程圖 .2 2.2 結(jié)構(gòu)體說明 .2 3 詳細設(shè)計詳細設(shè)計.3 3.1 遍歷函數(shù)設(shè)計 .3 3.1.1 Kosaraju 算法基本思路：.3 3.1.2 偽代碼.4 3.2 調(diào)試分析和測試結(jié)果 .6 3.2.1 調(diào)試分析.6 3.2.2 測試結(jié)果.6 參考文

2、獻參考文獻.8 附附 錄（關(guān)鍵部分程序清單）錄（關(guān)鍵部分程序清單）.9 1 系統(tǒng)分析 1.1 題目介紹題目介紹 在鍵盤上輸入有向圖，對任意給定的圖（頂點數(shù)和邊數(shù)自定），建立它的鄰 接表并輸出。然后判斷該圖是否強連通。如果是強連通圖，求出該圖的所有強連 通分量并輸出字符。 1.2 功能要求功能要求 首先輸入圖的類型，有向圖（因為遍歷與權(quán)值無關(guān)，所以沒有涉及帶權(quán)圖）。 然后輸入圖的頂點數(shù)、邊數(shù)和各條邊，之后生成該圖的鄰接表并輸出。 再輸入要遍歷該圖的起點，然后從所輸入的點深度搜索該圖的十字鏈表，并 按遍歷順序輸出頂點內(nèi)容。之后決定是否繼續(xù)遍歷該圖或輸入另一個需要遍歷的 圖亦或是結(jié)束程序。 要求采取

3、簡單方便的輸入方式。并且系統(tǒng)要求提供觀察有向圖圖形結(jié)構(gòu)和各 強連通分量結(jié)構(gòu)的功能。 2 概要設(shè)計 2.1 流程圖流程圖 根據(jù)程序要求，設(shè)計流程圖如下： 是 否 圖 2.1流程圖 2.2 結(jié)構(gòu)體說明結(jié)構(gòu)體說明 /有向圖十字鏈表存儲表示 typedef struct arcbox int tailvex,headvex;/該弧的尾和頭頂點的位置 開始 輸入有向圖 圖的類型 確定有無權(quán)值 的類型 1（有權(quán)值）0（無權(quán)值） 深度優(yōu)先遍歷該圖 輸入從哪個頂點開始遍歷該圖 結(jié)束 是否還有頂點結(jié)束 對反圖 GT 進行遍歷，刪除能夠遍歷到的頂點 struct arcbox *hlink,*tlink;/分別為

4、弧頭相同和弧尾相同的弧的鏈域 infotype * info;/該弧相關(guān)信息的指針 arcbox; typedef struct vexnode vextype data; arcbox *firstin,*firstout;/分別指向該頂點第一條入弧和出弧 vexnode; typedef struct vexnode xlistmax_vex_num;/表頭向量 int vexnum,arcnum;/有向圖的當(dāng)前頂點數(shù)和弧數(shù) OLgraph; 3 詳細設(shè)計 3.1 遍歷函數(shù)設(shè)計遍歷函數(shù)設(shè)計 3.1.1 Kosaraju 算法基本思路算法基本思路： 這個算法可以說是最容易理解，最通用的算法，

5、其比較關(guān)鍵的部分是同時應(yīng)用了 原圖 G 和反圖 GT。(步驟 1)先用對原圖 G 進行深搜形成森林(樹)，（步驟 2）然 后任選一棵樹對其進行深搜(注意這次深搜節(jié)點 A 能往子節(jié)點 B 走的要求是 EAB 存在于反圖 GT)，能遍歷到的頂點就是一個強連通分量。余下部分和原來的森林 一起組成一個新的森林，繼續(xù)步驟 2 直到?jīng)]有頂點為止。 改進思路： 當(dāng)然，基本思路實現(xiàn)起來是比較麻煩的(因為步驟 2 每次對一棵樹進行深搜時，可 能深搜到其他樹上去，這是不允許的，強連通分量只能存在單棵樹中)，我們當(dāng)然 不這么做，我們可以巧妙的選擇第二深搜選擇的樹的順序，使其不可能深搜到其 他樹上去。想象一下，如果步

6、驟 2 是從森林里選擇樹，那么哪個樹是不連通(對于 GT 來說)到其他樹上的呢？就是最后遍歷出來的樹，它的根節(jié)點在步驟 1 的遍歷 中離開時間最晚，而且可知它也是該樹中離開時間最晚的那個節(jié)點。這給我們提 供了很好的選擇，在第一次深搜遍歷時，記錄時間 i 離開的頂點 j，即 numbi =j。那么，每次只需找到?jīng)]有找過的頂點中具有最晚離開時間的頂點直接深搜(對 于 GT 來說)就可以了。每次深搜都得到一個強連通分量。 隱藏性質(zhì): 分析到這里，已經(jīng)知道怎么求強連通分量了。但是，如果把求出來的每個強連通 分量收縮成一個點，并且用求出每個強連通分量的順序來標(biāo)記收縮后的節(jié)點，那 么這個順序其實就是強連通

7、分量收縮成點后形成的有向無環(huán)圖的拓撲序列。首先， 應(yīng)該明確搜索后的圖一定是有向無環(huán)圖，如果還有環(huán)，那么環(huán)上的頂點對應(yīng)的所 有原來圖上的頂點構(gòu)成一個強連通分量，而不是構(gòu)成環(huán)上那么多點對應(yīng)的獨自的 強連通分量了。然后就是為什么是拓撲序列，我們在改進分析的時候，不是先選 的樹不會連通到其他樹上（對于反圖 GT 來說），也就是后選的樹沒有連通到先 選的樹，也即先出現(xiàn)的強連通分量收縮的點只能指向后出現(xiàn)的強連通分量收縮的 點。那么拓撲序列不是理所當(dāng)然的嗎？這就是 Kosaraju 算法的一個隱藏性質(zhì)。 3.1.2 偽代碼偽代碼 Kosaraju_Algorithm: step1：對原圖 G 進行深度優(yōu)先遍

8、歷，記錄每個節(jié)點的離開時間。 step2：選擇具有最晚離開時間的頂點，對反圖 GT 進行遍歷，刪除能夠遍歷到的 頂點，這些頂點構(gòu)成一個強連通分量。 step3：如果還有頂點沒有刪除，繼續(xù) step2，否則算法結(jié)束。 3.1.3. 實現(xiàn)代碼： #include using namespace std; const int MAXN = 110; typedef int AdjTableMAXN; /鄰接表類型 int n; bool flagMAXN; /訪問標(biāo)志數(shù)組 int belgMAXN; /存儲強連通分量,其中 belgi表示頂點 i 屬于第 belgi個 強連通分量 int numbM

9、AXN; /結(jié)束時間標(biāo)記,其中 numbi表示離開時間為 i 的頂點 AdjTable adjMAXN, radjMAXN; /鄰接表,逆鄰接表 /用于第一次深搜,求得 numb1.n的值 void VisitOne(int cur, int for ( int i=1; i=adjcur0; +i ) if ( false=flagadjcuri ) VisitOne(adjcuri,sig); numb+sig = cur; /用于第二次深搜,求得 belg1.n的值 void VisitTwo(int cur, int sig) flagcur = true; belgcur = sig

10、; for ( int i=1; i=radjcur0; +i ) if ( false=flagradjcuri ) VisitTwo(radjcuri,sig); /Kosaraju 算法,返回為強連通分量個數(shù) int Kosaraju_StronglyConnectedComponent() int i, sig; /第一次深搜 memset(flag+1,0,sizeof(bool)*n); for ( sig=0,i=1; i0; -i ) if ( false=flagnumbi ) VisitTwo(numbi,+sig); return sig; 3.2 調(diào)試分析和測試結(jié)果調(diào)試

11、分析和測試結(jié)果 編譯、運行及調(diào)試環(huán)境: Microsoft Visual C+ 3.2.1 調(diào)試分析調(diào)試分析 一在輸入圖信息的時候，若輸入非法字符，程序會異常終止。例如程序要求輸 入一個整型，用戶卻輸入了一個字母，這時候會出現(xiàn)異常。只是程序是否健壯性 的一個體現(xiàn)。 先用字符串接收字符，轉(zhuǎn)換成整型后再判斷是否符合要求。如果不符合便提示用 戶按要求重新輸入。還有其他一些類似的輸入異常，都是采用類似的處理方法。 二作為一個完整的程序，友好的界面是必須的。因次程序中適當(dāng)?shù)夭捎萌诵曰?的提示命令，使得界面更加簡潔，明了。 3.2.2 測試結(jié)果測試結(jié)果 測試案例： 3 1 4 2 6 5 圖 3.2.2案

12、例結(jié)構(gòu)圖 圖 1程序運行 圖 2程序結(jié)果 參考文獻 1 王為青，張圣亮 . C 語言實戰(zhàn) 105 例. 人民郵電出版社，2007.3 2 嚴(yán)蔚敏，吳偉民 . 數(shù)據(jù)結(jié)構(gòu)（C 語言版）.清華大學(xué)出版社，1997.4 3 袁平波.數(shù)據(jù)結(jié)構(gòu)實驗指導(dǎo),合肥 .中國科學(xué)技術(shù)大學(xué)出版社，2010.7 4 楊克昌，劉志輝 . 趣味 C 程序設(shè)計集錦，北京 . 中國水利水電出版社， 2010.1 附 錄（關(guān)鍵部分程序清單） # include # include typedef int vextype; typedef int infotype; typedef int status; # define max

13、_vex_num 15 # define FALSE 0 # define TRUE 1 # define OVERFLOW -2 /有向圖十字鏈表存儲表示 typedef struct arcbox int tailvex,headvex; struct arcbox *hlink,*tlink; infotype * info; arcbox; typedef struct vexnode vextype data; arcbox *firstin,*firstout; vexnode; typedef struct vexnode xlistmax_vex_num; int vexnum

14、,arcnum; OLgraph; int Locatevex(OLgraph G,int d) int k; for(k=0;kG.vexnum;+k) if(G.xlistk.data=d) return k; status creat_DG(OLgraph vextype tailnum,headnum; arcbox *p; printf(輸入結(jié)點個數(shù):); scanf(%d, printf(輸入弧的條數(shù):); scanf(%d, printf(輸入有無權(quán)值判定符(0 表示沒有,1 表示有):); scanf(%d, printf(輸入所有弧結(jié)點數(shù)據(jù):); for(a=0;aG.vex

15、num;+a) scanf(%d, G.xlista.firstin=NULL; G.xlista.firstout=NULL; for(k=0;ktailvex=i; p-headvex=j; p-hlink=G.xlistj.firstin; p-tlink=G.xlisti.firstout; /p-info=NULL; G.xlistj.firstin=G.xlisti.firstout=p; if(incinfo) printf(輸入權(quán)值:); scanf(%d,p-info); return TRUE; /creat_DG typedef int boolen; boolen vi

16、sitedmax_vex_num ; int finishedmax_vex_num ; int number; void DFS_1(OLgraph G,int v) arcbox *p; visitedv=TRUE; p=G.xlistv.firstout; while(p) if(!visitedp-headvex) DFS_1(G,p-headvex); p=p-tlink; finishednumber=v; number=number+1; void DFStraverse_1(OLgraph G) int v; for(v=0;vG.vexnum;+v) visitedv=FALSE; for(v=0;vtailvex) DFS_2(G,p-tailvex); p=p-hlink; void DFStraverse_2(OLgraph G) int v,m=1; for(v=0;v=0;v-) if(!visitedfinishedv) printf(n); printf(n); printf(第%d 個連通分量的頂點集:,m); m=m+1; DFS_2(G,finishedv);