六、樹(shù)和二叉樹(shù)的回顧課件

1、第六章回顧樹(shù)的定義和基本術(shù)語(yǔ) 子樹(shù) 孩子 葉子 兄弟 度 二叉樹(shù)的性質(zhì) 2k-1 2k-1 n0=n2+1 log2n+1 i的雙親 i/2； 2in， i無(wú)左孩子 ；2i+1n， i無(wú)右孩子二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉鏈表、三叉鏈表二叉樹(shù)的遍歷先序遍歷、中序遍歷、后序遍歷 線索二叉樹(shù) 在二叉鏈表的基礎(chǔ)上增加兩個(gè)標(biāo)志域，表示按某種次序遍歷時(shí)的前驅(qū)和后繼樹(shù)的三種存儲(chǔ)結(jié)構(gòu)雙親表示法孩子鏈表表示法孩子兄弟表示法森林和二叉樹(shù)的轉(zhuǎn)換 由森林轉(zhuǎn)換為二叉樹(shù) 由二叉樹(shù)轉(zhuǎn)換為森林樹(shù)和森林的遍歷樹(shù)的先根遍歷（= 二叉樹(shù)的先序遍歷）樹(shù)的后根遍歷（= 二叉樹(shù)的中序遍歷）森林的先序遍歷（= 二叉樹(shù)的先序遍歷）森林的中序遍歷（=

2、 二叉樹(shù)的中序遍歷）赫夫曼樹(shù)和赫夫曼編碼課前思考1、如何確定一項(xiàng)工程的工期？最佳工期如何計(jì)算？（關(guān)鍵路徑問(wèn)題）2、如何以最低造價(jià)架構(gòu)城市之間的通信網(wǎng)？幾個(gè)小區(qū)之間要建一個(gè)供水站，建在什么位置最合適？（最小生成樹(shù)問(wèn)題）3、如何合理安排大一到大四的教學(xué)計(jì)劃？（拓?fù)渑判騿?wèn)題）4、從上海到北京怎么走最省時(shí)間或金錢(qián)？如何花費(fèi)最少周游所有城市？ （最短路徑問(wèn)題）例北京上海南京濟(jì)南徐州280500320180160600260200青島連200課前導(dǎo)學(xué)7.1 圖的定義和術(shù)語(yǔ)7.2 圖的存儲(chǔ)結(jié)構(gòu)7.3 圖的遍歷7.4 圖的應(yīng)用7.5 總結(jié)與提高第七章 圖【重點(diǎn)和難點(diǎn)】 理解各種圖的算法及其應(yīng)用場(chǎng)合。 【知識(shí)點(diǎn)

3、】圖的類型定義、圖的存儲(chǔ)表示、圖的深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷、無(wú)向網(wǎng)的最小生成樹(shù)、最短路徑、拓?fù)渑判颉㈥P(guān)鍵路徑【學(xué)習(xí)指南】數(shù)據(jù)結(jié)構(gòu)中對(duì)圖的討論側(cè)重于在計(jì)算機(jī)中如何表示圖以及如何實(shí)現(xiàn)圖的操作和應(yīng)用等。圖是較線性表和樹(shù)更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，因此和線性表、樹(shù)不同，雖然在遍歷圖的同時(shí)可以對(duì)頂點(diǎn)或弧進(jìn)行各種操作，但更多圖的應(yīng)用問(wèn)題如求最小生成樹(shù)和最短路徑等在圖論的研究中都早已有了特定算法，在本章中主要是介紹它們?cè)谟?jì)算機(jī)中的具體實(shí)現(xiàn)，應(yīng)多對(duì)照具體圖例的存儲(chǔ)結(jié)構(gòu)進(jìn)行學(xué)習(xí)。而圖遍歷的兩種搜索路徑和樹(shù)遍歷的兩種搜索路徑極為相似，應(yīng)將兩者的算法對(duì)照學(xué)習(xí)。 有向圖(Digraph)有向圖G是由兩個(gè)集合V(G)

4、和E(G)組成的，其中：V(G)是頂點(diǎn)的非空有限集，E(G)是有向邊（也稱?。┑挠邢藜希∈琼旤c(diǎn)的有序?qū)?，記為，v,w是頂點(diǎn)，v為弧尾，w為弧頭例245136G1圖G1中：V(G1)=1,2,3,4,5,6 E(G1)=, , , , , , 無(wú)向圖(Undigraph)無(wú)向圖G是由兩個(gè)集合V(G)和E(G)組成的其中：V(G)是頂點(diǎn)的非空有限集，E(G)是邊的有限集合，邊是頂點(diǎn)的無(wú)序?qū)?，記為（v,w）或（w,v)，并且（v,w)=(w,v)例157324G26圖G2中：V(G2)=1,2,3,4,5,6,7 E(G1)=(1,2), (1,3), (2,3), (2,4),(2,5), (

5、5,6), (5,7)有向完備圖n個(gè)頂點(diǎn)的有向圖最大邊數(shù)是n(n-1)無(wú)向完備圖n個(gè)頂點(diǎn)的無(wú)向圖最大邊數(shù)是n(n-1)/2例213213有向完備圖無(wú)向完備圖稀疏圖有很少條邊或弧的圖（enlogn) 粗略：e(n-1)稠密圖有很多條邊或弧的圖例G21573246例157324G26稀疏圖稠密圖子圖如果圖G(V,E)和圖G(V,E),滿足：VV EE 則稱G為G的子圖0123子圖0130123023356例245136圖與子圖權(quán)(Weight)與圖的邊或弧相關(guān)的數(shù),可以表示兩個(gè)頂點(diǎn)之間的距離或耗費(fèi)網(wǎng)帶權(quán)的圖上海北京 怎么走最優(yōu)?例北京上海南京濟(jì)南徐州280500320180160600260200

