山大《數(shù)據(jù)結(jié)構(gòu)》講義05圖

1、第五章 圖內(nèi)容概述圖是一種應(yīng)用非常廣泛的數(shù)據(jù)結(jié)構(gòu)，目前已被應(yīng)用于社會、化學(xué)、管理學(xué)、地理和電子工程等不同領(lǐng)域。例如，圖常用于化合物（特別是碳氫化合物）的分子結(jié)構(gòu)研究、空中航線和通信網(wǎng)絡(luò)的描述、項目策劃、遺傳研究、統(tǒng)計等。本章將介紹：圖的基本概念；鄰接矩陣、鄰接表等存儲表示；處理圖的幾個重要算法，包括深度優(yōu)先搜索、廣度優(yōu)先搜索；圖的應(yīng)用，包括拓撲排序、最小生成樹、最短路徑。重點與難點重點包括：圖的鄰接矩陣和鄰接表存儲結(jié)構(gòu)，圖的深度優(yōu)先和廣度優(yōu)先遍歷，最小生成樹、拓撲排序、關(guān)鍵路徑和最短路徑的求解。難點包括：求最小生成樹、拓撲排序、關(guān)鍵路徑和最短路徑算法。思考1圖是一種相對于線性表、樹更復(fù)雜的數(shù)據(jù)

2、結(jié)構(gòu)，其復(fù)雜性體現(xiàn)在何處？2在解決圖的具體應(yīng)用問題時，圖的存儲表示（鄰接矩陣、鄰接表）的選取標(biāo)準(zhǔn)是什么？3論述圖的深度優(yōu)先搜索遍歷的策略4編寫一個實現(xiàn)連通圖G的深度優(yōu)先搜索遍歷的非遞歸程序。5論述圖的廣度優(yōu)先搜索遍歷的策略6論述Prim算法的基本思想。使用Prim算法構(gòu)造如下圖所示的圖G的一棵最小生成樹。7為什么尋找最短路徑的算法稱為“貪婪”算法？8論述FLOYD算法的基本思想。9有向網(wǎng)G2的鄰接矩陣如下所示，利用FLOYD算法求出所有頂點之間的最短路徑，寫全過程。第一節(jié)圖的教學(xué)結(jié)構(gòu)圖是一種相對于線性表、樹更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。為了更好的理解圖結(jié)構(gòu)，本節(jié)從圖的實例入手全面分析圖的定義、圖的特性和圖

3、的抽象類型。1、圖的定義在給出圖（Graph）的定義之前，先看一個圖的應(yīng)用舉例。例5-1航空公司需要設(shè)計一個航線咨詢系統(tǒng)來處理乘客從某個城市飛往另一個城市的請求。問題的求解方案：用圖描述航線（參見圖5-1（a），對圖進行窮舉搜索，以確定從起始城市到目的城市之間的航線。如果乘客對航線提出進一步的要求，譬如要求航線中的中轉(zhuǎn)站最少，則這個問題反映到圖上就是要找一條從起點到終點所含邊數(shù)最少的路徑。求解方法是從起始頂點出發(fā)對圖做廣度優(yōu)先搜索，一旦遇到目的頂點就終止。如果乘客為了節(jié)省費用需要一條飛行距離最短的航線，則問題反映在圖上就是求解從起始頂點到目的頂點的最短路徑，問題的求解方案則分別采取對圖進行廣度

4、優(yōu)先搜索和求解最短路徑。給出了圖的幾個示例。顯然，圖提供了一種用圖形說明數(shù)據(jù)的方法。不過，圖也表示了數(shù)據(jù)項之間的關(guān)系，圖的這種性質(zhì)非常重要。子圖由圖的頂點子集和邊的子集組成。圖5-2給出了圖5-1（b）的部分子圖。如果圖中的某兩個頂點v和w由一條邊e=（v，w）連接在一起，則稱頂點v與w相鄰接，v與w互為鄰接點（Adjacent），而邊e依附于（Incident）頂點v和w，或者說邊e與v和w相關(guān)聯(lián)。如果頂點對是無序的，則圖G稱為一個無向圖；如果頂點對是有序的，則圖G稱為有向圖。有向圖的頂點對通常表示為V，w，表示從v到w的一條弧，且稱v為弧尾或初始點，稱w為弧頭或終端點。常用術(shù)語digrap

5、h表示有向圖，術(shù)語graph表示無向圖。例如圖5-1（a）G1是一個有向圖，其中城市（A，B，G）是頂點，從一個頂點到另一個頂點的有向邊（用帶箭頭的線段表示）則表示一條航線。圖5-1（b）G2是一個無向圖，圖中頂點代表建筑物，無向邊代表建筑物之間的道路，宿舍與圖書館是相鄰接的。兩個頂點之間的路徑是從一個頂點開始而結(jié)束于另一個頂點的頂點序列，且每一個頂點與下一個頂點相鄰接。路徑的長度是指一條路徑上經(jīng)過的邊的數(shù)目。頂點序列中頂點不重復(fù)出現(xiàn)的路徑稱為簡單路徑。例如圖5-1（b）中，宿舍圖書館體育場是一條簡單路徑。起點與終點是同一個頂點的路徑叫做回路或環(huán)（Cycle）。除起點與終點之外，其余頂點不重復(fù)

6、出現(xiàn)的回路，稱為簡單回路。例如圖5-1（a）中，定點序列（C，F(xiàn)，G，C）是一條簡單回路。在無向圖中，如果每一對不同的頂點之間都有一條路徑，則圖是連通的（Connected）。也就是說，在連通圖中，從任意一個頂點出發(fā)，都可以沿一條路徑到達其它頂點。圖5-3（a）是一個連通圖，圖5-3（b）是一個非連通圖。注意：連通圖不一定在每對頂點之間都有一條邊。如果在圖中每一對不同的頂點之間都有一條邊，則稱之為完全（Complete）圖。圖5-3（c）是一個完全圖的示例。顯然，完全圖是連通圖，反之則不然。無向圖G中極大連通子圖稱為G的連通分量。圖5-4（a）是一個非連通圖，但有三個連通分量。在有向圖G中，如

