數(shù)據結構課程設計實習報告題目：拓撲排序班級：學號：姓名：2008年6月23日至6月27日

實習報告［題目］拓撲排序。實習報告建立有向無環(huán)圖，并輸出拓撲的序列。［基本要求］輸入頂點數(shù)和邊，輸出圖的拓撲的序列。一.問題分析及任務定義對一個有向無環(huán)圖(DirectedAcyclicGraph簡稱DAG)G進行拓撲排序，是將G中所有頂點排成一個線性序列，使得圖中任意一對頂點u和v,若<山v>EE(G)，則u在線性序列中出現(xiàn)在v之前。通常，這樣的線性序列稱為滿足拓撲次序(TopoiSicaiOrder)的序列，簡稱拓撲序列。拓撲排序演示：拓撲排序招撲序列?拓撲排序招撲序列?拓撲排序拓撲排序拓撲排序拓撲排序拓那序列嘖使使拓撲排序????O拓撲序列????痛撲序列③。伽⑥幽拓撲排序?—??—?拓撲排序?—?拓撲序列??@??隔那序列????拓撲排序拓撲排序拓撲排序拓撲排序已完成.拓撲排序序列如下所示。知道了拓撲序列拓撲序列.、4注意：若將圖中頂點按拓撲次序排成一行，則圖中所有的有向邊均是從左指向右的。若圖中存在有向環(huán)，則不可能使頂點滿足拓撲次序。一個DAG的拓撲序列通常表示某種方案切實可行?！纠恳槐緯淖髡邔局械母髡鹿?jié)學習作為頂點，各章節(jié)的先學后修關系作為邊，構成一個有向圖。按有向圖的拓撲次序安排章節(jié)，才能保證讀者在學習某章節(jié)時，其預備知識已在前面的章節(jié)里介紹過。Ci%C73⑴圖E(心圖就的拓補次似Ci%C73⑴圖E(心圖就的拓補次似||列【例】對圖G9進行拓撲排序，至少可得到如下的兩個(實際遠不止兩個)拓撲序列：C0，C1，C2，C4，C3，C5，C7，C8，C6和C0，C7，C9，C1，C4，C2，C3，C6，C5。當有向圖中存在有向環(huán)時，拓撲序列不存在【例】下面(a)圖中的有向環(huán)重排后如(b)所示，有向邊＜v3,vl＞和其它邊反向。若有向圖被用來表示某項工程實施方案或某項工作計劃，則找不到該圖的拓撲序列^即含有向環(huán))，就意味著該方案或計劃是不可行的。V6Vl史VJVl史VJv]r3(a)(b)仃向環(huán)爪例二.概要設計和數(shù)據結構選擇其結構存儲結構:采用鏈接表來存儲圖中的各條邊的關系，鏈接表采用結點和鏈接點，體分別如下所示：其結構typedefstructedgenode//鄰接點{intadjvex;//鄰接點的序號structedgenode*next;}Vertex;typedefstruct//結點{intdata;//結點的入度Vertex*link;}Adjlist;Typedefstruct{Adjlistvertices[MAXVEX];//鄰接表表中結點數(shù)組定義intvexnum,edgenum;//vexnum表示頂點數(shù)，edgenum表示邊數(shù)}ALGraph;定義各個結點：typedefstructvexnodeadjlist[MAXVEX];建立鄰接表例如一個有向圖的結構為：其鄰接表的形式如下:第一列的數(shù)為各頂點的原始度數(shù)。（2）主要算法基本思想。輸出拓撲序列：先輸出入度為0的頂點，再改變其他頂點的入度；循環(huán)以上步驟。具體實現(xiàn)方法：初始r為0（r為每次對全部結點搜索后度數(shù)為0的結點個數(shù)），對鄰接表的各結點進行搜索，當結點的入度不為0，使r加1；當結點的入度為0，使此結點的度數(shù)減1，輸出此結點的值，m加1（m為輸出頂點的個數(shù)），再把此結點的各個鄰接點的入度減1。接著按上面的步驟一樣進行，直到r==n，即結點的入度都不為0。最后如果m<n,即輸出的個數(shù)少于頂點數(shù)則說明網中有環(huán)。（3）設計表示法（1）函數(shù)調用關系如圖所示。(2)函數(shù)接口說明。(1.voidLianJieBiao(adjlistg,intn,inte)/*建立頂點的鏈接表，先初始化各結點的度數(shù)為0,尾為空，再提示輸入相關的一條邊的兩個頂點，要是輸入的數(shù)字有誤提示重新輸入，把這條邊的終點的結點的度數(shù)加1,再把這條邊的終點的結點鏈結到起點上，重復操作。最后打印輸出各頂點的起始度數(shù)。*/(2.voidBianLi(adjlistg,intn)/*通過已建立的鏈接表來遍歷圖，利用for()語句把每個結點的鏈結點打印輸出，以此來遍歷圖，每行最后用”表示結束。*/(3.voidTuoPuPaiXv(adjlistadj,intn)/*輸出拓撲排序的結果，具體實現(xiàn)方法：初始r為0(r為每次對全部結點搜索后度數(shù)為0的結點個數(shù))，對鏈接表的各結點進行搜索，當結點的入度不為0，使r加1；當結點的入度為0，使此結點的度數(shù)減1，輸出此結點的值，m加1(m為輸出頂點的個數(shù))，再把此結點的各個鏈接點的入度減1。接著按上面的步驟一樣進行，直到r==n，即結點的入度都不為0。最后如果m<n,即輸出的個數(shù)少于頂點數(shù)則說明網中有環(huán)。*/(4.main()/*先輸入結點數(shù)和邊數(shù)，接著依次調用LianJieBiao(adjlistg,intn,inte)，BianLi(adjlistg,intn)，TuoPuPaiXv(adjlistadj,intn)三個函數(shù)。*/實現(xiàn)注釋(1.輸入的頂點數(shù)和邊數(shù)應大于0，輸入邊的時候避免輸入(1，1)之類的環(huán)。(2.輸入的頂點個數(shù)最大值為30(3.為方便起見，輸入的頂點用整型調試報告調試實驗時，應逐步調用函數(shù)，先調試LianJieBiao(g,vex,edge);再調試BianLi(g,vex);接著調試TuoPuPaiXv(g,vex);最后調試整段代碼，這樣改錯時方便點。另外，上機前的靜態(tài)檢查不能忽視；程序的調試過程可暫時多加一些輸出語句以便及時查看一下中間運行情況，并對程序規(guī)格說明作少量調整和改動。6。算法改善為避免每次選入度為0的頂點時掃描整個存儲空間，可設一個棧或隊列暫存所有入度為零的頂點。在開始排序前，掃描對應的存儲空間，將人度為零的頂點均入棋隊）。以后每次選人度為零的頂點時，只需做出棧（隊）操作即可。1）此思想方法：該方法的每一步均是輸出當前無后繼（即出度為0）的頂點。對于一個DAG，按此方法輸出的序列是逆拓撲次序。因此設置一個棧或向量）T來保存輸出的頂點序列，即可得到拓撲序列。若T是棧，則每當輸出頂點時，只需做人棧操作，排序完成時將棧中頂點依次出棧即可得拓撲序列。若T是向量，則將輸出的頂點從T[n-1]開始依次從后往前存放，即可保證T中存儲的頂點是拓撲序列。算法的抽象描述為：NonSuccFirstTopSort（G）{//（優(yōu)先輸出無后繼的頂點while（G中有出度為0的頂點）do{從G中選一出度為0的頂點v且輸出v；從G中刪去v及v的所有人邊}if（輸出的頂點數(shù)目＜|V（G）|）Error（"G中存在有向環(huán)，排序失敗!”）；}2）算法求精在對該算法求精時，可用逆鄰接表作為G的存儲結構。設置一個向量outdegree[0..n-1]或在逆鄰接表的頂點表結點中增加1個出度域來保存各頂點當前的出度;設置一個?；蜿犃衼頃捍嫠谐龆葹榱愕捻旤c。除了增加一個?；蛳蛄縏來保存輸出的頂點序列外，該算法完全類似于NonPreFirstTopSort，具體算法【參見練習】。利用深度優(yōu)先遍歷對DAG拓撲排序當從某頂點v出發(fā)的DFS搜索完成時，v的所有后繼必定均已被訪問過（想像它們均已被刪除），此時的v相當于是無后繼的頂點，因此在DFS算法返回之前輸出頂點v即可得到DAG的逆拓撲序列。其中第一個輸出的頂點必是無后繼（出度為0）的頂點，它應是拓撲序列的最后一個頂點。若希望得到的不是逆拓撲序列，同樣可增加T來保存輸出的頂點。若假設T是棧，并在DFSTraverse算法的開始處將T初始化，利用DFS求拓撲序列的抽象算法可描述為：voidDFSTopSort（G，i，T）{//在DisTraverse中調用此算法，i是搜索的出發(fā)點，T是棧intj；visited[i]=TRUE；〃訪問ifor（所有i的鄰接點j）//即＜i，j＞EE（G）if（!visited[j]）DFSTopSort（G，j，T）；〃以上語句完全類似于DFS算法Push（&T，i）；〃從i出發(fā)的搜索已完成，輸出i}只要將深度優(yōu)先遍歷算法DFSTraverse中對DFS的調用改為對DFSTopSort的調用，即可求得拓撲序列T。其具體算法不難從上述抽象算法求精后得到。若G是一個DAG，則用DFS遍歷實現(xiàn)的拓撲排序與NonSuccFirstTopSort算法完全類似；但若C中存在有向環(huán)，則前者不能正常工作。7程序清單#include"stdio.h”#include"malloc.h”#defineMAXVEX30〃定義頂點的最大個數(shù)typedefstructedgenode〃鄰接點{intadjvex;//鄰接點的序號structedgenode*next;}Vertex;typedefstruct〃結點{intdata;〃結點的入度Vertex*link;}Adjlist;typedefstruct{Adjlistvertices[MAXVEX];intvexnum,edgenum;//vexnum表示頂點數(shù)，edgenum表示邊數(shù)}ALGraph;ALGraphLinJieBiao_creat(ALGraphg,intn,inte)/健立頂點的鄰接表{inti,s,d;Vertex*p;for(i=1;i<=n;i++)〃創(chuàng)建鄰接表的結點{g.vertices[i].link=NULL;//結點的尾為空g.vertices[i].data=0;//入度為0}for(i=1;i<=e;i++){printf("\n第％d條邊=>\n\t起點序號，終點序號:”,i);scanf("%d%d”,&s,&d);〃輸入有邊的2個點while(s==d||s>n||d>n)//s==d有環(huán){printf("輸入錯誤，請重新輸A\n");printf("\n第％d條邊=>\n\t起點序號，終點序號:”,i);scanf("%d%d”,&s,&d);}g.vertices[d].data++;//入度加1p=(Vertex*)malloc(sizeof(Vertex));p->adjvex=d;/*把終點的頂點鄰接到起點的頂點*/p->next=g.vertices[s].link;g.vertices[s].link=p;}printf(-各頂點的原始度數(shù)\n");for(i=1;i<=n;i++)printf(”結點％d的度數(shù)為：％d\n”,i,g.vertices[i].data);//輸出各頂點的起始度數(shù)returng;}voidBianLi(ALGraphg,intn)//通過已建立的鄰接表來遍歷圖{inti;Vertex*p;printf(-遍歷圖的結果如下:\n");for(i=1;i<=n;i++){printf("%d=>”,i);//鄰接表中的一個結點p=g.vertices[i].link;//鄰接表中一個結點的第一個鄰接點while(p!=NULL)//一個頂點的全部鄰接點{if(p->next!=NULL)printf("%d-->",p->adjvex);elseprintf("%d",p->adjvex);p=p->next;//T一個鄰接點}printf(”A\n”);//結束符號}}voidTuoPuPaiXu(ALGraphg,intn)//輸出拓撲排序的結果{intm,i,k,r;Vertex*q;m=0;printf(-拓撲排序結果為：\n");while(r<n)//當一次遍歷后全部的頂點入度為0時，退出循環(huán){r=0;//r表示全部頂點一次遍歷后，頂點的度數(shù)不為0的頂點數(shù)for(i=1;i<=n;i++)if(g.vertices[i].data==0)//g.vertices[i]的入度為0時{g.vertices[i].data--;m++;//輸出的個數(shù)加1if(m<n)printf("%d->”,i);elseprintf("%d”,i);q=g.vertices[i].link;//q指向adj[i]的下一個鄰接點while(q!=NULL)〃一個頂點的全部鄰接點的讀書減1{k=q->adjvex;g.vertices[k].data--;q=q->next;}}else〃當g.vertices[i]的入度不為0時，r++{r++;}}if(m<n)printf("網中有環(huán)!\n");//當輸出的個數(shù)小于頂點的個數(shù)，表明圖中有環(huán)}voidmain(){ALGraphg;printf("結點數(shù)(n)和邊數(shù)(e):");scanf("%d%d”,&g.vexnum,&g.edgenum);//輸入頂點數(shù)和邊數(shù)g=LinJieBiao_creat(g,g.vexnum