6、青島連200例157324G26路徑：1，2，5，7，6，5，2，3路徑長(zhǎng)度：7簡(jiǎn)單路徑：1，2，5，7，6回路：1，2，5，7，6，5，2，1簡(jiǎn)單回路：1，2，3，1連通從頂點(diǎn)V到頂點(diǎn)W有路徑，則說(shuō)V和W是連通的；連通圖無(wú)向圖中任意兩個(gè)頂點(diǎn)都是連通的連通分量無(wú)向圖中的極大連通子圖強(qiáng)連通圖有向圖中，對(duì)每一對(duì)Vi,VjV, ViVj,從Vi到Vj 和從Vj到 Vi都存在路徑強(qiáng)連通分量有向圖中的極大強(qiáng)連通子圖強(qiáng)連通圖（有向圖）356例連通圖例245136非強(qiáng)連通圖例2413例2413非強(qiáng)連通圖的兩個(gè)強(qiáng)連通分量2. 圖的抽象數(shù)據(jù)類型ADT Graph 數(shù)據(jù)對(duì)象V：V是具有相同特性的數(shù)據(jù)元素的集合，稱

7、為頂點(diǎn)集。數(shù)據(jù)關(guān)系R：RVR VR| v,wV且P(v,w)，表示從v到w的弧，謂詞P(v,w)定義了弧的意義或信息 基本操作P：結(jié)構(gòu)的建立和銷毀: CreateGraph(&G,V,VR); / 按V和VR的定義構(gòu)造圖G DestroyGraph(&G); / 銷毀圖G 對(duì)頂點(diǎn)的訪問(wèn)操作: LocateVex(G, u); / 若G中存在頂點(diǎn)u，則返回該頂點(diǎn)在圖中位置；否則返回其它信息。 GetVex(G, v); / 返回v的值 PutVex(&G, v, value); / 對(duì)v賦值value 對(duì)鄰接點(diǎn)的操作: FirstAdjVex(G, v); / 返回v的第一個(gè)鄰接點(diǎn)。若該頂點(diǎn)在G

8、中沒(méi)有鄰接點(diǎn)，則返回“空” NextAdjVex(G, v, w); /返回v的（相對(duì)于w的）下一個(gè)鄰接點(diǎn)若w是v的最后一個(gè)鄰接點(diǎn)，則返回“空” 插入或刪除頂點(diǎn): InsertVex(&G, v); / 在圖G中增添新頂點(diǎn)v DeleteVex(&G, v); / 刪除G中頂點(diǎn)v及其相關(guān)的弧 插入和刪除弧: InsertArc(&G, v, w); / 在G中增添弧，若G是無(wú)向的，則還增添對(duì)稱弧 DeleteArc(&G, v, w); /在G中刪除弧，若G是無(wú)向的，則還刪除對(duì)稱弧遍歷: DFSTraverse(G, v, Visit(); / 從頂點(diǎn)v起深度優(yōu)先遍歷圖G，并對(duì)每個(gè)頂點(diǎn)調(diào)用函數(shù)

9、Visit一次且僅一次 BFSTraverse(G, v, Visit(); / 從頂點(diǎn)v起廣度優(yōu)先遍歷圖 G，并對(duì)每個(gè)頂點(diǎn)調(diào)用函數(shù)Visit一次且僅一次7.2 圖的存儲(chǔ)結(jié)構(gòu)（1）鄰接矩陣表示頂點(diǎn)間相聯(lián)關(guān)系的矩陣定義：設(shè)G=(V,E)是有n1個(gè)頂點(diǎn)的圖，G的鄰接矩陣A是具有以下性質(zhì)的n階方陣?yán)鼼12413例15324G2網(wǎng)絡(luò)的鄰接矩陣可定義為：權(quán)的有向圖（有向網(wǎng)）的鄰接矩陣?yán)?452375318642帶權(quán)的無(wú)向圖（無(wú)向網(wǎng)）的鄰接矩陣 分析： 構(gòu)造一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向網(wǎng)的時(shí)間復(fù)雜度為O（n2+e*n），其中O（n2）用于對(duì)鄰接矩陣初始化。（2）鄰接表實(shí)現(xiàn)：為圖

10、中每個(gè)頂點(diǎn)建立一個(gè)單鏈表，第i個(gè)單鏈表中的結(jié)點(diǎn)表示依附于頂點(diǎn)Vi的邊（有向圖中指以Vi為尾的?。﹫D的鄰接表存儲(chǔ)表示：#define MAX_VERTEX_NUM 20 / 最大頂點(diǎn)個(gè)數(shù)typedef struct ArcNode int adjvex; /該弧所指向頂點(diǎn)的位置 struct ArcNode *nextarc; /指示下一條邊或弧的指針 OtherInfo info; / 與該弧相關(guān)的信息 ArcNode;typedef struct VertexNode VertexData data; /頂點(diǎn)信息 ArcNode *firstarc; /指向第一條依附該頂點(diǎn)的弧的指針 Ver

11、texNode;typedef struct VertexNode vertexMAX_VERTEX_NUM; / 鄰接表 int vexnum, arcnum; / 圖的當(dāng)前頂點(diǎn)數(shù)和弧(邊)數(shù) GraphKind kind; / 圖的種類標(biāo)志 AdjList; /鄰接表存儲(chǔ)的圖例G1bdac例aecbdG21234acdbdatafirstarc 3 2 4 1adjvex nextarc1234acdbdatafirstarc 2 5 3 4adjvex nextarc5e 4 3 1 5 2 1 3 2特點(diǎn)無(wú)向圖中頂點(diǎn)Vi的度為第i個(gè)單鏈表中的結(jié)點(diǎn)數(shù)有向圖中頂點(diǎn)Vi的出度為第i個(gè)單鏈表中

12、的結(jié)點(diǎn)個(gè)數(shù)頂點(diǎn)Vi的入度為整個(gè)單鏈表中鄰接點(diǎn)域值是i的結(jié)點(diǎn)個(gè)數(shù)逆鄰接表：有向圖中對(duì)每個(gè)結(jié)點(diǎn)建立以Vi為頭的弧的單鏈表例G1bdac1234acdbvexdatafirstarc 4 1 1 3adjvexnext逆鄰接表鄰接表與鄰接矩陣的比較： 在邊稀疏（e n（n-1）/2）的 情況下，用鄰接表表示圖比鄰接矩陣節(jié)省存儲(chǔ)空間，當(dāng)和邊相關(guān)的信息較多時(shí)更是如此。 在鄰接表上容易找到任何一頂點(diǎn)的第一個(gè)鄰接點(diǎn)和下一個(gè)鄰接點(diǎn)，但要判定任意兩個(gè)頂點(diǎn)（vi和vj）之間是否有邊或弧相連，則需搜索第i個(gè)或第j個(gè)鏈表，因此，不及鄰接矩陣方便。（3）十字鏈表 十字鏈表是有向圖的另一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，可以看成是將有向圖