7、果對于每一對vi，vjV，vivj，從vi到vj和從vj到vi都存在路徑，則稱G是強連通圖。有向圖中的極大強連通子圖稱作有向圖的強連通分量。例如圖5-1（a）中的航線圖不是強連通圖，但圖5-5是它的一個強連通分量。一個連通圖的生成樹是一個極小連通子圖，它含有圖中全部頂點，但只有足以構(gòu)成一棵樹的若干條邊。圖5-6是G3中最大連通分量的一棵生成樹。如果在一棵生成樹上添加一條邊，必定構(gòu)成一個環(huán)，因為這條邊使得它依附的那兩個頂點之間有了第二條路。一棵有n個頂點的生成樹有且僅有n-1條邊。如果一個圖有n個頂點和小于n-1條邊，則是非連通圖。如果多于n-1條邊，則一定有環(huán)。但是，有n-1條邊的圖不一定是生

8、成樹。例5-2是一個生成樹的應(yīng)用舉例。例5-2局域網(wǎng)LAN擴展的常規(guī)做法是利用透明網(wǎng)橋（Bridge）連接不同的局域網(wǎng)段。為了提高擴展局域網(wǎng)的可靠性，我們可以在LAN之間設(shè)置并行的兩個或多個網(wǎng)橋，如圖5-7所示。但是，由于在拓撲結(jié)構(gòu)中產(chǎn)生了回路，這樣配置引起了另外一些問題：由于透明網(wǎng)橋?qū)τ谀康牡刂凡幻鞔_的幀采取擴散算法，在本例中網(wǎng)橋B1、B2將目的地址不明的幀F(xiàn)分別復(fù)制到LAN2中形成幀F(xiàn)1、F2。緊接著，橋B1看見目的地不明確的幀F(xiàn)2，將其復(fù)制轉(zhuǎn)發(fā)到LAN1，產(chǎn)生一個新幀，如F3（圖中未畫出）；類似地，橋B2也將F1復(fù)制轉(zhuǎn)發(fā)到LAN1，產(chǎn)生F4。隨后，橋B1又復(fù)制轉(zhuǎn)發(fā)F4，而橋B2則復(fù)制轉(zhuǎn)發(fā)

9、F3，無限循環(huán)下去。解決這個難題的方法是讓網(wǎng)橋相互通信，并用一棵覆蓋到每個LAN的生成樹（SpanningTree）覆蓋實際的拓撲結(jié)構(gòu)。生成樹網(wǎng)橋是DEC公司針對透明網(wǎng)橋中存在的環(huán)路問題而提出的，IEEE將其標(biāo)準(zhǔn)定義802.1d。有時圖的邊或弧具有與它相關(guān)的數(shù)值，這種與圖的邊或弧相關(guān)的數(shù)值叫做權(quán)（Weight）。這些權(quán)可以表示從一個頂點到另一個頂點的距離或耗費。這種帶權(quán)的圖通常稱為網(wǎng)（Network）。2、圖的特性設(shè)G是一個無向圖，頂點vi的度（Degree）di是與頂點相連的邊的個數(shù)。對于圖5-4中的G3，dA=4，dB=2，dC=1。特性1設(shè)G=（V，E）是一個無向圖，用V表示頂點個數(shù)，用

10、E表示邊的個數(shù)。令V=n，E=e，di為頂點i的度，則有1）=2e2）0en(n-1)/2對于無向圖，e的取值范圍是0n（n-1）。一個具有n個頂點，n（n-1）條邊的無向圖是一個完全圖。設(shè)G是一個有向圖，頂點vi的入度（In-Degree）d是以頂點vi為頭的弧的數(shù)目。頂點vi的出度（Out-Degree）d是以頂點vi為尾的弧的數(shù)目。例如，對于圖5-1（a），d=2，d=0。對于有向圖，一個頂點的度是該頂點的入度與出度之和。特性2設(shè)G=（V，E）是一個有向圖，n和e的含義與特性1相同，則1）=e2）0en(n-1)對于一個有向圖，e的取值范圍是0n（n-1）。一個具有n個頂點，n（n-1）

11、條邊的有向圖是一個完全圖。3、圖的抽象類型圖是一種數(shù)據(jù)結(jié)構(gòu)，加上一組基本操作，就構(gòu)成了抽象數(shù)據(jù)類型。抽象數(shù)據(jù)類型Graph專指無向圖，而抽象數(shù)據(jù)類型Digraph專指有向圖。圖的抽象數(shù)據(jù)類型定義如下：ADTGraph/Digraph數(shù)據(jù)對象V：V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點集。數(shù)據(jù)關(guān)系R：R=VR對于有向圖VR=V，w|v，wV且P(v，w),V，w表示從v到w的弧，謂詞P(v，w)定義了弧V，w的意義或信息對于無向圖VR=(v，w)|v，wV且P(v，w),(v，w)表示從v到w的邊，謂詞P(v，w)定義了邊(v，w)的意義或信息基本操作P：CreateGraph（G，V，VR）

12、返回結(jié)果：V是圖的頂點集，VR是圖中邊或弧集合。按V和VR的定義構(gòu)造圖G。DestoryGraph（G）初始條件：G是已經(jīng)存在的一個圖。操作結(jié)果：銷毀圖G。Exist（G，v，w）初始條件：G是已經(jīng)存在的一個圖，v、w是兩個頂點。操作結(jié)果：如果存在邊（v，w）或弧V，w，則返回TRUE，否則返回FALSE。Edges（G）初始條件：G是已經(jīng)存在的一個圖。操作結(jié)果：返回圖中邊的數(shù)目。Vertices（G）初始條件：G是已經(jīng)存在的一個圖。操作結(jié)果：返回圖中頂點的數(shù)目。Add（G，v，w）初始條件：圖G已存在，v，w是兩個頂點。操作結(jié)果：如果G是有向圖，則在G中添加一條弧V，w；如果G是無向圖，則在

13、G中添加一條邊（v，w）。Delete（G，v，w）初始條件：圖G已存在，v，w是兩個頂點。操作結(jié)果：如果G是有向圖，則在G中刪除一條弧V，w；如果G是無向圖，則在G中刪除一條邊（v，w）。Degree（G，v）初始條件：圖G及頂點v已存在。操作結(jié)果：返回圖G中頂點v的度。Indegree（G，v）初始條件：圖G及頂點v已存在。操作結(jié)果：如果G是有向圖，則返回頂點v的入度；如果G是無向圖，則返回圖G中頂點v的度。Outdegree（G，v）初始條件：圖G及頂點v已存在。操作結(jié)果：如果G是有向圖，則返回頂點v的出度；如果G是無向圖，則返回圖G中頂點v的度。DFSTraverse（G，v，visi

