六、樹和二叉樹的回顧課件

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

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

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

4、和E(G)組成的，其中：V(G)是頂點的非空有限集，E(G)是有向邊（也稱弧）的有限集合，弧是頂點的有序?qū)?，記為，v,w是頂點，v為弧尾，w為弧頭例245136G1圖G1中：V(G1)=1,2,3,4,5,6 E(G1)=, , , , , , 無向圖(Undigraph)無向圖G是由兩個集合V(G)和E(G)組成的其中：V(G)是頂點的非空有限集，E(G)是邊的有限集合，邊是頂點的無序?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個頂點的有向圖最大邊數(shù)是n(n-1)無向完備圖n個頂點的無向圖最大邊數(shù)是n(n-1)/2例213213有向完備圖無向完備圖稀疏圖有很少條邊或弧的圖（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ù),可以表示兩個頂點之間的距離或耗費網(wǎng)帶權(quán)的圖上海北京 怎么走最優(yōu)?例北京上海南京濟南徐州280500320180160600260200

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

7、為頂點集。數(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 對頂點的訪問操作: LocateVex(G, u); / 若G中存在頂點u，則返回該頂點在圖中位置；否則返回其它信息。 GetVex(G, v); / 返回v的值 PutVex(&G, v, value); / 對v賦值value 對鄰接點的操作: FirstAdjVex(G, v); / 返回v的第一個鄰接點。若該頂點在G

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

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

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

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

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

13、的鄰接表和逆鄰接表結(jié)合起來得到的一種鏈表。tailtex headtex hlink tlink info 弧結(jié)點的結(jié)構(gòu)其中， tailtex和headtex指明該有向邊始頂點和終頂點的位置。 hlink是指向弧頭相同的下一條弧的指針；tlink是指向弧尾相同的下一條弧的指針。Info指向該弧的相關(guān)信息。 每個頂點有一個結(jié)點，它相當于出邊表和入邊表的表頭結(jié)點：其中，數(shù)據(jù)成員data存放與該頂點相關(guān)的信息，指針Firstin指示以該頂點為弧頭的第一個弧結(jié)點，F(xiàn)irstout指示以該頂點為弧尾的第一個弧結(jié)點。 data Firstin Firstout頂點結(jié)點的結(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 有向圖的十字鏈表存儲表示： #define MAX_VERTEX_NUM 20 typedef struct ArcNode int tailvex, headvex; / 該弧的尾和頭頂點的位置 struct ArcNode *hlink, *tlink; / 分別指向下一個弧頭相同和弧尾相同的弧的指針域 InfoType *info; / 該弧相關(guān)信息的指針 ArcNode; typedef struc

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

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

17、的邊都鏈接在同一個單鏈表中。 從頂點 i 出發(fā), 可以循環(huá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é)點的結(jié)構(gòu) #define MAX_VERTEX_NUM 20 typedef struct EdgeNode int mark , ivex, jvex; / 訪問標記和該邊依附的兩個頂點的位置 struct EdgeNode *ilink, *jlink; / 分別指向依附這兩個

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

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

20、述過程，直至圖中所有頂點都被訪問為止。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)先遍歷算法遞歸算法開始訪問V0,置標志求V0鄰接點有鄰接點w求下一鄰接點wV0W訪問過結(jié)束NYNYDFS開始標志數(shù)組初始化Vi=0Vi訪問過DFSVi=Vi+1Vi=Vexnums結(jié)束NNYYBo

21、olean visitedMAX; /訪問標志數(shù)組Status(*VisitFunc)(int v); /函數(shù)變量void DFSTraverse(Graph G,Status(*Visit)(int v)/對圖G作深度優(yōu)先遍歷 VisitFunc = Visit; /使用全局變量VisitFunc，使DFS不必設(shè)函數(shù)指針參數(shù) for(v = 0;vG.vexnum;+v) visitedv = FALSE; /訪問標志數(shù)組初始化 for(v = 0;v=0; w=NextAdjVex(G,v,w) if(!visitedw) DFS(G,w); /對v的尚未訪問的鄰接頂點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當以鄰接表作存儲結(jié)構(gòu)時，深度優(yōu)先搜索遍歷圖的時間復(fù)雜度為O（n+e）2. 廣度優(yōu)先遍歷(BFS)方法：從圖的某一頂點V

23、0出發(fā)，訪問此頂點后，依次訪問V0的各個未曾訪問過的鄰接點；然后分別從這些鄰接點出發(fā)，廣度優(yōu)先遍歷圖，直至圖中所有已被訪問的頂點的鄰接點都被訪問到；若此時圖中尚有頂點未被訪問，則另選圖中一個未被訪問的頂點作起點，重復(fù)上述過程，直至圖中所有頂點都被訪問為止。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)先遍歷算法開始標志數(shù)組初始化Vi=0Vi訪問過BFSVi=Vi+1Vi=Vexnums結(jié)束NNYY開始訪問V0,置標志求V鄰接點ww存在嗎V下一鄰接點ww訪問過結(jié)束NYNYBFS初始化隊列V0入隊隊列空嗎隊頭V出隊訪問w,置標志w入隊NYvoid BFSTraverse(Graph G,Status(*Visit)(int v)/按廣度優(yōu)先非遞歸遍歷圖G。使用輔助隊列Q和訪問標志數(shù)組visited。 for(v = 0;vG.vexnum;+v) visitedv = FALSE; InitQueue(Q); /置空的輔助隊列Q for(v = 0; v=0; w=Nex

25、tAdjVex(G,u,w) if(!Visitedw) /w為u的尚未訪問的鄰接頂點 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 圖的連通性問題1. 無向圖的連通分量和生成樹

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

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

29、est(Graph G,CSTree &T) /建立無向圖G的深度優(yōu)先生成森林的（最左）孩子（右）兄弟鏈表T T = NULL; for(v = 0;vG.vexnum;+v) visitedv = FALSE; for(v = 0;vnextsibling = p; /是其它生成樹的根 q = p; /q指示當前生成樹的根 DFSTree(G,v,p); /建立以p為根的生成樹 /DFSForestvoid DFSTree(Graph G,int v,CSTree &T) /從第v個頂點出發(fā)濃深度優(yōu)先遍歷圖G，建立以T為根的生成樹。 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é)點 *p = GetVex(G,w),NULL,NULL; if(first) /w是v的第一個未被訪問的鄰接頂點 T-lchild = p; first = FALSE; /是根的左孩子結(jié)點 /if else /w是v的其它未被訪問的鄰接頂點 q-nextsibling = p; /是上一鄰接頂點的右兄弟結(jié)點 /else q = p; DFSTree(G,w,q); /從第w個

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

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

33、的最小生成樹算法實現(xiàn)：圖用鄰接矩陣表示算法描述：算法評價：T(n)=O(n)void MiniSpanTree_PRIM(MGraph G,VertexType u) /用普里姆算法從第u個頂點出發(fā)構(gòu)造網(wǎng)G的最小生成樹T，輸出T的各條邊。 /記錄從頂點集U到V-U的代價最小的邊的輔助數(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); /輸出生成樹的邊 closedgek.lowcost = 0; /第k頂點并入U集 for(j = 0;jG.vexnum;+j) if(G.arcskj.adjclosedgej.lowcost) /新頂點并入U后重新選擇最小邊 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)，令最小生成樹初始狀態(tài)為只有n個頂點而無邊的非連通圖T=(V,)，每個頂點自成一個連通分量在E中選取代價最小的邊，若該邊依附的頂點落在T中不同的連通分量上，則將此邊加入到T中；否則，舍去此邊，選取下一條代價最小的邊依此類推，直至T中所有頂點都在同一連通分量上為止例165432651356642516543212345（0）用頂點數(shù)組和邊數(shù)組存放頂點和邊信息（1）初始時，令每個頂點的jihe互不相同；每個邊的

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

37、E;算法描述：例1654326513566425datajihe124536124536124536vexhweight112213233544vextflag61535500000001342567893345566664260000111114211122222165432123457.4.2 有向無環(huán)圖的應(yīng)用1. 基本概念 有向無環(huán)圖（Directed Acyclic Graph） 一個無環(huán)的有向圖，簡稱DAG圖。 作用：是描述一項工程進行過程的有效工具。主要進行拓撲排序和關(guān)鍵路徑的操作。V1V2V4V5V8DAGV3V7V6DG2. 拓撲排序問題提出： 學生應(yīng)按怎樣的順序?qū)W習這些課程，

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

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

40、成一個線性序列的過程（深度優(yōu)先遍歷）檢測AOV網(wǎng)中是否存在環(huán)的方法：對有向圖構(gòu)造其頂點的拓撲有序序列，若網(wǎng)中所有頂點都在它的拓撲有序序列中，則該AOV網(wǎng)必定不存在環(huán)拓撲排序的方法在有向圖中選一個沒有前驅(qū)的頂點且輸出之從圖中刪除該頂點和所有以它為尾的弧重復(fù)上述兩步，直至全部頂點均已輸出；或者當圖中不存在無前驅(qū)的頂點為止動畫演示C1C2C3C4C5C6C7C8C9C10C11C12拓撲序列：C1-C2-C3-C4-C5-C7-C9-C10-C11-C6-C12-C8或 ：C9-C10-C11-C6-C1-C12-C4-C2-C3-C5-C7-C8一個AOV網(wǎng)的拓撲序列不是唯一的算法實現(xiàn)以鄰接表作存

41、儲結(jié)構(gòu)把鄰接表中所有入度為0的頂點進棧棧非空時，輸出棧頂元素Vj并退棧；在鄰接表中查找Vj的直接后繼Vk，把Vk的入度減1；若Vk的入度為0則進棧重復(fù)上述操作直至?？諡橹?。若棧空時輸出的頂點個數(shù)不是n，則有向圖有環(huán)；否則，拓撲排序完畢類似算法 7.11Status TopologicalSort(ALGraph G) /有向圖G采用鄰接表存儲結(jié)構(gòu)。 /若G無回路，則輸出G的頂點的一個拓撲序列并返回OK，否則ERROR。 FindInDegree(G,indegree); /對各頂點求入度indegree0.vernum-1 InitStack(S); for(i = 0;inextarc) k

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

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

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

45、求Ve(i)求Vl(j)求e(i)求l(i)計算l(i)-e(i)987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4V1V2V3V4V5V6V7V8V9頂點 Ve Vl0645771614180668710161418a1a2a3a4a5a6a7a8a9a10a11活動 e l l-e00002266046258377077071031616014140033e(i)=Ve(j) l(i)=Vl(k)-dut() 算法實現(xiàn)輸入頂點和弧信息，建立其鄰接表 計算每個頂點的入度 對其進行拓撲排序 排序過程中求頂點的Vei 將得到的拓撲序列進

46、棧 按逆拓撲序列求頂點的Vli 計算每條弧的ei和li,找出ei=li的關(guān)鍵活動Status TopologicalOrder ( ALGraph G, SqStack &T ) / 有向圖 G 采用鄰接表存儲結(jié)構(gòu)，求各頂點事件的最早發(fā)生時間 ve（全局變量）。/ T 為拓撲序列頂點棧，S 為零入度頂點棧。/ 如果 G 無回路，則用棧 T 返回 G 的一個拓撲序列，且函數(shù)值為 OK，否則為 ERROR。FindInDegree ( G, indegree ); / 對各頂點求入度 indegree 0.vernum-1InitStack (S); / 初始化零入度頂點棧 Sfor ( i =

47、0; i nextarc ) k = p-adjvex; / 對 j 號頂點的每個鄰接點入度減 1if ( ! ( -indegree k ) ) Push ( S, k ); / 若入度減為 0 ，則入棧if ( vej + *( p-info) vek ) / 求各頂點的最早發(fā)生時間 vek = vej + *( p-info)； / for 結(jié)束 / while 結(jié)束if ( count nextarc ) k = p-adjvex; dut = *( p-info ); / dut 是事件 vj 到事件 vk 活動持續(xù)時間，即 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)鍵活動 / for ( p = G.verticesj.firstarc ) 結(jié)束 / CriticalPath7.4.3 最短路徑問題提出用帶權(quán)的有向圖表示一個交通運輸網(wǎng)，圖中：頂點表示城市邊表示城市間的交通聯(lián)系權(quán)表示此線路的長度或沿此線路運輸所花的時間或費用等問題：從某

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

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

51、13-192220V4:19終點 從V0到各終點的最短路徑及其長度V1V2V3V4V5V6Vj-2120V6:205164320856230137173294. 算法實現(xiàn)圖用帶權(quán)鄰接矩陣存儲ad數(shù)組dist存放當前找到的從源點V0到每個終點的最短路徑長度，其初態(tài)為圖中直接路徑權(quán)值數(shù)組pre表示從V0到各終點的最短路徑上，此頂點的前一頂點的序號；若從V0到某終點無路徑，則用0作為其前一頂點的序號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長度最短路法分析：T(n)=O(n)算法描述 類似算法 7.15void ShortestPath_DIJ( MGraph G, int v0, PathMatrix &p, ShortPathTable &D) / 用Dijkstra 算法求有向網(wǎng)G的v0頂點到其余頂點v的最短路/pv及其帶權(quán)長度Dv。若pvw為TRUE，則w是從v0到v / 當前求得最短路徑上的頂點。 finalv為TRUE當且僅當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頂點屬于S集 /開始主循環(huán)，每次求得v0到某個v頂點的最短路徑，并加v到S集 for (i=1;iG.vexnum;+i) / 其余G.vexnum-1個頂點 min=INFINITY; / 當前所知離v0頂點的最近距離 for (w=0;wG.vexnum;+w) if(!finalw) if(Dwmin) v=w; min=D