13、的鄰接表和逆鄰接表結(jié)合起來(lái)得到的一種鏈表。tailtex headtex hlink tlink info 弧結(jié)點(diǎn)的結(jié)構(gòu)其中， tailtex和headtex指明該有向邊始頂點(diǎn)和終頂點(diǎn)的位置。 hlink是指向弧頭相同的下一條弧的指針；tlink是指向弧尾相同的下一條弧的指針。Info指向該弧的相關(guān)信息。 每個(gè)頂點(diǎn)有一個(gè)結(jié)點(diǎn)，它相當(dāng)于出邊表和入邊表的表頭結(jié)點(diǎn)：其中，數(shù)據(jù)成員data存放與該頂點(diǎn)相關(guān)的信息，指針Firstin指示以該頂點(diǎn)為弧頭的第一個(gè)弧結(jié)點(diǎn)，F(xiàn)irstout指示以該頂點(diǎn)為弧尾的第一個(gè)弧結(jié)點(diǎn)。 data Firstin Firstout頂點(diǎn)結(jié)點(diǎn)的結(jié)構(gòu)例bdacab cd1234 1

14、 3 1 2 3 4 3 1 4 3 4 2 4 1abactailtex headtex hlink tlink info data Firstin Firstoutcadacddbdc 有向圖的十字鏈表存儲(chǔ)表示： #define MAX_VERTEX_NUM 20 typedef struct ArcNode int tailvex, headvex; / 該弧的尾和頭頂點(diǎn)的位置 struct ArcNode *hlink, *tlink; / 分別指向下一個(gè)弧頭相同和弧尾相同的弧的指針域 InfoType *info; / 該弧相關(guān)信息的指針 ArcNode; typedef struc

15、t VertexNode VertexData data; ArcNode *firstin, *firstout; / 分別指向該頂點(diǎn)第一條入弧和出弧 VertexNode; typedef struct VertexNode vertexMAX_VERTEX_NUM; / 表頭向量 int vexnum, arcnum; / 有向圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù) GraphKind kind; /圖的種類 OrthList; / 十字鏈表存儲(chǔ)的圖（4）鄰接多重表 鄰接多重表是無(wú)向圖的另一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，由于用鄰接表存儲(chǔ)無(wú)向圖時(shí)，雖然容易求出頂點(diǎn)和邊的各種信息，但在鄰接表中每一條邊有兩個(gè)結(jié)點(diǎn)，分別在第i

16、和第j個(gè)鏈表中，給圖的某些操作帶來(lái)不便。在鄰接多重表中, 每一條邊只有一個(gè)邊結(jié)點(diǎn),為有關(guān)邊的處理提供了方便。其中, mark 是記錄是否處理過(guò)的標(biāo)記; ivex和jvex是該邊兩頂點(diǎn)位置。 ilink指向下一條依附頂點(diǎn)ivex的邊； jlink是指向下一條依附頂點(diǎn)jvex的邊, info存放與該邊相關(guān)的權(quán)值。 mark ivex ilink jvex jlink info邊結(jié)點(diǎn)的結(jié)構(gòu)頂點(diǎn)結(jié)點(diǎn)的結(jié)構(gòu) 存儲(chǔ)頂點(diǎn)信息的結(jié)點(diǎn)表以順序表方式組織, 每一個(gè)頂點(diǎn)結(jié)點(diǎn)有兩個(gè)數(shù)據(jù)成員：其中，data 存放與該頂點(diǎn)相關(guān)的信息，F(xiàn)irstout 是指示第一條依附該頂點(diǎn)的邊的指針。在鄰接多重表中, 所有依附同一個(gè)頂點(diǎn)

17、的邊都鏈接在同一個(gè)單鏈表中。 從頂點(diǎn) i 出發(fā), 可以循環(huán)鏈找到所有依附于該頂點(diǎn)的邊，也可以找到它的所有鄰接頂點(diǎn)。 data Firstout例aecbd1234acdb5e 1 2 1 4 3 4 3 2 3 5 5 2 data Firstout mark ivex ilink jvex jlink info邊結(jié)點(diǎn)的結(jié)構(gòu) #define MAX_VERTEX_NUM 20 typedef struct EdgeNode int mark , ivex, jvex; / 訪問(wèn)標(biāo)記和該邊依附的兩個(gè)頂點(diǎn)的位置 struct EdgeNode *ilink, *jlink; / 分別指向依附這兩個(gè)

18、頂點(diǎn)的下一條邊 InfoType *info; / 該邊信息指針 EdgeNode; typedef struct VertexData data; EdgeNode *firstedge; / 指向第一條依附該頂點(diǎn)的邊 VertexNode; typedef struct VertexNode VertexMAX_VERTEX_NUM; int vexnum, edgenum; / 無(wú)向圖的當(dāng)前頂點(diǎn)數(shù)和邊數(shù) GraphKind kind; AdjMultiList; /鄰接多重表存儲(chǔ)的圖7.3 圖的遍歷圖的遍歷：從圖中某個(gè)頂點(diǎn)出發(fā)訪遍圖中其余頂點(diǎn)，并且使圖中的每個(gè)頂點(diǎn)僅被訪問(wèn)一次過(guò)程. 遍歷

19、圖的過(guò)程實(shí)質(zhì)上是通過(guò)邊或弧對(duì)每個(gè)頂點(diǎn)查找其鄰接點(diǎn)的過(guò)程，其耗費(fèi)的時(shí)間取決于所采用的存儲(chǔ)結(jié)構(gòu)。 圖的遍歷有兩條路徑：深度優(yōu)先搜索和廣度優(yōu)先搜索 當(dāng)用鄰接矩陣作圖的存儲(chǔ)結(jié)構(gòu)時(shí)，查找每個(gè)頂點(diǎn)的鄰接點(diǎn)所需要時(shí)間為O（n2），n為圖中頂點(diǎn)數(shù)；而當(dāng)以鄰接表作圖的存儲(chǔ)結(jié)構(gòu)時(shí)，找鄰接點(diǎn)所需時(shí)間為 O（e），e為無(wú)向圖中邊的數(shù)或有向圖中弧的數(shù)。1. 深度優(yōu)先遍歷(DFS：Depth-First Search)方法：從圖的某一頂點(diǎn)V0出發(fā)，訪問(wèn)此頂點(diǎn)；然后依次從V0的未被訪問(wèn)的鄰接點(diǎn)出發(fā)，深度優(yōu)先遍歷圖，直至圖中所有和V0相通的頂點(diǎn)都被訪問(wèn)到；若此時(shí)圖中尚有頂點(diǎn)未被訪問(wèn)，則另選圖中一個(gè)未被訪問(wèn)的頂點(diǎn)作起點(diǎn)，重復(fù)上