14、t（）初始條件：圖G已存在，v是G中的某個頂點，visit是頂點的應(yīng)用函數(shù)。操作結(jié)果：從頂點v起深度優(yōu)先遍歷圖G，并對頂點調(diào)用函數(shù)visit一次且僅一次。一旦visit失敗，則操作失敗。BFSTraverse（G，v，visit（）初始條件：圖G已存在，v是G中的某個頂點，visit是頂點的應(yīng)用函數(shù)。操作結(jié)果：從頂點v起廣度優(yōu)先遍歷圖G，并對頂點調(diào)用函數(shù)visit一次且僅一次。一旦visit失敗，則操作失敗。ADTGraph/Digraph第二節(jié)圖的計算機表示如果編寫程序解決關(guān)于圖的問題，則首先必須找到表示圖的抽象數(shù)據(jù)類型的方法。通常不直接表示邊（或?。┑募希歉鶕?jù)它們與每個獨立頂點的依附

15、關(guān)系來表示。無向圖和有向圖最常用的描述方法都基于鄰接的方式：鄰接矩陣、鄰接鏈表。1、鄰接矩陣表示法一個n個頂點的圖G=（V，E）的鄰接矩陣（AdjacencyMatrix）是一個nn矩陣AdjMatrix，AdjMatrix中的每個元素是0或1。假設(shè)圖G中頂點集合：V=1，2，n，那么AdjMatrix中的元素定義如下：AdjMatrixij=圖5-1的鄰接矩陣如圖5-8所示。注意：對于無向圖，它的鄰接矩陣是對稱的，即AdjMatrixij等于AdjMatrixji。對于帶權(quán)圖，則令A(yù)djMatrixij等于從頂點i到頂點j的邊的權(quán)值，而不是簡單地等于1；如果從頂點i到頂點j之間的邊不存在，則

16、AdjMatrixij等于代替0。例如，圖5-9展示了一個帶權(quán)的有向圖的鄰接矩陣。2、建立圖的鄰接矩陣的算法圖的鄰接矩陣存儲結(jié)構(gòu)的C語言描述形式如下：#defineINFINITYINT_MAX#defineMAX_VERTEX_NUM20typedefenumDG=1,AG,DN,ANGraphKind；/有向圖、無向圖；有向網(wǎng)、無向網(wǎng)typedefstructnodeVertexTypevextex；/頂點信息Node；typedefstructarcsintadj；/頂點鄰接關(guān)系/該邊或弧的相關(guān)信息指針Arcs;typedefstructNodenodesMAX_VERTEX_NUM；/

17、頂點集合ArcsarcsMAX_VERTEX_NUMMAX_VERTEX_NUM；/鄰接矩陣intvexnum,arcnum；/頂點數(shù)和弧數(shù)GraphKindkind;/kind取值1、2、3、4分別表示有向圖、無向圖、有向網(wǎng)、無向網(wǎng)Graph;借助于鄰接矩陣容易判定任意兩個頂點之間是否存在邊（弧），且容易求得各個頂點的度。對于無向圖，頂點vi的度是鄰接矩陣中第i行的元素之和。對于無向圖，第i行的元素之和為頂點的出度，第i列的元素之和則為該頂點的入度。采用鄰接矩陣存儲圖，很容易實現(xiàn)圖的基本操作，下面給出在圖中增加或刪除邊（或弧）的操作的C語言算法。3、在鄰接矩陣存儲的圖上添加、刪除一條邊1在圖

18、中添加一條邊（或弧）根據(jù)圖G的鄰接矩陣的定義，如果在有向圖G中添加一條弧V，w，只需將元素AdjMatrixvw賦值為1即可；如果在無向圖G中添加一條邊（v，w），由于無向圖的鄰接矩陣是對稱的，則需要將AdjMatrixvw和AdjMatrixwv皆賦值為1。voidaddarc（Graph*g，intv，intw）/*在圖g中，增加一條從頂點v到頂點w的邊*/garcsvw.adj=1；if(gkind=2)garcswv.adj=1;return；算法5-1在鄰接矩陣存儲的圖上添加一條邊2在圖中刪除一條邊（?。└鶕?jù)圖G的鄰接矩陣的定義，如果在有向圖G中刪除一條弧V，w，只需將元素AdjMa

19、trixvw賦值為0即可；如果在無向圖G中刪除一條邊（v，w），由于無向圖的鄰接矩陣是對稱的，則需要將AdjMatrixvw和AdjMatrixwv皆賦值為0。voiddeletearc（Graph*g，intv，intw）/*在圖中g(shù)，刪除一條從頂點v到頂點w的邊*/garcsvw.adj=0；if(gkind=2)garcswv.adj=0;return；算法5-2在鄰接矩陣存儲的圖上刪除一條邊下面的C語言程序是在鄰接矩陣存儲結(jié)構(gòu)上對圖的構(gòu)造操作的實現(xiàn)框架，它根據(jù)圖的類型調(diào)用具體的構(gòu)造函數(shù)，并輸出鄰接矩陣。其中，在main()中完成賦初值操作，包括對圖中的每條邊（或?。┑钠瘘c、終點、權(quán)值以

20、及頂點信息、頂點數(shù)、邊數(shù)、圖的類型的賦值；create_1()、create_2()、create_3()、create_4()分別完成有向圖、無向圖、有向網(wǎng)、無向網(wǎng)的鄰接矩陣的構(gòu)建；printf_adjmatrix()完成鄰接矩陣的輸出操作。#include#include#include#defineMAXLEN10#defineLARGE999typedefstructintaMAXLEN,bMAXLEN,wMAXLEN;/*第K邊的起點,終點,權(quán)值*/charvexsMAXLEN;/*頂點信息集合*/intvexnum,arcnum;/*頂點數(shù)和邊數(shù)*/intkind;/*圖的類型*/

