原创力文档- 1、本文档共881页，可阅读全部内容。
- 2、原创力文档（book118）网站文档一经付费（服务费），不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。
- 3、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。如您付费，意味着您自己接受本站规则且自行承担风险，本站不退款、不进行额外附加服务；查看《如何避免下载的几个坑》。如果您已付费下载过本站文档，您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“版权申诉”（推荐），也可以打举报电话：400-050-0827(电话支持时间：9:00-18:30)。
由於有向圖的存儲形式的不同，拓撲排序演算法的實現也不同。1）基於鄰接矩陣表示的存儲結構A為有向圖G的鄰接矩陣，則有：·找圖G中無前驅的頂點——在A中找到值全為0的列；·刪除以i為起點的所有弧——將矩陣中i對應的行全部置為0。演算法步驟如下：（1）取1作為第一新序號；（2）找一個未新編號的、值全為0的列j，若找到則轉（3）；否則，若所有的列全部都編過號，拓撲排序結束；若有列未曾被編號，則該圖中有回路；（3）輸出列號對應的頂點j，把新序號賦給所找到的列；（4）將矩陣中j對應的行全部置為0;（5）新序號加1，轉（2）。2）基於鄰接表的存儲結構入度為零的頂點即為沒有前驅的頂點，我們可以附設一個存放各頂點入度的數組indegree［］，於是有（1）找G中無前驅的頂點——查找indegree［i］為零的頂點v#-i；（2）刪除以i為起點的所有弧——對鏈在頂點i後面的所有鄰接頂點k，將對應的indegree［k］減1。為了避免重複檢測入度為零的頂點，可以再設置一個輔助棧，若某一頂點的入度減為0，則將它入棧。每當輸出某一入度為0的頂點時，便將它從棧中刪除。演算法的實現：intTopoSort(AdjListG){StackS;intindegree［MAX-VERTEX-NUM］;inti,count,k;ArcNode*p;FindID(G,indegree);/*求各頂點入度*/InitStack(S);/*初始化輔助棧*/for(i=0;iG.vexnum;i++)if(indegree［i］==0)Push(S,i);/*將入度為0的頂點入棧*/count=0;while(!StackEmpty(S)){Pop(S,i);printf(″%c″,G.vertex［i］.data);count++;/*輸出i號頂點並計數*/p=G.vertexes［i］.firstarc;while(p!=NULL){k=p-adjvex;indegree［k］--;/*i號頂點的每個鄰接點的入度減1*/if(indegree［k］==0)Push(S,k);/*若入度減為0，則入棧*/p=p-nextarc;}}/*while*/if(countG.vexnum)return(Error);/*該有向圖含有回路*/elsereturn(Ok);}【演算法7.10拓撲排序演算法】voidFindID(AdjListG,intindegree［MAX-VERTEX-NUM］)/*求各頂點的入度*/{inti;ArcNode*p;for(i=0;iG.vexnum;i++)indegree［i］=0;for(i=0;iG.vexnum;i++){p=G.vertexes［i］.firstarc;while(p!=NULL){indegree［p-adjvex］++;p=p-nextarc;}}/*for*/}【演算法7.11求各頂點入度的函
文档评论（0）