20、述過(guò)程，直至圖中所有頂點(diǎn)都被訪問(wèn)為止。V1V2V4V5V3V7V6V8例深度遍歷：V1 V2 V4 V8 V5 V3 V6 V7V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8深度遍歷：V1 V2 V4 V8 V5 V6 V3 V7深度遍歷：V1 V2 V4 V8 V5 V6 V3 V7V1V2V4V5V3V7V6V8例深度遍歷：V1 V2 V4 V8 V3 V6 V7 V5深度優(yōu)先遍歷算法遞歸算法開(kāi)始訪問(wèn)V0,置標(biāo)志求V0鄰接點(diǎn)有鄰接點(diǎn)w求下一鄰接點(diǎn)wV0W訪問(wèn)過(guò)結(jié)束NYNYDFS開(kāi)始標(biāo)志數(shù)組初始化Vi=0Vi訪問(wèn)過(guò)DFSVi=Vi+1Vi=Vexnums結(jié)束NNYYBo

21、olean visitedMAX; /訪問(wèn)標(biāo)志數(shù)組Status(*VisitFunc)(int v); /函數(shù)變量void DFSTraverse(Graph G,Status(*Visit)(int v)/對(duì)圖G作深度優(yōu)先遍歷 VisitFunc = Visit; /使用全局變量VisitFunc，使DFS不必設(shè)函數(shù)指針參數(shù) for(v = 0;vG.vexnum;+v) visitedv = FALSE; /訪問(wèn)標(biāo)志數(shù)組初始化 for(v = 0;v=0; w=NextAdjVex(G,v,w) if(!visitedw) DFS(G,w); /對(duì)v的尚未訪問(wèn)的鄰接頂點(diǎn)w遞歸調(diào)用DFS /

22、 類似算法 7.4V1V2V4V5V3V7V6V8例深度遍歷：V11234v1v3v4v2vexdatafirstarc 2 7 8 3adjvexnext5v5 6 4 1 5 1 2 8 2v6v7v8678 7 3 6 3 5 4V3 V7 V6 V2 V5 V8 V4V1V2V4V5V3V7V6V8例12341342vexdatafirstarc 2 7 8 3adjvexnext55 6 4 8 2678678 7深度遍歷：V1V3 V7 V6 V2 V4 V8 V5當(dāng)以鄰接表作存儲(chǔ)結(jié)構(gòu)時(shí)，深度優(yōu)先搜索遍歷圖的時(shí)間復(fù)雜度為O（n+e）2. 廣度優(yōu)先遍歷(BFS)方法：從圖的某一頂點(diǎn)V

23、0出發(fā)，訪問(wèn)此頂點(diǎn)后，依次訪問(wèn)V0的各個(gè)未曾訪問(wèn)過(guò)的鄰接點(diǎn)；然后分別從這些鄰接點(diǎn)出發(fā)，廣度優(yōu)先遍歷圖，直至圖中所有已被訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)都被訪問(wèn)到；若此時(shí)圖中尚有頂點(diǎn)未被訪問(wèn)，則另選圖中一個(gè)未被訪問(wèn)的頂點(diǎn)作起點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪問(wèn)為止。V1V2V4V5V3V7V6V8例廣度遍歷：V1 V2 V3 V4 V5 V6 V7 V8V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8廣度遍歷：V1 V2 V3 V4 V5 V6 V7 V8廣度遍歷：V1 V2 V3 V4 V5 V6 V7 V8V1V2V4V5V3V7V6V8例廣度遍歷：V1 V2 V3 V4 V6

24、V7 V8 V5廣度優(yōu)先遍歷算法開(kāi)始標(biāo)志數(shù)組初始化Vi=0Vi訪問(wèn)過(guò)BFSVi=Vi+1Vi=Vexnums結(jié)束NNYY開(kāi)始訪問(wèn)V0,置標(biāo)志求V鄰接點(diǎn)ww存在嗎V下一鄰接點(diǎn)ww訪問(wèn)過(guò)結(jié)束NYNYBFS初始化隊(duì)列V0入隊(duì)隊(duì)列空嗎隊(duì)頭V出隊(duì)訪問(wèn)w,置標(biāo)志w入隊(duì)NYvoid BFSTraverse(Graph G,Status(*Visit)(int v)/按廣度優(yōu)先非遞歸遍歷圖G。使用輔助隊(duì)列Q和訪問(wèn)標(biāo)志數(shù)組visited。 for(v = 0;vG.vexnum;+v) visitedv = FALSE; InitQueue(Q); /置空的輔助隊(duì)列Q for(v = 0; v=0; w=Nex

25、tAdjVex(G,u,w) if(!Visitedw) /w為u的尚未訪問(wèn)的鄰接頂點(diǎn) Visitedw = TRUE; Visit(w); EnQueue(Q,W); /if /while /if /BFSTraverse 類似算法 7.8例1423512341342vexdatafirstarc 5 5 4 3adjvexnext55 1 5 1 1 4 3 2 20 1 2 3 4 51fr遍歷序列：10 1 2 3 4 54fr遍歷序列：1 40 1 2 3 4 54 3fr遍歷序列：1 4 3例1423512341342vexdatafirstarc 5 5 4 3adjvexnex

26、t55 1 5 1 1 4 3 2 20 1 2 3 4 54 3 2fr遍歷序列：1 4 3 20 1 2 3 4 5 3 2fr遍歷序列：1 4 3 20 1 2 3 4 5 3 2 5fr遍歷序列：1 4 3 2 50 1 2 3 4 5 2 5fr遍歷序列：1 4 3 2 50 1 2 3 4 5 5fr遍歷序列：1 4 3 2 50 1 2 3 4 5 fr遍歷序列：1 4 3 2 5例1423512341342vexdatafirstarc 5 5 4 3adjvexnext55 1 5 1 1 4 3 2 27.4 圖的應(yīng)用7.4.1 圖的連通性問(wèn)題1. 無(wú)向圖的連通分量和生成樹(shù)

27、連通分量非連通圖的每一個(gè)連通部分（連通的子圖）連通圖例1245136例2非連通圖562413連通的無(wú)向圖從任一頂點(diǎn)出發(fā)可以深度和廣度優(yōu)先遍歷所有的頂點(diǎn)，非連通的則無(wú)法實(shí)現(xiàn)這一點(diǎn)。連通分量2連通分量1生成樹(shù) 所有頂點(diǎn)均由邊連接在一起，但不存在回路的圖生成樹(shù)的種類 深度優(yōu)先生成樹(shù)與廣度優(yōu)先生成樹(shù)生成森林 非連通圖每個(gè)連通分量的生成樹(shù)一起組成非連通圖的生成森林ACDEIBFGHJONMLK非連通無(wú)向圖AHKCDEIBFOGJNML非連通圖的生成森林說(shuō)明（1）一個(gè)圖可以有許多棵不同的生成樹(shù)（2）所有生成樹(shù)具有以下共同特點(diǎn)：生成樹(shù)的頂點(diǎn)個(gè)數(shù)與圖的頂點(diǎn)個(gè)數(shù)相同生成樹(shù)是圖的極小連通子圖一個(gè)有n個(gè)頂點(diǎn)的連通圖

28、的生成樹(shù)有n-1條邊生成樹(shù)中任意兩個(gè)頂點(diǎn)間的路徑是唯一的在生成樹(shù)中再加一條邊必然形成回路（3）含n個(gè)頂點(diǎn)n-1條邊的圖不一定是生成樹(shù)GHKIONMLKONMLKONMLKV1V2V4V5V3V7V6V8例深度遍歷：V1 V2 V4 V8 V5 V3 V6 V7V1V2V4V5V3V7V6V8深度優(yōu)先生成樹(shù)V1V2V4V5V3V7V6V8廣度優(yōu)先生成樹(shù)V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8廣度遍歷：V1 V2 V3 V4 V5 V6 V7 V8例ABLMCFDEGHKIJABLMFCJDEGHKI深度優(yōu)先生成森林生成非連通圖的深度優(yōu)先生成森林的算法void DFSFor

29、est(Graph G,CSTree &T) /建立無(wú)向圖G的深度優(yōu)先生成森林的（最左）孩子（右）兄弟鏈表T T = NULL; for(v = 0;vG.vexnum;+v) visitedv = FALSE; for(v = 0;vnextsibling = p; /是其它生成樹(shù)的根 q = p; /q指示當(dāng)前生成樹(shù)的根 DFSTree(G,v,p); /建立以p為根的生成樹(shù) /DFSForestvoid DFSTree(Graph G,int v,CSTree &T) /從第v個(gè)頂點(diǎn)出發(fā)濃深度優(yōu)先遍歷圖G，建立以T為根的生成樹(shù)。 visitedv = TRUE; first = TRUE

30、; for(w = FistAdjVex(G,v); w=0; w = NextAdjVex(G,v,w) if(!visitedw) p = (CSTree)malloc(sizeof(CSNode); /分配孩子結(jié)點(diǎn) *p = GetVex(G,w),NULL,NULL; if(first) /w是v的第一個(gè)未被訪問(wèn)的鄰接頂點(diǎn) T-lchild = p; first = FALSE; /是根的左孩子結(jié)點(diǎn) /if else /w是v的其它未被訪問(wèn)的鄰接頂點(diǎn) q-nextsibling = p; /是上一鄰接頂點(diǎn)的右兄弟結(jié)點(diǎn) /else q = p; DFSTree(G,w,q); /從第w個(gè)

31、頂點(diǎn)出發(fā)深度優(yōu)先遍歷圖G，建立子生成樹(shù)q /if/DFSTree2. 最小生成樹(shù) 問(wèn)題提出 要在n個(gè)城市間建立通信聯(lián)絡(luò)網(wǎng)，頂點(diǎn)表示城市權(quán)城市間建立通信線路所需花費(fèi)代價(jià)希望找到一棵生成樹(shù)，它的每條邊上的權(quán)值之和（即建立該通信網(wǎng)所需花費(fèi)的總代價(jià)）最小最小代價(jià)生成樹(shù) 問(wèn)題分析1654327131791812752410n個(gè)城市間，最多可設(shè)置n(n-1)/2條線路n個(gè)城市間建立通信網(wǎng)，只需n-1條線路問(wèn)題轉(zhuǎn)化為：如何在可能的線路中選擇n-1條，能把 所有城市（頂點(diǎn)）均連起來(lái)，且總耗費(fèi) （各邊權(quán)值之和）最小 構(gòu)造最小生成樹(shù)方法方法一：普里姆(Prim)算法 從某頂點(diǎn)開(kāi)始，找其相鄰邊中權(quán)值最小的邊所連另一

32、個(gè)頂點(diǎn)，再找與這兩個(gè)頂點(diǎn)相鄰邊中權(quán)值最小的邊所連第三個(gè)頂點(diǎn)，重復(fù)，擴(kuò)展到所有頂點(diǎn)。方法二：克魯斯卡爾算法 先將所有頂點(diǎn)都看作無(wú)邊的非連通圖，選擇各頂點(diǎn)間最小邊做連通分量，直到所有定點(diǎn)都在同一個(gè)連通分量上。例1654326513566425131163141643142116432142516543214253普里姆(Prim)算法算法思想：設(shè)N=(V,E)是連通網(wǎng)，TE是N上最小生成樹(shù)中邊的集合初始令U=u0,(u0V), TE=在所有uU,vV-U的邊(u,v)E中，找一條代價(jià)最小的邊(u0,v0)將(u0,v0)并入集合TE，同時(shí)v0并入U(xiǎn)重復(fù)上述操作直至U=V為止，則T=(V,TE)為N

33、的最小生成樹(shù)算法實(shí)現(xiàn)：圖用鄰接矩陣表示算法描述：算法評(píng)價(jià)：T(n)=O(n)void MiniSpanTree_PRIM(MGraph G,VertexType u) /用普里姆算法從第u個(gè)頂點(diǎn)出發(fā)構(gòu)造網(wǎng)G的最小生成樹(shù)T，輸出T的各條邊。 /記錄從頂點(diǎn)集U到V-U的代價(jià)最小的邊的輔助數(shù)組定義： /struct / VertxtType adjvex; / VRType lowcost; / closedgeMAX_VERTEX_NUM; k = LocateVex(G,u); for(j = 0;jG.vexnum;+j) /輔助數(shù)組初始化 if(j! = K) closedgej = u,

34、G,arcskj.adj; /adjvex, lowcost closedgek.lowcost = 0; /初始，U = u for(i=1;i0,viV-U printf(closedgek.adjvex , G.vexsk); /輸出生成樹(shù)的邊 closedgek.lowcost = 0; /第k頂點(diǎn)并入U(xiǎn)集 for(j = 0;jG.vexnum;+j) if(G.arcskj.adjclosedgej.lowcost) /新頂點(diǎn)并入U(xiǎn)后重新選擇最小邊 closedgej = G.vexsk, G.arcskj.adj; /MiniSpanTree10 1 2 3 4 50 1 2 3

35、 4 51-21-41-1例16543265135664251-51-3165432651356642516543214253克魯斯卡爾(Kruskal)算法算法思想：設(shè)連通網(wǎng)N=(V,E)，令最小生成樹(shù)初始狀態(tài)為只有n個(gè)頂點(diǎn)而無(wú)邊的非連通圖T=(V,)，每個(gè)頂點(diǎn)自成一個(gè)連通分量在E中選取代價(jià)最小的邊，若該邊依附的頂點(diǎn)落在T中不同的連通分量上，則將此邊加入到T中；否則，舍去此邊，選取下一條代價(jià)最小的邊依此類推，直至T中所有頂點(diǎn)都在同一連通分量上為止例165432651356642516543212345（0）用頂點(diǎn)數(shù)組和邊數(shù)組存放頂點(diǎn)和邊信息（1）初始時(shí)，令每個(gè)頂點(diǎn)的jihe互不相同；每個(gè)邊的

36、flag為0（2）選出權(quán)值最小且flag為0的邊（3）若該邊依附的兩個(gè)頂點(diǎn)的jihe 值不同，即非連通，則令 該邊的flag=1, 選中該邊；再令該邊依附的兩頂點(diǎn)的jihe 以及兩集合中所有頂點(diǎn)的jihe 相同 若該邊依附的兩個(gè)頂點(diǎn)的jihe 值相同，即連通，則令該 邊的flag=2, 即舍去該邊（4）重復(fù)上述步驟，直到選出n-1條邊為止 頂點(diǎn)結(jié)點(diǎn)：typedef struct int data; /頂點(diǎn)信息 int jihe; VEX;邊結(jié)點(diǎn)：typedef struct int vexh, vext; /邊依附的兩頂點(diǎn) int weight; /邊的權(quán)值 int flag; /標(biāo)志域EDG

37、E;算法描述：例1654326513566425datajihe124536124536124536vexhweight112213233544vextflag61535500000001342567893345566664260000111114211122222165432123457.4.2 有向無(wú)環(huán)圖的應(yīng)用1. 基本概念 有向無(wú)環(huán)圖（Directed Acyclic Graph） 一個(gè)無(wú)環(huán)的有向圖，簡(jiǎn)稱DAG圖。 作用：是描述一項(xiàng)工程進(jìn)行過(guò)程的有效工具。主要進(jìn)行拓?fù)渑判蚝完P(guān)鍵路徑的操作。V1V2V4V5V8DAGV3V7V6DG2. 拓?fù)渑判騿?wèn)題提出： 學(xué)生應(yīng)按怎樣的順序?qū)W習(xí)這些課程，

38、才能無(wú)矛盾、順利地完成學(xué)業(yè)？ 課程代號(hào) 課程名稱 先修課C1C2C3C4C5C6C7C8C9C10C11C12無(wú)C1C1,C2C1C3,C4C11C3.C5C3,C6無(wú)C9C9C1,C9,C10程序設(shè)計(jì)基礎(chǔ)離散數(shù)學(xué)數(shù)據(jù)結(jié)構(gòu)匯編語(yǔ)言程序設(shè)計(jì)方法學(xué)計(jì)算機(jī)原理編譯原理操作系統(tǒng)高等數(shù)學(xué)線性代數(shù)普通物理數(shù)值分析拓?fù)渑判颍河赡硞€(gè)集合上的一個(gè)偏序得到該集合上的一個(gè)全序的操作。拓?fù)渑判驅(qū)嶋H上是對(duì)鄰接表表示的圖進(jìn)行深度優(yōu)先遍歷的過(guò)程. 答案：采用拓?fù)渑判蚶n程代號(hào) 課程名稱 先修棵C1C2C3C4C5C6C7C8C9C10C11C12無(wú)C1C1,C2C1C3,C4C11C3.C5C3,C6無(wú)C9C9C1,C9,