21、intarcsMAXLENMAXLEN;/*鄰接矩陣*/Graph;voidcreategraph(Graph*g)/*建立圖的鄰接矩陣結(jié)構(gòu)*/switch(g-kind)case1:create_1(g);break;/case2:create_2(g);break;case3:create_3(g);break;case4:create_4(g);break;default:printf(Errorn);voidprintf_adjmatrix(Graphg)/*輸出鄰接矩陣*/inti,j;printf(鄰接矩陣為:n);printf(vertext);for(i=0;iG.VEXNUM

22、;I+)printf(?%4c?,g.vexsi);printf(n);for(i=0;iG.VEXNUM;I+)printf(%4ct,g.vexsi);for(j=0;jarcsij=0;for(k=0;karcnum;k+)g-arcsg-ak-1g-bk-1=1;printf_adjmatrix(*g);voidcreate_2(Graph*g)/*建立無向圖的鄰接矩陣結(jié)構(gòu)*/inti,j,k;for(i=0;ivexnum;i+)for(j=0;jvexnum;j+)g-arcsij=0;for(k=0;karcnum;k+)g-arcsg-ak-1g-bk-1=1;g-arcsg-

23、bk-1g-ak-1=1;printf_adjmatrix(*g);voidcreate_3(Graph*g)/*建立有向網(wǎng)的鄰接矩陣結(jié)構(gòu)*/inti,j,k;for(i=0;ivexnum;i+)for(j=0;jvexnum;j+)g-arcsij=LARGE;for(k=0;karcnum;k+)g-arcsg-ak-1g-bk-1=g-wk;printf_adjmatrix(*g);voidcreate_4(Graph*g)/*建立無向網(wǎng)的鄰接矩陣結(jié)構(gòu)*/inti,j,k;for(i=0;ivexnum;i+)for(j=0;jvexnum;j+)g-arcsij=LARGE;for(

24、k=0;karcnum;k+)g-arcsg-ak-1g-bk-1=g-wk;g-arcsg-bk-1g-ak-1=g-wk;printf_adjmatrix(*g);main()Graphg;inti,j,k;printf(n請輸入圖的類型(1:有向圖2:無向圖3:有向網(wǎng)4:無向網(wǎng)):);scanf(%d,&g.kind);printf(請輸入頂點數(shù),邊數(shù):);scanf(%d,%d,&g.vexnum,&g.arcnum);printf(請輸入%d個頂點的信息:,g.vexnum);for(i=0;iG.VEXNUM;I+)getchar(g.vexsi);for(k=0;kG.ARCNU

25、M;K+)label:if(g.kind=1|g.kind=3)printf(第%d條邊的起點編號,終點編號:,k+1);elseprintf(第%d條邊的兩個頂點的編號:,k+1);scanf(%d,%d,&g.ak,&g.bk);while(g.akg.vexnum|g.bkg.vexnum)printf(編號超出范圍,重新輸入);gotolabel;if(g.kind=3|g.kind=4)printf(t該邊的權(quán)值:);scanf(%d,&g.wk);elseg.wk=NULL;creategraph(&g);/*創(chuàng)建鄰接矩陣結(jié)構(gòu)的圖*/4、鄰接表存儲結(jié)構(gòu)的數(shù)據(jù)類型鄰接表（Adjace

26、ncyList）是一種順序存儲與鏈?zhǔn)酱鎯ο嘟Y(jié)合的存儲結(jié)構(gòu)，順序存儲部分用來保存圖中頂點信息，鏈?zhǔn)酱鎯Σ糠直４鎴D中邊或弧的信息。具體做法是：圖G被表示為一個數(shù)組或向量v1，v2，vn，每個元素對應(yīng)圖中一個頂點。每個vi存儲頂點vi的信息，以及一個指向包含所有依附于頂點vi的邊組成的單鏈表的指針，vi稱之為頭結(jié)點。頭結(jié)點結(jié)構(gòu)如下圖所示：其中data存放與頂點相關(guān)的信息，firstarc是指針；鄰接單鏈表中每個結(jié)點表示依附于該頂點的一條邊（對于有向圖則是以頂點vi為尾的?。?，稱為邊（?。┙Y(jié)點。其中adjvex存放依附于該邊的另一個頂點在一維數(shù)組中的序號，對于有向圖，存放的是該弧結(jié)點所表示的弧的弧頭頂

27、點在一維數(shù)組中的序號；nextarc為指向下一條邊（或?。┙Y(jié)點的指針；info存儲和邊或弧相關(guān)的信息，如權(quán)值等。5、建立鄰接表表示圖的算法圖的鄰接表存儲結(jié)構(gòu)的C語言描述形式如下：#defineMAXLEN10typedefstructnode/*邊結(jié)點結(jié)構(gòu)*/intadjvex;/*存放與頭結(jié)點相鄰接的頂點在數(shù)組中的序號*/intinfo;/*權(quán)值等信息*/structnode*nextarc;/*指向與頭結(jié)點相鄰接下一個頂點的表結(jié)點*/EdgeNode;typedefstruct/*頭結(jié)點結(jié)構(gòu)*/intid;/*頂點入度*/chardata;/*頂點信息*/EdgeNode*firstarc

28、;/*指向頭結(jié)點對應(yīng)的單鏈表中的表結(jié)點*/VexNode;typedefstruct/*鄰接表結(jié)構(gòu)*/VexNodeadjsMAXLEN;/*鄰接表的頭結(jié)點集合*/intvexnum,arcnum;/*頂點數(shù),邊數(shù)*/intkind;/*圖的種類*/AdjList;顯然，當(dāng)圖中頂點數(shù)較多，而邊或弧數(shù)目較少時，采用鄰接表存儲結(jié)構(gòu)可以節(jié)省大量的存儲單元。另外，對于無向圖如果采用鄰接表存儲結(jié)構(gòu)，則很容易確定圖中每個頂點的度，因為只要查看一下依附于該頂點的鏈表中邊結(jié)點的個數(shù)即可。有向圖采用鄰接表存儲結(jié)構(gòu)時，很容易確定圖中每個頂點的出度，該頂點的出度等于依附于該頂點的鏈表中弧結(jié)點的個數(shù)。但如果要求圖中第

29、i個頂點的入度，則需要掃描整個鄰接表，統(tǒng)計各條單鏈表中各個弧結(jié)點的adjvex域出現(xiàn)i值的次數(shù)。所以，如果實際問題中，需要頻繁計算有向圖中頂點的入度，一般需要另建一個逆鄰接表。逆鄰接表的結(jié)構(gòu)與鄰接表的結(jié)構(gòu)相同，只是圖中頂點vi對應(yīng)的單鏈表中的弧結(jié)點表示的是以vi為頭的弧，其中的adjvex域存放的是該弧結(jié)點所表示弧的弧尾頂點的序號。在圖中，頂點是沒有先后順序的，但當(dāng)我們采用某一種確定的存儲方式將其存儲后，頂點的存儲順序就構(gòu)成了頂點之間的相對順序。我們用頂點的存儲順序表示該頂點在圖中“位置”。在此意義下，圖的基本操作還包括：LocateVertex（G，v）初始條件：圖G及頂點v已存在。操作結(jié)果

30、：求得頂點v在圖G中的位置。FirstVertex（G，v）初始條件：圖G及頂點v已存在。操作結(jié)果：求出圖中頂點v的第一個鄰接點。NextVertex（G，v，w）初始條件：圖G及頂點v、w已存在。操作結(jié)果：圖G中與頂點v相鄰接的頂點w的下一個鄰接點。即求頂點v的某個鄰接點，它的存儲順序排在鄰接點w的存儲位置之后。圖的鄰接表存儲結(jié)構(gòu)是一種很常用的存儲結(jié)構(gòu)，算法5-3和算法5-4分別實現(xiàn)了在鄰接表存儲結(jié)構(gòu)上CreateGraph、Delete操作。為了簡化書寫，假設(shè)頂點信息類型為整數(shù)類型。在算法5-3中，為了更方便地創(chuàng)建圖G的鄰接表，假設(shè)圖G的賦初值操作已完成，包括圖中的每條邊（或?。┑钠瘘c、終

31、點、權(quán)值以及頂點信息、頂點數(shù)、邊數(shù)、圖的類型均已賦值。算法5-3的C語言描述如下：AdjListcreatelist(Graphg,AdjListadjl)/*創(chuàng)建圖g的鄰接表*/inti;EdgeNode*p;adjl.vexnum=g.vexnum;adjl.arcnum=g.arcnum;adjl.kind=g.kind;for(i=0;iADJL.VEXNUM;span*生成頭結(jié)點*/adjl.adjsi.data=g.vexsi;adjl.adjsi.firstarc=NULL;adjl.adjsi.id=0;if(g.kind=1|g.kind=3)/*建立有向圖、有向網(wǎng)的鄰接表*

32、/for(i=0;iadjvex=g.bi-1;pinfo=g.wi;pnextarc=adjl.adjsg.ai-1.firstarc;adjl.adjsg.ai-1.firstarc=p;adjl.adjsg.bi-1.id+;if(g.kind=2|g.kind=4)/*建立無向圖、無向網(wǎng)的鄰接表*/for(i=0;iadjvex=g.bi-1;pinfo=g.wi;pnextarc=adjl.adjsg.ai-1.firstarc;adjl.adjsg.ai-1.firstarc=p;adjl.adjsg.bi-1.id+;p=(EdgeNode*)malloc(sizeof(Edge

33、Node);padjvex=g.ai-1;pinfo=g.wi;pnextarc=adjl.adjsg.bi-1.firstarc;adjl.adjsg.bi-1.firstarc=p;adjl.adjsg.ai-1.id+;printf(鄰接表為:n);for(i=0;iG.VEXNUM;I+)span*輸出鄰接表*/printf(%d,%c=,i+1,adjl.adjsi.data);p=adjl.adjsi.firstarc;while(p!=NULL)printf(%c,%d-,adjl.adjsp-adjvex.data,p-info);p=pnextarc;printf(n);re

34、turnadjl;算法5-3建立鄰接表存儲表示的圖6、鄰接表與鄰接矩陣的比較在解決具體的應(yīng)用問題時，圖的鄰接矩陣存儲表示和鄰接表存儲表示哪一種更好呢？比如本章第一節(jié)中例1，航線圖是采用鄰接表還是鄰接矩陣存儲呢？答案取決于對圖實施的最頻繁的操作是什么。例如，對圖進行的兩種最常見的操作是：l確定是否存在一條從頂點i到頂點j的邊；l查找與給定頂點i鄰接的所有頂點。使用鄰接矩陣進行第一種操作的效率比鄰接表稍高。利用鄰接矩陣確定從頂點i到頂點j是否存在一條邊，只需要檢查AdjMatrixij的值即可。然而，如果使用鄰接表，則必須遍歷第i個鏈表來確定對應(yīng)的頂點j的邊結(jié)點是否存在。另一方面，鄰接表能夠更加有

35、效的支持第二種操作。已知鄰接矩陣，為了確定給定頂點i的所有鄰接頂點，必須遍歷矩陣的第i行；然而，利用鄰接表，只需遍歷第i個鏈表。對于具有n個頂點的圖而言，鄰接矩陣的第i行總有n個元素，而鄰接表的第i個鏈表只有與頂點i鄰接的頂點數(shù)那么多的結(jié)點，這個數(shù)字通常比n小得多。對于航線圖采用鄰接表存儲結(jié)構(gòu)較好，因為最常用的操作是查找所有與給定城市（頂點）鄰接的城市。從空間需求來考慮這兩種存儲結(jié)構(gòu)，鄰接矩陣總有n2個元素，空間復(fù)雜性為O（n2）。而鄰接表中結(jié)點數(shù)等于有向圖的弧數(shù)或者無向圖的邊數(shù)的兩倍，即使加上n個頭結(jié)點，空間復(fù)雜度為O（n+e）,e為邊（或?。?shù)。如果在圖中頂點數(shù)固定不變的情況下，對于增加、

36、刪除邊（或?。┑牟僮鳎ㄟ^算法5-2與算法5-4比較可知：采用鄰接矩陣要比使用鄰接表更好。但如果對于圖結(jié)構(gòu)本身需要在解決問題過程中動態(tài)地產(chǎn)生的情況，鄰接表則是最佳選擇。7、十字鏈表結(jié)構(gòu)特點十字鏈表是存儲有向圖的一種存儲方法，它實際上是將圖的鄰接表與逆鄰接表結(jié)合在一起。在十字鏈表中，仍然用一維數(shù)組存儲圖的各個結(jié)點，但頭結(jié)點的結(jié)構(gòu)變?yōu)槠渲?，vertex域存放與頂點相關(guān)的信息，firstin和firstout均為指針域，firstin存放以該頂點為弧頭的單鏈表的頭指針，firstout存放以該頂點為弧尾的單鏈表的頭指針。同時，鏈表中的邊結(jié)點結(jié)構(gòu)變?yōu)槠渲?，headvex域存放該弧的弧頭頂點在數(shù)組中的序

37、號；tailvex域存放該弧的弧尾頂點在數(shù)組中的序號；info域存放弧具有的權(quán)值等信息；hlink為指針域，它指向與該弧具有相同弧頭的下一條弧的邊結(jié)點；tlink也為指針域，它指向與該弧具有相同弧尾的下一條弧的邊結(jié)點。一個有向圖及其十字鏈表。十字鏈表存儲結(jié)構(gòu)的C語言描述如下：#defineMAX_VERTEX_NUM20typedefstructArcBoxinttailvex,headvex;structArcBox*hlink,*tlink;InfoType*info;ArcBox;typedefstructVexNodeVertexTypevertex;ArcBox*firstin,*f