39、C10程序設(shè)計(jì)基礎(chǔ)離散數(shù)學(xué)數(shù)據(jù)結(jié)構(gòu)匯編語(yǔ)言程序設(shè)計(jì)方法學(xué)計(jì)算機(jī)原理編譯原理操作系統(tǒng)高等數(shù)學(xué)線性代數(shù)普通物理數(shù)值分析C1C2C3C4C5C6C7C8C9C10C11C12例：建立表示課程之間優(yōu)先關(guān)系的有向圖頂點(diǎn)表示課程有向弧表示先決條件，若課程i是課程j的先決條件，則圖中有弧AOV網(wǎng)AOV網(wǎng)用頂點(diǎn)表示活動(dòng)，用弧表示活動(dòng)間優(yōu)先關(guān)系的有向圖稱為頂點(diǎn)表示活動(dòng)的網(wǎng)(Activity On Vertex network)，簡(jiǎn)稱AOV網(wǎng)若是圖中有向邊，則vi是vj的直接前驅(qū)；vj是vi的直接后繼AOV網(wǎng)中不允許有回路，這意味著某項(xiàng)活動(dòng)以自己為先決條件拓?fù)渑判虬袮OV網(wǎng)絡(luò)中各頂點(diǎn)按照它們相互之間的優(yōu)先關(guān)系排列