38、irstout;VerNode;typedefstructVerNodexlistMAX_VERTEX_NUM;intvexnum,arcnum;OLGraph;8、鄰接多重表的特點鄰接多重表是存儲無向圖的一種存儲方法。在無向圖的鄰接表存儲結(jié)構(gòu)中，表示同一條邊的邊結(jié)點有兩個，它們分別出現(xiàn)在以此邊的兩個頂點為頭結(jié)點的鏈表中。在實際問題中，有時要對圖中的邊進行某種操作，如刪除一條邊，這時就需要兩次掃描鄰接表，找到表示同一條邊的兩個邊結(jié)點并進行刪除，顯然，這給操作帶來不便。鄰接多重表是對鄰接表的一種改進，在鄰接多重表中，表示一條邊的邊結(jié)點只有一個。其中，mark域為標(biāo)志域，用來標(biāo)記此邊是否被訪問過；

39、ivertex域和jvertex域分別存放此邊的兩個頂點在圖中的位置；info域存放邊的權(quán)值；ilink和jlink為指針域，分別指向與此邊的兩個頂點相關(guān)聯(lián)的其他邊結(jié)點。在鄰接多重表中，存儲圖中頂點信息的一維數(shù)組的結(jié)構(gòu)與鄰接表相同。第三節(jié)圖的遍歷圖的遍歷是圖結(jié)構(gòu)的一種基本操作，圖的許多其它操作則建立在遍歷基礎(chǔ)之上。由于圖結(jié)構(gòu)的復(fù)雜性，所以它的遍歷操作也較復(fù)雜。本節(jié)介紹圖遍歷的兩種基本方法：深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷。1、深度優(yōu)先搜索遍歷的策略圖的深度優(yōu)先搜索（Depth-FirstSearch，DFS）策略是從給定頂點v出發(fā)，在回溯之前，沿著從v出發(fā)的一條路徑盡可能深入前進。其遍歷規(guī)則

40、為：從v出發(fā)，訪問v的一個未被訪問的鄰接頂點w1，再從w1出發(fā)，訪問w1的一個未被訪問的鄰接頂點w2，然后從w2出發(fā)，訪問w2的一個未被訪問的鄰接頂點w3，如此下去，直到一個所有鄰接點都被訪問過的頂點為止。然后回溯到尚有鄰接點未被訪問的頂點，重復(fù)上述過程，直到圖中所有與v有路徑相通的頂點都被訪問過；此時，若圖中還存在未被訪問過的頂點，則從其中一個未被訪問過的頂點出發(fā)，重復(fù)上述過程，直到圖中所有頂點都被訪問為止。例如，對于有向圖5-14的一個深度優(yōu)先搜索從頂點A開始，有可能首先訪問A，B，F(xiàn)，I，H；接著回溯到I，但從它已經(jīng)無法到達任何一個未被訪問過的頂點，所以回溯到F，并從F訪問到G，再從G到

41、達頂點C和D（也可以到達B、F、I和H，但它們已經(jīng)被訪問過了）；然后再回溯到C，但從它也無法到達任何一個未被訪問過的頂點，所以回溯到G；同樣發(fā)現(xiàn)從G也無法到達任何一個未被訪問過的頂點，回溯到F，再回溯到B，從這些頂點都無法到達未被訪問過的頂點；最后，回溯到A，從A可以到達最后一個未被訪問過的頂點E。這樣，深度優(yōu)先搜索遍歷頂點的順序為：A，B，F(xiàn)，I，H，G，C，D，E。如果從某些頂點開始深度優(yōu)先搜索，或許不能到達所有其他頂點。例如，從B開始的一個深度優(yōu)先搜索將訪問到頂點B、F、I、H、G、C、D，但無法到達A、E。這時，需要再從其中一個未被訪問過的頂點出發(fā)，繼續(xù)進行深度優(yōu)先搜索。根據(jù)深度優(yōu)先搜

42、索的遍歷規(guī)則，我們可以給出其遞歸算法，遞歸算法思想描述如下：（1）訪問起始頂點v。（2）對于每個鄰接于v的頂點w，如果w未被訪問，則將w作為起始頂點，應(yīng)用深度優(yōu)先搜索算法。2、深度優(yōu)先搜索遍歷的算法voiddepth_traversal（AdjListg，intn）/*圖g采用鄰接表存儲結(jié)構(gòu)*/inti，visitedMAXLEN；for(i=0；iN；i+)visitedi=0；for(i=0；iN；i+)if(visitedi=0)dfs(g，i，visited)；voiddfs（AdjListg，intk，intvisited）/*從頂點k出發(fā)，深度優(yōu)先搜索遍歷圖g*/EdgeNode*

43、p；intw；visitedk=1；printf（“%dn”，k）；p=g.adjsk.firstarc；w=padjvex；while（p!=NULL）if（visitedw=0）dfs(g，w，visited)；p=pnextarc；w=padjvex；算法5-5深度優(yōu)先搜索遍歷圖3、廣度優(yōu)先搜索遍歷的策略圖的廣度優(yōu)先搜索（Broad-FirstSearch，BFS）策略是在訪問給定頂點v之后，先訪問與v鄰接的所有頂點w1、w2、wk，然后再依次從w1、w2、wk出發(fā)，訪問它們的未被訪問過的鄰接頂點，重復(fù)上述操作，直到圖中所有被訪問過的頂點的鄰接頂點都被訪問為止。若此時圖中還有未被訪問過的

44、頂點，則從一個未被訪問過的頂點出發(fā)，重復(fù)上述過程，直到圖中所有的頂點都被訪問過為止。例如，對前面的有向圖5-14的一個廣度優(yōu)先搜索中從A出發(fā)訪問A，接著訪問A的鄰接頂點B、D、E，然后選擇A的第一個鄰接頂點B，并訪問所有鄰接于B的尚未被訪問過的頂點F；對于A的下一個鄰接點D，重復(fù)上面過程，訪問未被訪問的頂點C、H；再接著，對于A的最后一個鄰接點E，它的唯一的鄰接點H已被訪問過，不再繼續(xù)訪問。訪問F、C、H之后，再繼續(xù)對它們的未被訪問過的鄰接點進行廣度優(yōu)先搜索，依次訪問G、I，至此圖中所有頂點皆被訪問過，搜索結(jié)束。同深度優(yōu)先搜索一樣，從某些頂點開始的一個廣度優(yōu)先搜索有可能不能訪問圖中所有的頂點。

45、例如，對于圖5-14，從B開始的一個廣度優(yōu)先搜索可以首先訪問B和F，接著訪問G和I，再下面訪問H和C，最后訪問D，而A和E則無法從B到達。從廣度優(yōu)先搜索遍歷過程可以看出，最先探測的頂點最先訪問，符合隊列的“先進先出”特征。因此，在廣度優(yōu)先搜索中使用隊列是自然而然的。廣度優(yōu)先搜索算法的基本思想是：（1）訪問起始頂點。（2）初始化一個隊列為僅包含起始頂點。（3）當(dāng)這個隊列非空時，做以下工作：從隊列中刪除一個頂點v。對于所有鄰接于v的頂點w，如果w未被訪問，則訪問w，并將w添加到隊列中。4、廣度優(yōu)先搜索遍歷的算法假設(shè)圖采用鄰接表存儲結(jié)構(gòu)，廣度優(yōu)先搜索算法的C語言描述如下：voidBFS(inti,A

46、djListadjl)/*從頂點i出發(fā)廣度優(yōu)先搜索*/EdgeNode*p;intj;intvisitedMAXLEN;for(j=0;jADJL.VEXNUM;J+)span*初始化所有點*/InitQueue(q);printf(%4c-,adjl.adjsi-1.data);visitedij-1=1;EnQueue(q,i);while(!QueueEmpty(q)j=DeQueue(q);p=adjl.adjsj-1.firstarc;while(p!=NULL)if(visitedpadjvex=0)printf(%4c-,adjl.adjspadjvex.data);visite

47、dp-adjvex=1;EnQueue(q,padjvex+1);p=pnextarc;算法5-6廣度優(yōu)先搜索遍歷圖5、遍歷的應(yīng)用之一：生成樹在對無向圖或有向圖進行遍歷時，對于連通圖，僅需從圖中任一頂點出發(fā)，進行深度優(yōu)先搜索或廣度優(yōu)先搜索，便可訪問到圖中所有頂點。對非連通圖，則需從多個頂點出發(fā)進行搜索，而每一次從一個新的起始點出發(fā)進行搜索過程中得到的頂點訪問序列恰為其各個連通分量中的頂點集。例如，圖5-4中的G3是非連通無向圖，按照圖5-15所示G3的鄰接表進行深度優(yōu)先搜索遍歷，三次調(diào)用DFS過程(分別從頂點A、D和G出發(fā))得到的頂點訪問序列為：ALMJBFCDEGKHI這三個頂點集分別加上所

48、有依附于這些頂點的邊，便構(gòu)成了非連通圖G3的三個連通分量，如圖5-4(b)所示。設(shè)E（G）為連通圖G中所有邊的集合，則從圖中任一頂點出發(fā)遍歷圖時，必定將E（G）分成兩個集合T（G）和B（G），其中T（G）是遍歷圖過程中歷經(jīng)的邊的集合；B(G)是剩余的邊的集合。顯然，T(G)和圖G中所有頂點一起構(gòu)成連通圖G的極小連通子圖即生成樹，并且稱由深度優(yōu)先搜索得到的生成樹為深度優(yōu)先生成樹，由廣度優(yōu)先搜索得到的生成樹為廣度優(yōu)先生成樹。考察圖5-16（a）中的圖，如果從頂點1開始BFS，生成樹為5-16（b），如果從頂點8和頂點6開始BFS得到的生成樹分別為圖5-16（c）和（d）。對于非連通圖，每個連通分量

49、中的頂點集，和遍歷時走過的邊一起構(gòu)成若干棵生成樹，這些連通分量的生成樹組成非連通圖的生成森林。6、遍歷的應(yīng)用：尋找路徑若從起始頂點出發(fā)開始搜索（深度優(yōu)先或廣度優(yōu)先）且到達目的頂點終止搜索，則可以找到一條從起始頂點到目的頂點的路徑。計算機網(wǎng)絡(luò)中的路由問題是需要圖的搜索算法的問題，在這類問題中，必須在一個網(wǎng)絡(luò)中找到一條優(yōu)化的路徑：一個圖或有向圖的最短路徑，一個帶權(quán)圖或帶權(quán)有向圖的代價最小的路徑。作為路由問題的簡單例子，對于本章第一節(jié)的例5-1，乘客可能對兩個城市之間的最直接路線很感興趣，也就是兩個城市之間的具有最少中間點（或中轉(zhuǎn)站）的路線。我們用圖來模擬航線，上述問題就轉(zhuǎn)變?yōu)榍笕∫粭l從起始頂點到目

50、的頂點之間的最小數(shù)目的弧所組成的最短路徑。求取這樣一條最短路徑的算法可利用廣度優(yōu)先搜索算法的一個簡單修改來實現(xiàn)：（1）訪問起始頂點start，并將其標(biāo)簽置為0；（2）初始化distance為0；（3）初始化一個隊列為僅包含start；（4）當(dāng)目的頂點destination還未被訪問并且隊列非空時，做如下工作（循環(huán)操作）：從隊列中刪除頂點v。如果v的標(biāo)簽大于distance，將distance加1。對于鄰接于v的每一個頂點w，如果w未被訪問，則訪問w，并將其標(biāo)簽置為distance+1；將w添加到隊列中。（5）如果目的頂點destination還未被訪問，則顯示“從起始頂點無法到達目的頂點”，否

51、則，如下查找最短路徑中的頂點p0，pdistance：初始化pdistance為destination。對于從distance-10的每一個值k，找到鄰接于pk+1并且標(biāo)簽為k的一個頂點pk。表5-1跟蹤了這個算法在前面給出的圖5-14中查找從頂點A到頂點H的最短路徑時算法第一部分的執(zhí)行。表5-1步驟vdistance隊列標(biāo)簽ABCDEFGHI1，2，34444444ABDEFCH00111222ABDEDEFEFCHFCHCHGIHGI001110111201211220121122012112323012112323012112323接著，步驟5決定了從A到H的一條路徑上的一系列頂點，例如

52、，p2=“H”，p1=“D”，p0=“A”。第四節(jié)圖的應(yīng)用之一最小生成樹工程設(shè)計中的造價問題，可借助于求圖的最小生成樹實現(xiàn)。構(gòu)造最小生成樹的兩種常用算法是普里姆（Prim）算法和克魯斯卡爾（Kruskal）算法。1、普里姆（Prim）算法的思想假設(shè)G=（V，E）為一個網(wǎng)絡(luò)，其中V為網(wǎng)中所有頂點的集合，E是網(wǎng)中所有帶權(quán)邊的集合。設(shè)立兩個新集合U和T，其中集合U用于存放G中最小生成樹的頂點，T用于存放G的最小生成樹的邊。集合U的初始值僅含有起始頂點，假設(shè)構(gòu)造最小生成樹時，從頂點u1開始，那么U=u1。集合T的初始值為T=。Prim算法的思想是，從所有uU、vV-U的邊中，選取具有最小權(quán)值的邊（u,