40、成一個(gè)線性序列的過(guò)程（深度優(yōu)先遍歷）檢測(cè)AOV網(wǎng)中是否存在環(huán)的方法：對(duì)有向圖構(gòu)造其頂點(diǎn)的拓?fù)溆行蛐蛄?，若網(wǎng)中所有頂點(diǎn)都在它的拓?fù)溆行蛐蛄兄?，則該AOV網(wǎng)必定不存在環(huán)拓?fù)渑判虻姆椒ㄔ谟邢驁D中選一個(gè)沒(méi)有前驅(qū)的頂點(diǎn)且輸出之從圖中刪除該頂點(diǎn)和所有以它為尾的弧重復(fù)上述兩步，直至全部頂點(diǎn)均已輸出；或者當(dāng)圖中不存在無(wú)前驅(qū)的頂點(diǎn)為止動(dòng)畫(huà)演示C1C2C3C4C5C6C7C8C9C10C11C12拓?fù)湫蛄校篊1-C2-C3-C4-C5-C7-C9-C10-C11-C6-C12-C8或 ：C9-C10-C11-C6-C1-C12-C4-C2-C3-C5-C7-C8一個(gè)AOV網(wǎng)的拓?fù)湫蛄胁皇俏ㄒ坏乃惴▽?shí)現(xiàn)以鄰接表作存