53、v），將頂點v加入集合U，并將邊（u,v）加入集合T中，如此不斷重復(fù)，直到U=V時，最小生成樹構(gòu)造完畢。Prim算法可用下述過程描述：（1）U=u1，T=，標(biāo)記u1為已被訪問；（2）while（UV）do（u，v）=minWuv；uU、vV-U；T=T+（u，v）；標(biāo)記v為已被訪問；U=U+v；（3）結(jié)束。為了實現(xiàn)Prim算法，需要設(shè)置兩個輔助數(shù)組lowcost和closevex，其中l(wèi)owcost為一維數(shù)組，用于保存集合V-U中各頂點與集合U中各個頂點構(gòu)成的所有邊中具有最小權(quán)值的邊的權(quán)值；數(shù)組closevex也是一個一維數(shù)組，用于保存該邊在集合U中的頂點。我們利用這兩個輔助數(shù)組來標(biāo)記在生成樹

54、求解過程中已經(jīng)加入到生成樹中的頂點和邊。具體實現(xiàn)是：假設(shè)初始狀態(tài)為U=u1，這時lowcost1=0，表示頂點u1已經(jīng)加入到集合U中；lowcost的其他分量的值是頂點u1到其余頂點所構(gòu)成的直接邊的權(quán)值。然后不斷選取權(quán)值最小的邊（ui，uk），其中uiU而ukV-U，并將lowcostk置為0，表示頂點uk已經(jīng)加入集合U中。由于頂點由集合V-U進入集合U，從而引起這兩個集合的內(nèi)容發(fā)生變化，所以此時還需要根據(jù)具體情況對數(shù)組lowcost和closevex的部分分量進行更新。2、普里姆（Prim）算法的C語言實現(xiàn)#defineMAXCOST9999voidprim(Graphg)/*從頂點v1出發(fā)

55、的最小生成樹*/inti,j,k,min;intlowcostMAXLEN;/*權(quán)值*/intclosevexMAXLEN;/*最小生成樹結(jié)點*/for(i=1;iG.VEXNUM;I+)span*初始化*/lowcosti=g.arcs0i;closevexi=0;lowcost0=0;for(i=1;iG.VEXNUM;I+)span*尋找當(dāng)前最小權(quán)值的邊的頂點*/min=MAXCOST;k=1;j=1;while(jG.VEXNUM)if(lowcostjMIN&LOWCOSTJ!=0)min=lowcostj;k=j;j+;printf(%5d%5dn,k,min);lowcostk=

56、0;for(j=1;jG.VEXNUM;J+)span*修改其它頂點的邊的權(quán)值*/if(g.arcskjLOWCOSTJ)lowcostj=g.arcskj;closevexj=k;算法5-7Prim算法3、克魯斯卡爾（Kruskal）算法的思想Kruskal算法是一種按照網(wǎng)中邊的權(quán)值遞增的順序構(gòu)造最小生成樹的方法。它的基本思想是：假設(shè)G=（V，E）為一個無向連通網(wǎng)絡(luò)，其中V為網(wǎng)中所有頂點的集合，E是網(wǎng)中所有帶權(quán)邊的集合。利用集合T求G的最小生成樹，其初始態(tài)為T=（V，），即開始時，最小生成樹T僅含有圖G的n個頂點，而不包含任何一條邊，這樣T中的各個頂點就各自構(gòu)成一個連通分量。然后根據(jù)邊的權(quán)值

57、不減的原則，選取符合下面條件的邊加入到生成樹T中，選取條件為：一條邊的兩個頂點分別屬于兩個不同的連通分量且權(quán)值最小，同時將兩個獨立的連通分量連接為一個連通分量。重復(fù)上述過程，直到T中只含有一個連通分量，此連通分量即為一棵最小生成樹。第五節(jié)圖的應(yīng)用之二拓撲排序與關(guān)鍵路徑對整個工程和系統(tǒng)而言，人們所關(guān)心的無外乎于兩個問題，一是工程能否順利進行，二是估算整個工程完成所必須的最短時間，對于有向圖，即為進行拓撲排序和關(guān)鍵路徑的操作。1、拓撲排序的實現(xiàn)算法所謂拓撲排序是指將頂點按照拓撲次序排列。有幾種簡單的算法可以求出一個圖的拓撲次序。一種算法的思想如下：（1）在有向圖中查找一個沒有后繼（或前驅(qū)）的頂點并

58、添加到頂點表中。（2）從圖中刪除該頂點和所有以該頂點為頭（尾）的弧。重復(fù)上述兩步，當(dāng)圖為空時，頂點表將以拓撲次序出現(xiàn)。描述這個算法的偽代碼如下：Topsort1（DAGtheGraph）/ArrangestheverticesingraphtheGraphintoatopologicalorder/andplacestheminlistaListn=vexnum/將有向無環(huán)圖的頂點數(shù)賦給nWhile（n）selectavertexvthathasnosuccessors；insertlist（aList，v）;/將頂點v添加到頂點表alist中deletefromtheGraphvertexv

59、anditsedges;returnaLlist;另一種算法是對遞歸的深度優(yōu)先搜索算法的簡單修改。首先，將沒有前驅(qū)的頂點入棧；每次從棧中彈出一個頂點，將它添加到頂點表的頭部，。這個算法的C語言代碼如下：Statustopsort(AdjListadjl)/*拓撲排序*/inti,k,count;EdgeNode*p;printf(拓撲排序序列為:n);InitStack(s);for(i=0;i,adjl.adjsi.data);+count;for(p=adjl.adjsi.firstarc;p;p=pnextarc)k=padjvex;if(!(-adjl.adjsk.id)Push(s,

60、k);if(countADJL.VEXNUM)span*拓撲排序輸出的頂點數(shù)圖中的頂點數(shù)*/printf(n網(wǎng)中有環(huán)!n);returnERROR;elsereturnOK;算法5-8拓撲排序算法2、AOE網(wǎng)在工程規(guī)劃中，經(jīng)常需要考慮這樣的問題，完成整個工程最短需要多長時間，工程中哪些工序是一些重要的活動，縮短這些活動的時間，可以縮短整個工程的工期。在生產(chǎn)管理中，也存在這樣的問題，一件產(chǎn)品有多道工序，減少哪道工序的時間可以縮短產(chǎn)品的生產(chǎn)時間。諸如此類的問題，可以用AOE網(wǎng)來描述和分析。所謂AOE（ActivityOnEdge）網(wǎng)是指頂點表示事件，弧表示活動，弧上的權(quán)值表示活動持續(xù)時間的有向網(wǎng)。