41、儲(chǔ)結(jié)構(gòu)把鄰接表中所有入度為0的頂點(diǎn)進(jìn)棧棧非空時(shí)，輸出棧頂元素Vj并退棧；在鄰接表中查找Vj的直接后繼Vk，把Vk的入度減1；若Vk的入度為0則進(jìn)棧重復(fù)上述操作直至?？諡橹?。若?？諘r(shí)輸出的頂點(diǎn)個(gè)數(shù)不是n，則有向圖有環(huán)；否則，拓?fù)渑判蛲戤咁愃扑惴?7.11Status TopologicalSort(ALGraph G) /有向圖G采用鄰接表存儲(chǔ)結(jié)構(gòu)。 /若G無(wú)回路，則輸出G的頂點(diǎn)的一個(gè)拓?fù)湫蛄胁⒎祷豋K，否則ERROR。 FindInDegree(G,indegree); /對(duì)各頂點(diǎn)求入度indegree0.vernum-1 InitStack(S); for(i = 0;inextarc) k

42、 = p-adjvex; /對(duì)i號(hào)頂點(diǎn)的每個(gè)鄰接點(diǎn)的入度減1 if(!(- - indegreek) Push(S,k); /若入度減為0，則入棧 /for /while if(countG.vexnum) return ERROR; /該有向圖有回路 else return OK;/TopologicalSort 算法分析建鄰接表：T(n)=O(e)搜索入度為0的頂點(diǎn)的時(shí)間：T(n)=O(n)拓?fù)渑判颍篢(n)=O(n+e)3. 關(guān)鍵路徑問(wèn)題提出把工程計(jì)劃表示為有向圖，用頂點(diǎn)表示事件，弧表示活動(dòng)；每個(gè)事件表示在它之前的活動(dòng)已完成，在它之后的活動(dòng)可以開(kāi)始.例 設(shè)一個(gè)工程有11項(xiàng)活動(dòng)，9個(gè)事件

43、事件 V1表示整個(gè)工程開(kāi)始 事件V9表示整個(gè)工程結(jié)束問(wèn)題：（1）完成整項(xiàng)工程至少需要多少時(shí)間？ （2）哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵？987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4AOE網(wǎng)AOE網(wǎng)(Activity On Edge)也叫邊表示活動(dòng)的網(wǎng)。AOE網(wǎng)是一個(gè)帶權(quán)的有向無(wú)環(huán)圖，其中頂點(diǎn)表示事件，弧表示活動(dòng)，權(quán)表示活動(dòng)持續(xù)時(shí)間路徑長(zhǎng)度路徑上各活動(dòng)持續(xù)時(shí)間之和關(guān)鍵路徑路徑長(zhǎng)度最長(zhǎng)的路徑Ve(j)表示事件Vj的最早發(fā)生時(shí)間Vl(j)表示事件Vj的最遲發(fā)生時(shí)間e(i)表示活動(dòng)ai的最早開(kāi)始時(shí)間l(i)表示活動(dòng)ai的最遲開(kāi)始時(shí)間l(i)

44、-e(i)表示完成活動(dòng)ai的時(shí)間余量關(guān)鍵活動(dòng)關(guān)鍵路徑上的活動(dòng)，即l(i)=e(i)的活動(dòng)987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4問(wèn)題分析如何找e(i)=l(i)的關(guān)鍵活動(dòng)？ 設(shè)活動(dòng)ai用弧表示，其持續(xù)時(shí)間記為：dut()則有：（1）e(i)=Ve(j) （2）l(i)=Vl(k)-dut()jkai如何求Ve(j)和Vl(j)？(1)從Ve(1)=0開(kāi)始向前遞推(2)從Vl(n)=Ve(n)開(kāi)始向后遞推987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4求關(guān)鍵路徑步驟

45、求Ve(i)求Vl(j)求e(i)求l(i)計(jì)算l(i)-e(i)987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4V1V2V3V4V5V6V7V8V9頂點(diǎn) Ve Vl0645771614180668710161418a1a2a3a4a5a6a7a8a9a10a11活動(dòng) e l l-e00002266046258377077071031616014140033e(i)=Ve(j) l(i)=Vl(k)-dut() 算法實(shí)現(xiàn)輸入頂點(diǎn)和弧信息，建立其鄰接表 計(jì)算每個(gè)頂點(diǎn)的入度 對(duì)其進(jìn)行拓?fù)渑判?排序過(guò)程中求頂點(diǎn)的Vei 將得到的拓?fù)湫蛄羞M(jìn)

46、棧 按逆拓?fù)湫蛄星箜旤c(diǎn)的Vli 計(jì)算每條弧的ei和li,找出ei=li的關(guān)鍵活動(dòng)Status TopologicalOrder ( ALGraph G, SqStack &T ) / 有向圖 G 采用鄰接表存儲(chǔ)結(jié)構(gòu)，求各頂點(diǎn)事件的最早發(fā)生時(shí)間 ve（全局變量）。/ T 為拓?fù)湫蛄许旤c(diǎn)棧，S 為零入度頂點(diǎn)棧。/ 如果 G 無(wú)回路，則用棧 T 返回 G 的一個(gè)拓?fù)湫蛄校液瘮?shù)值為 OK，否則為 ERROR。FindInDegree ( G, indegree ); / 對(duì)各頂點(diǎn)求入度 indegree 0.vernum-1InitStack (S); / 初始化零入度頂點(diǎn)棧 Sfor ( i =

47、0; i nextarc ) k = p-adjvex; / 對(duì) j 號(hào)頂點(diǎn)的每個(gè)鄰接點(diǎn)入度減 1if ( ! ( -indegree k ) ) Push ( S, k ); / 若入度減為 0 ，則入棧if ( vej + *( p-info) vek ) / 求各頂點(diǎn)的最早發(fā)生時(shí)間 vek = vej + *( p-info)； / for 結(jié)束 / while 結(jié)束if ( count nextarc ) k = p-adjvex; dut = *( p-info ); / dut 是事件 vj 到事件 vk 活動(dòng)持續(xù)時(shí)間，即 dutif ( vlk dut vlj ) vlj = v

48、lk dut; / for 結(jié)束for ( j = 0; j nextarc ) k = p-adjvex; dut = *( p-info );ee = vej; el = vlk dut;tag = ( ee = = el ) ? * : ;printf ( j, k, dut, ee, el, tag ); / 輸出關(guān)鍵活動(dòng) / for ( p = G.verticesj.firstarc ) 結(jié)束 / CriticalPath7.4.3 最短路徑問(wèn)題提出用帶權(quán)的有向圖表示一個(gè)交通運(yùn)輸網(wǎng)，圖中：頂點(diǎn)表示城市邊表示城市間的交通聯(lián)系權(quán)表示此線路的長(zhǎng)度或沿此線路運(yùn)輸所花的時(shí)間或費(fèi)用等問(wèn)題：從某

49、頂點(diǎn)出發(fā)，沿圖的邊到達(dá)另一頂點(diǎn)所經(jīng)過(guò)的路徑中，各邊上權(quán)值之和最小的一條路徑最短路徑例：下圖中從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑51643208562301371732913長(zhǎng)度最短路徑8131921202. 迪杰斯特拉(Dijkstra)算法思想按路徑長(zhǎng)度遞增次序產(chǎn)生最短路徑算法：把V分成兩組：（1）S：已求出最短路徑的頂點(diǎn)的集合（2）V-S=T：尚未確定最短路徑的頂點(diǎn)集合將T中頂點(diǎn)按最短路徑遞增的次序加入到S中，保證：（1）從源點(diǎn)V0到S中各頂點(diǎn)的最短路徑長(zhǎng)度都不大于 從V0到T中任何頂點(diǎn)的最短路徑長(zhǎng)度 （2）每個(gè)頂點(diǎn)對(duì)應(yīng)一個(gè)距離值 S中頂點(diǎn)：從V0到此頂點(diǎn)的最短路徑長(zhǎng)度 T中頂點(diǎn)：從V0到此

50、頂點(diǎn)的只包括S中頂 點(diǎn)作中間頂點(diǎn)的最短路徑長(zhǎng)度 51643208562301371732913長(zhǎng)度最短路徑8131921203. 求最短路徑步驟初使時(shí)令 S=V0,T=其余頂點(diǎn)，T中頂點(diǎn)對(duì)應(yīng)的距離值：若存在，為弧上的權(quán)值若不存在，為從T中選取一個(gè)其距離值為最小的頂點(diǎn)W，加入S對(duì)T中頂點(diǎn)的距離值進(jìn)行修改：若加進(jìn)W作中間頂點(diǎn)，從V0到Vi的距離值比不加W的路徑要短，則修改此距離值重復(fù)上述步驟，直到S中包含所有頂點(diǎn)，即S=V為止516432085623013717329: 13: 8: : 30: : 32從中選 V2 : 81383032V2:813-133032V1:13-13302220V3:

51、13-192220V4:19終點(diǎn) 從V0到各終點(diǎn)的最短路徑及其長(zhǎng)度V1V2V3V4V5V6Vj-2120V6:205164320856230137173294. 算法實(shí)現(xiàn)圖用帶權(quán)鄰接矩陣存儲(chǔ)ad數(shù)組dist存放當(dāng)前找到的從源點(diǎn)V0到每個(gè)終點(diǎn)的最短路徑長(zhǎng)度，其初態(tài)為圖中直接路徑權(quán)值數(shù)組pre表示從V0到各終點(diǎn)的最短路徑上，此頂點(diǎn)的前一頂點(diǎn)的序號(hào)；若從V0到某終點(diǎn)無(wú)路徑，則用0作為其前一頂點(diǎn)的序號(hào)516432085623013717329dist0 1 2 3 4 5 60 13 8 30 32pre0 1 2 3 4 5 60 1 1 0 1 0 1(1)k=111321222011193121

52、4111長(zhǎng)度最短路法分析：T(n)=O(n)算法描述 類似算法 7.15void ShortestPath_DIJ( MGraph G, int v0, PathMatrix &p, ShortPathTable &D) / 用Dijkstra 算法求有向網(wǎng)G的v0頂點(diǎn)到其余頂點(diǎn)v的最短路/pv及其帶權(quán)長(zhǎng)度Dv。若pvw為T(mén)RUE，則w是從v0到v / 當(dāng)前求得最短路徑上的頂點(diǎn)。 finalv為T(mén)RUE當(dāng)且僅當(dāng)vS, / 即已經(jīng)求得v0到v的最短路徑。 for (v=0;vG.vexnum;+v) finalv=FALSE; Dv=G.arcsv0v; for (w=0;wG.vexnum;+w) Pvw=FALSE; / 設(shè)空路徑 if (DvINFINITY) Pvv0=TRUE; Pvv=TRUE; /for Dv0=0; finalv0=TRUE; /初始化，v0頂點(diǎn)屬于S集 /開(kāi)始主循環(huán)，每次求得v0到某個(gè)v頂點(diǎn)的最短路徑，并加v到S集 for (i=1;iG.vexnum;+i) / 其余G.vexnum-1個(gè)頂點(diǎn) min=INFINITY; / 當(dāng)前所知離v0頂點(diǎn)的最近距離 for (w=0;wG.vexnum;+w) if(!finalw) if(Dwmin) v=w; min=D