數(shù)據(jù)結(jié)構(gòu)教學(xué)課件：Chapter Seven Graph

1、數(shù)據(jù)結(jié)構(gòu)Chapter Seven Graph引圖的基本概念圖的存儲(chǔ)表示圖的遍歷與連通性 最小生成樹(shù)最短路徑 活動(dòng)網(wǎng)絡(luò) 圖是由頂點(diǎn)集合(vertex)及頂點(diǎn)間的關(guān)系集合組成的一種數(shù)據(jù)結(jié)構(gòu)： Graph( V, E ) 其中 ： V = x | x 某個(gè)數(shù)據(jù)對(duì)象 是頂點(diǎn)的有窮非空集合； E = (x, y) | x, y V 或 E = | x, y V & Path (x, y) 是頂點(diǎn)之間關(guān)系的有窮集合，也叫做邊(edge)集合。Path (x, y)表示從 x 到 y 的一條單向通路, 它是有方向的。1、圖的概念：定義1、圖的概念：常用術(shù)語(yǔ)有向圖與無(wú)向圖 ： 在有向圖中，頂點(diǎn)對(duì)是有序的。在

2、無(wú)向圖中，頂點(diǎn)對(duì)(x, y)是無(wú)序的。完全圖： 若有 n 個(gè)頂點(diǎn)的無(wú)向圖有 n(n-1)/2 條邊, 則此圖為完全無(wú)向圖。有 n 個(gè)頂點(diǎn)的有向圖有n(n-1) 條邊, 則此圖為完全有向圖。鄰接頂點(diǎn)： 如果 (u, v) 是 E(G) 中的一條邊，則稱u 與 v 互為鄰接頂點(diǎn)。1、圖的概念：常用術(shù)語(yǔ)權(quán)： 某些圖的邊具有與它相關(guān)的數(shù), 稱之為權(quán)。這種帶權(quán)圖叫做網(wǎng)絡(luò)。子圖： 設(shè)有兩個(gè)圖 G(V, E) 和 G(V, E)。若 V V 且 E E, 則稱 圖G 是 圖G 的子圖。頂點(diǎn)的度： 一個(gè)頂點(diǎn)v的度是與它相關(guān)聯(lián)的邊的條數(shù)。記作TD(v)。在有向圖中, 頂點(diǎn)的度等于該頂點(diǎn)的入度與出度之和。1、圖的

3、概念：常用術(shù)語(yǔ)頂點(diǎn) v 的入度：是以 v 為終點(diǎn)的有向邊的條數(shù), 記作 ID(v)； 頂點(diǎn) v 的出度：是以 v 為始點(diǎn)的有向邊的條數(shù), 記作 OD(v)。路徑： 在圖 G(V, E) 中, 若從頂點(diǎn) vi 出發(fā), 沿一些邊經(jīng)過(guò)一些頂點(diǎn) vp1, vp2, , vpm，到達(dá)頂點(diǎn)vj。則稱頂點(diǎn)序列 ( vi vp1 vp2 . vpm vj ) 為從頂點(diǎn)vi 到頂點(diǎn) vj 的路徑。它經(jīng)過(guò)的邊(vi, vp1)、(vp1, vp2)、.、(vpm, vj)應(yīng)是屬于E的邊。路徑長(zhǎng)度 ：非帶權(quán)圖的路徑長(zhǎng)度是指此路徑上邊的條數(shù)。帶權(quán)圖的路徑長(zhǎng)度是指路徑上各邊的權(quán)之和。1、圖的概念：常用術(shù)語(yǔ)簡(jiǎn)單路徑：若路

4、徑上各頂點(diǎn) v1,v2,.,vm 均不互相重復(fù), 則稱這樣的路徑為簡(jiǎn)單路徑?；芈罚?若路徑上第一個(gè)頂點(diǎn) v1 與最后一個(gè)頂點(diǎn)vm 重合, 則稱這樣的路徑為回路或環(huán)。連通圖與連通分量：在無(wú)向圖中, 若從頂點(diǎn)v1到頂點(diǎn)v2有路徑, 則稱頂點(diǎn)v1與v2是連通的。如果圖中任意一對(duì)頂點(diǎn)都是連通的, 則稱此圖是連通圖。非連通圖的極大連通子圖叫做連通分量。1、圖的概念：常用術(shù)語(yǔ)強(qiáng)連通圖與強(qiáng)連通分量：在有向圖中, 若對(duì)于每一對(duì)頂點(diǎn)vi和vj, 都存在一條從vi到vj和從vj到vi的路徑, 則稱此圖是強(qiáng)連通圖。非強(qiáng)連通圖的極大強(qiáng)連通子圖叫做強(qiáng)連通分量。生成樹(shù)： 一個(gè)連通圖的生成樹(shù)是它的極小連通子圖，在n個(gè)頂點(diǎn)的

5、情形下，有n-1條邊。但有向圖則可能得到它的由若干有向樹(shù)組成的生成森林。本章不予討論的圖例213213有向完全圖無(wú)向完全圖356例245136圖與子圖1、圖的概念：示例例245136G1頂點(diǎn)2入度：1 出度：3頂點(diǎn)4入度：1 出度：0例157324G26頂點(diǎn)5的度：3頂點(diǎn)2的度：41、圖的概念：示例例157324G26例245136G1路徑：1，2，3，5，6，3路徑長(zhǎng)度：5簡(jiǎn)單路徑：1，2，3，5回路：1，2，3，5，6，3，1簡(jiǎn)單回路：3，5，6，3路徑：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，11、圖

6、的概念：示例連通圖例245136強(qiáng)連通圖356非連通圖連通分量例2451361、圖的概念：示例2、圖的基本操作CreatGraph(G)輸入圖G的頂點(diǎn)和邊，建立圖G的存儲(chǔ)。DestroyGraph(G)釋放圖G占用的存儲(chǔ)空間。GetVex(G，v)在圖G中找到頂點(diǎn)v，并返回頂點(diǎn)v的相關(guān)信息。PutVex(G，v，value)在圖G中找到頂點(diǎn)v，并將value值賦給頂點(diǎn)v。InsertVex(G，v)在圖G中增添新頂點(diǎn)v。DeleteVex(G，v)在圖G中，刪除頂點(diǎn)v以及所有和頂點(diǎn)v相關(guān)聯(lián)的邊或弧。InsertArc(G，v，w)在圖G中增添一條從頂點(diǎn)v到頂點(diǎn)w的邊或弧。2、圖的基本操作Del

7、eteArc(G，v，w)在圖G中刪除一條從頂點(diǎn)v到頂點(diǎn)w的邊或弧。DFSTraverse(G，v)在圖G中，從頂點(diǎn)v出發(fā)深度優(yōu)先遍歷圖G。BFSTtaverse(G，v)在圖G中，從頂點(diǎn)v出發(fā)廣度優(yōu)先遍歷圖G。LocateVex(G，u)在圖G中找到頂點(diǎn)u，返回該頂點(diǎn)在圖中位置。FirstAdjVex(G，v)在圖G中，返回v的第一個(gè)鄰接點(diǎn)。若頂點(diǎn)在G中沒(méi)有鄰接頂點(diǎn)，則返回“空”。NextAdjVex(G，v，w)在圖G中，返回v的(相對(duì)于w的)下一個(gè)鄰接頂點(diǎn)。若w是v的最后一個(gè)鄰接點(diǎn)，則返回“空”。2、圖的基本操作 說(shuō)明：一個(gè)圖中，頂點(diǎn)是無(wú)序的，但當(dāng)采用某一種確定的存儲(chǔ)方式存儲(chǔ)后，存儲(chǔ)結(jié)構(gòu)

8、中頂點(diǎn)的存儲(chǔ)次序構(gòu)成了頂點(diǎn)之間的相對(duì)次序，這里用頂點(diǎn)在圖中的位置表示該頂點(diǎn)的存儲(chǔ)順序；同樣的道理，對(duì)一個(gè)頂點(diǎn)的所有鄰接點(diǎn)，采用該頂點(diǎn)的第i個(gè)鄰接點(diǎn)表示與該頂點(diǎn)相鄰接的某個(gè)頂點(diǎn)的存儲(chǔ)順序?？傊?，存儲(chǔ)方式導(dǎo)致順序，導(dǎo)致定位。3、圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu)有如下常用4種：(1) 鄰接矩陣(2) 鄰接表(3) 十字鏈表(4) 鄰接多重表3、圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu):鄰接矩陣思想：(1) 用一維數(shù)組存儲(chǔ)圖中頂點(diǎn) (2) 用矩陣表示圖中各頂點(diǎn)之間的鄰接關(guān)系 ，所以該矩陣稱為鄰接矩陣。1表示有連接邊，0表示無(wú)連接邊。(3) 網(wǎng)絡(luò)圖中，鄰接矩陣中有邊的數(shù)值為權(quán)值，無(wú)邊的填3、圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu):鄰接矩陣?yán)?/p>

9、：3、圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu):鄰接矩陣?yán)河邢驁D3、圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu):鄰接矩陣分析：無(wú)向圖的鄰接矩陣是對(duì)稱的，有向圖的鄰接矩陣可能是不對(duì)稱的。在有向圖中, 統(tǒng)計(jì)第 i 行 1 的個(gè)數(shù)可得頂點(diǎn) i 的出度，統(tǒng)計(jì)第 j 列 1 的個(gè)數(shù)可得頂點(diǎn) j 的入度。在無(wú)向圖中, 統(tǒng)計(jì)第 i 行 (列) 1 的個(gè)數(shù)可得頂點(diǎn)i 的度。3、圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu):鄰接矩陣缺點(diǎn)：確定圖中包含邊的數(shù)目困難。3、圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu):鄰接矩陣數(shù)據(jù)結(jié)構(gòu)： #define MaxVertexNum 100 /*最大頂點(diǎn)數(shù)設(shè)為100*/ typedef char VertexType; /*頂點(diǎn)類型設(shè)為字符型

10、*/ typedef int EdgeType; /*邊的權(quán)值設(shè)為整型*/ typedef struct VertexType vexsMaxVertexNum; /*頂點(diǎn)表*/ /*鄰接矩陣，即邊表*/ EdeType edgesMaxVertexNumMaxVertexNum; int n,e; /*頂點(diǎn)數(shù)和邊數(shù)*/ Mgragh; /*Maragh是以鄰接矩陣存儲(chǔ)的圖類型*/3、圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu):鄰接表思想：(1) 用一維數(shù)組存儲(chǔ)圖中頂點(diǎn) ，數(shù)據(jù)元素有指針域(2) 對(duì)應(yīng)一條邊，建立一個(gè)節(jié)點(diǎn)，稱為邊節(jié)點(diǎn)；邊節(jié)點(diǎn)形成鏈表3、圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu):鄰接表例：無(wú)向圖3、圖的存儲(chǔ)結(jié)構(gòu)圖

11、的存儲(chǔ)結(jié)構(gòu):鄰接表例：有向圖在有向圖的鄰接表中，第 i 個(gè)邊鏈表鏈接的邊都是頂點(diǎn) i 發(fā)出的邊。也叫做出邊表。在有向圖的逆鄰接表中，第 i 個(gè)邊鏈表鏈接的邊都是進(jìn)入頂點(diǎn) i 的邊。也叫做入邊表。3、圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu):鄰接表例：有向網(wǎng)圖3、圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu):鄰接表節(jié)點(diǎn)結(jié)構(gòu)3、圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu):鄰接表數(shù)據(jù)結(jié)構(gòu)：邊結(jié)構(gòu) define MaxVerNum 100 /*最大頂點(diǎn)數(shù)為100*/ typedef struct node /*邊表結(jié)點(diǎn)*/ int adjvex; /*鄰接點(diǎn)域*/ struct node * next; /*指向下一個(gè)鄰接點(diǎn)的指針域*/ /*若要表示網(wǎng)圖

12、，則還需增一個(gè)數(shù)據(jù)域info*/ EdgeNode; 3、圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu):鄰接表數(shù)據(jù)結(jié)構(gòu)：節(jié)點(diǎn)結(jié)構(gòu)typedef struct vnode /*頂點(diǎn)表結(jié)點(diǎn)*/ VertexType vertex; /*頂點(diǎn)域*/ EdgeNode * firstedge; /*邊表頭指針*/ VertexNode; /*AdjList是鄰接表類型*/typedef VertexNode AdjListMaxVertexNum; typedef struct AdjList adjlist; /*鄰接表*/ int n,e; /*頂點(diǎn)數(shù)和邊數(shù)*/ ALGraph; /*ALGraph是以鄰接表存儲(chǔ)的圖

13、類型*/3、圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu):十字鏈表思想：(1) 用一維數(shù)組存儲(chǔ)圖中頂點(diǎn) ，數(shù)據(jù)元素有兩個(gè)指針域，一個(gè)用于指示出度，另一個(gè)用于指示一個(gè)入度(2) 邊的邊節(jié)點(diǎn)，包含該邊的兩個(gè)頂點(diǎn)；同時(shí)包含兩指針區(qū)域，分別指向同一個(gè)出點(diǎn)和同一個(gè)入點(diǎn)(3) 是鄰接多重表的有向圖表示3、圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu):十字鏈表節(jié)點(diǎn)結(jié)構(gòu)：在弧結(jié)點(diǎn)中有五個(gè)域：其中尾域(tailvex)和頭(headvex)分別指示弧尾和弧頭這兩個(gè)頂點(diǎn)在圖中的位置，鏈域hlink指向弧頭相同的下一條弧，鏈域tlink指向弧尾相同的下一條弧，info域指向該弧的相關(guān)信息。3、圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu):十字鏈表例：有向圖弧頭相同的弧在同一

14、鏈表上，弧尾相同的弧也在同一鏈表上。它們的頭結(jié)點(diǎn)即為頂點(diǎn)結(jié)點(diǎn)，它由三個(gè)域組成：其中vertex域存儲(chǔ)和頂點(diǎn)相關(guān)的信息，如頂點(diǎn)的名稱等；firstin和firstout為兩個(gè)鏈域，分別指向以該頂點(diǎn)為弧頭或弧尾的第一個(gè)弧結(jié)點(diǎn) 3、圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu):鄰接多重表思想：(1) 用一維數(shù)組存儲(chǔ)圖中頂點(diǎn) ，數(shù)據(jù)元素有一個(gè)指針域。(2) 邊的邊節(jié)點(diǎn)，包含該邊的兩個(gè)頂點(diǎn)；同時(shí)包含兩指針區(qū)域，分別指向同一個(gè)出點(diǎn)和同一個(gè)入點(diǎn)(3) 主要用于無(wú)向圖。3、圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu):鄰接多重表節(jié)點(diǎn)結(jié)構(gòu)：3、圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu):鄰接多重表例：無(wú)向圖3、圖的遍歷 圖遍歷的分析定義：圖的遍歷是指從圖中的任一頂點(diǎn)出

15、發(fā)，對(duì)圖中的所有頂點(diǎn)訪問(wèn)一次且只訪問(wèn)一次。如何訪問(wèn)所有的連通分量？如何選擇一個(gè)頂點(diǎn)的多個(gè)鄰接點(diǎn)？圖的遍歷算法，有深度遍歷(DFS)和廣度遍歷(BFS)兩種。如何走出回路？3、圖的遍歷遍歷算法思路：設(shè)置訪問(wèn)標(biāo)記數(shù)組，visitedn；利用堆棧實(shí)現(xiàn)DFS，利用隊(duì)列實(shí)現(xiàn)BFS。DFS遍歷序列：v1v2 v4 v8 v5 v3 v6 v7BFS遍歷序列：v1v2 v3 v4 v5 v6 v7 v83、圖的遍歷DFS遍歷算法 （dfs.cpp） /*從第v個(gè)頂點(diǎn)出發(fā)遞歸地深度優(yōu)先遍歷圖G*/void DFS(Graph G,int v )/*訪問(wèn)第v個(gè)頂點(diǎn)*/visitedv=TRUE;VisitFun

16、c(v); for(w=FisrAdjVex(G,v);w; w=NextAdjVex(G,v,w) /*對(duì)v的尚未訪問(wèn)的鄰接頂點(diǎn)w遞歸調(diào)用DFS*/ if (!visitedw) DFS(G,w); 3、圖的遍歷DFS遍歷算法示例abchdekfg812345670F F F F F F F F F0 1 2 3 4 5 6 7 8TTTTTTTTTachdkfe bgachkfedbg訪問(wèn)標(biāo)志:訪問(wèn)次序:例如:achdkfe3、圖的遍歷BFS遍歷算法 （bfs.cpp）/*按廣度優(yōu)先非遞歸遍歷圖G*/void BFSTraverse(Graph G, Status(*Visit)(int

17、v) for (v=0;vG,vexnum;+v) visitedv=FALSE ; InitQueue(Q); /*置空隊(duì)列Q*/if (!visitedv) /*v尚未訪問(wèn)*/ EnQucue(Q,v); /*v入隊(duì)列*/ while (!QueueEmpty(Q) DeQueue(Q,u); /*隊(duì)頭元素出隊(duì)并置為u*/ visitedu=TRUE; visit(u); /*訪問(wèn)u*/ for(w=FistAdjVex(G,u); w; w=NextAdjVex(G,u,w) /*u的尚未訪問(wèn)的鄰接頂點(diǎn)w入隊(duì)列Q*/ if (!visitedw) EnQueue(Q,w); ? v4,v

18、5會(huì)導(dǎo)致v8重復(fù)入隊(duì)3、圖的遍歷BFS遍歷算法示例（bfs.cpp）3、圖的連通 無(wú)向圖的連通性思路：在循環(huán)調(diào)用DFS時(shí)，增加計(jì)數(shù)如果計(jì)數(shù)為0，則為連通，否則為非連通3、圖的連通 有向圖的連通性思路：先對(duì)出邊表操作，循環(huán)調(diào)用DFS，并計(jì)數(shù)，令為N。在每次調(diào)用DFS結(jié)束后，建立當(dāng)前VISITED頂點(diǎn)集合。此時(shí)可以得到N個(gè)頂點(diǎn)集合。再對(duì)入邊表操作，循環(huán)調(diào)用DFS，并計(jì)數(shù)，令為M。在每次調(diào)用DFS結(jié)束后，建立當(dāng)前VISITED頂點(diǎn)集合。此時(shí)可以得到M個(gè)頂點(diǎn)集合。比較兩次結(jié)果，即可得出結(jié)論。4、圖的生成樹(shù)和生成森林 定義當(dāng)無(wú)向圖為非連通圖時(shí)，從圖中某一頂點(diǎn)出發(fā)，利用深度優(yōu)先搜索算法或廣度優(yōu)先搜索算法不

19、可能遍歷到圖中的所有頂點(diǎn)，只能訪問(wèn)到該頂點(diǎn)所在的最大連通子圖(連通分量)的所有頂點(diǎn)。若從無(wú)向圖的每一個(gè)連通分量中的一個(gè)頂點(diǎn)出發(fā)進(jìn)行遍歷，可求得無(wú)向圖的所有連通分量。在算法中，需要對(duì)圖的每一個(gè)頂點(diǎn)進(jìn)行檢測(cè)：若已被訪問(wèn)過(guò)，則該頂點(diǎn)一定是落在圖中已求得的連通分量上；若還未被訪問(wèn)，則從該頂點(diǎn)出發(fā)遍歷圖，可求得圖的另一個(gè)連通分量。4、圖的生成樹(shù)和生成森林 定義對(duì)于非連通的無(wú)向圖，所有連通分量的生成樹(shù)組成了非連通圖的生成森林。4、圖的生成樹(shù)和生成森林 算法對(duì)圖進(jìn)行DFS(BFS)遍歷每次循環(huán)調(diào)用DFS時(shí)，表明有一個(gè)新的樹(shù)根節(jié)點(diǎn)產(chǎn)生。在DFS中，找到一個(gè)節(jié)點(diǎn)連入本次樹(shù)根節(jié)點(diǎn)。4、圖的生成樹(shù)和生成森林 算法/

20、*建立無(wú)向圖G的深度優(yōu)先生成森林的孩子兄弟鏈表T*/void DESForest(Graph G, CSTree *T) T=NULL; for (v=0;vG.vexnum;+v) visitedv=FALSE; for(v=0;vnextsibling=p; q=p; /*q指示當(dāng)前生成樹(shù)的根*/ DFSTree(G,v,&p); /*建立以p為根的生成樹(shù)*/生成樹(shù)采用孩子兄弟表示：(P129)CSTree : data , child, nextsibling4、圖的生成樹(shù)和生成森林 算法/*從第v個(gè)頂點(diǎn)出發(fā)深度優(yōu)先遍歷圖G，建立以*T為根的生成樹(shù)*/void DFSTree(Graph

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

22、=p;/*從第w個(gè)頂點(diǎn)出發(fā)深度優(yōu)先遍歷圖G，建立生成子樹(shù)*q*/ DFSTree(G,w,&q); 本算法開(kāi)始始終建立第一個(gè)子孩子，然后再建立兄弟，建立兄弟時(shí)候first為false,從底部向上建立5、最小生成樹(shù) 定義無(wú)向連通圖生成樹(shù)不是唯一的5、最小生成樹(shù) 定義按照生成樹(shù)的定義，n 個(gè)頂點(diǎn)的連通網(wǎng)絡(luò)的生成樹(shù)有 n 個(gè)頂點(diǎn)、n-1 條邊。如果無(wú)向連通圖是網(wǎng)，則必然有一個(gè)生成樹(shù)的各邊上的權(quán)值之和最小，此時(shí)這個(gè)生成樹(shù)稱為最小生成樹(shù)。構(gòu)造最小生成樹(shù)的準(zhǔn)則:必須只使用該網(wǎng)絡(luò)中的邊來(lái)構(gòu)造最小生成樹(shù)；必須使用且僅使用 n-1 條邊來(lái)聯(lián)結(jié)網(wǎng)絡(luò)中的 n 個(gè)頂點(diǎn)；不能使用產(chǎn)生回路的邊。5、最小生成樹(shù) 算法依據(jù)：

23、MST性質(zhì)在生成樹(shù)的構(gòu)造過(guò)程中，圖中 n 個(gè)頂點(diǎn)分屬兩個(gè)集合：已落在生成樹(shù)上的頂點(diǎn)集 U 和尚未落在生成樹(shù)上的頂點(diǎn)集V-U ，則應(yīng)在所有連通U中頂點(diǎn)和V-U中頂點(diǎn)的邊中選取權(quán)值最小的邊。UV-U5、最小生成樹(shù) 普里姆(Prim)算法算法描述：從連通網(wǎng)絡(luò) N = V, E 中的某一頂點(diǎn) u0 出發(fā)，選擇與它關(guān)聯(lián)的具有最小權(quán)值的邊(u0, v)，將其頂點(diǎn)加入到生成樹(shù)的頂點(diǎn)集合U中。以后每一步從一個(gè)頂點(diǎn)在U中，而另一個(gè)頂點(diǎn)不在U中的各條邊中選擇權(quán)值最小的邊(u, v),把它的頂點(diǎn)加入到集合U中。如此繼續(xù)下去，直到網(wǎng)絡(luò)中的所有頂點(diǎn)都加入到生成樹(shù)頂點(diǎn)集合U中為止。采用鄰接矩陣作為圖的存儲(chǔ)表示。5、最小生

24、成樹(shù) 普里姆(Prim)算法演示：abcdegf195141827168213127aedcbaaa19141814例如:e12ee8168d3dd7213c55 19 m m 14 m 1819 5 7 12 m m m 5 3 m m m m 7 3 8 21 m14 12 m 8 m 16 m m m 21 m 2718 m m m 16 27abcdefg5、最小生成樹(shù) 普里姆(Prim)算法實(shí)現(xiàn)(prim.cpp)1、建立矩陣存儲(chǔ)圖中邊的權(quán)。 4、初始選任一起點(diǎn)closevertex將矩陣中對(duì)應(yīng)行的權(quán)數(shù)值lowcostmin得下一點(diǎn)closevertex將矩陣中對(duì)應(yīng)行的權(quán)數(shù)值lowc

25、ostmin得下一點(diǎn)2、建立數(shù)組lowcost記錄每一頂點(diǎn)到達(dá)其他頂點(diǎn)的權(quán)數(shù)值，用于比較求出最小權(quán)數(shù)值。 3、建立數(shù)組closevertx記錄每一頂點(diǎn)最小權(quán)值的另一點(diǎn)。 5、每增加一新點(diǎn)，lowcost將會(huì)改變，因?yàn)樾曼c(diǎn)可能導(dǎo)致到某些點(diǎn)的權(quán)數(shù)值變小。而closevertx和lowcost記錄了全部搜索過(guò)程。5、最小生成樹(shù) 克魯斯卡爾 (Kruskal)算法算法描述：設(shè)有一個(gè)有 n 個(gè)頂點(diǎn)的連通網(wǎng)絡(luò) N = V, E ：(1)最初先構(gòu)造一個(gè)只有 n 個(gè)頂點(diǎn)，沒(méi)有邊的非連通圖 T = V, , 圖中每個(gè)頂點(diǎn)自成一個(gè)連通分量。(2)當(dāng)在 E 中選到一條具有最小權(quán)值的邊時(shí),若該邊的兩個(gè)頂點(diǎn)落在不同的連

26、通分量上，則將此邊加入到 T 中；否則將此邊舍去，重新選擇一條權(quán)值最小的邊。(3)如此重復(fù)下去，直到所有頂點(diǎn)在同一個(gè)連通分量上為止。5、最小生成樹(shù) 克魯斯卡爾 (Kruskal)算法演示：abcdegf195141827168213127aedcbgf148531621例如:71218195、最小生成樹(shù) 克魯斯卡爾 (Kruskal)算法實(shí)現(xiàn)(Kruskal.cpp)1、建立所有邊的數(shù)組，結(jié)構(gòu)如下： typedef struct elemtype v1; elemtype v2; int cost; EdgeType; 并將該數(shù)組按照cost升序2、建立father數(shù)組，記錄填加邊的頂點(diǎn)號(hào)，如

27、果相互連通，則為同一數(shù)字；如果新加邊的兩個(gè)頂點(diǎn)father數(shù)組記錄相同，為回路，該邊被舍棄；否則填加，直到找到n-1個(gè)邊為止。5、最小生成樹(shù) 比較兩種算法普里姆算法克魯斯卡爾算法時(shí)間復(fù)雜度O(n2)O(elog2e + elog2n + n)稠密圖稀疏圖算法名適應(yīng)范圍*最小堆和并查集算法6、兩點(diǎn)之間的最短路徑問(wèn)題兩點(diǎn)之間的最短路徑問(wèn)題最短路徑問(wèn)題：如果從圖中某一頂點(diǎn)(稱為源點(diǎn))到達(dá)另一頂點(diǎn)(稱為終點(diǎn))的路徑可能不止一條，如何找到一條路徑使得沿此路徑上各邊上的權(quán)值總和達(dá)到最小 。(1)、求從某個(gè)源點(diǎn)到其余各點(diǎn)的最短路徑 Dijkstra算法(2)、每一對(duì)頂點(diǎn)之間的最短路徑 Floyd算法通常包括

28、兩個(gè)問(wèn)題6、兩點(diǎn)之間的最短路徑問(wèn)題單源最短路徑問(wèn)題 (Dijkstra算法)問(wèn)題的提法： 給定一個(gè)帶權(quán)有向圖D與源點(diǎn)v，求從v到D中其它頂點(diǎn)的最短路徑。限定各邊上的權(quán)值大于或等于0。為求得這些最短路徑，Dijkstra提出按路徑長(zhǎng)度的遞增次序，逐步產(chǎn)生最短路徑的算法。首先求出長(zhǎng)度最短的一條最短路徑，再參照它求出長(zhǎng)度次短的一條最短路徑，依次類推，直到從頂點(diǎn)v到其它各頂點(diǎn)的最短路徑全部求出為止。Dijkstra算法示例1383032V2:813-133032V1:13-13302220V3:13-192220V4:19終點(diǎn) 從V0到各終點(diǎn)的最短路徑及其長(zhǎng)度V1V2V3V4V5V6Vj-2120V6

29、:205164320856230137173296、兩點(diǎn)之間的最短路徑問(wèn)題單源最短路徑問(wèn)題 (Dijkstra算法)算法實(shí)現(xiàn)：引入一個(gè)輔助數(shù)組dist。它的每一個(gè)分量disti表示當(dāng)前找到的從源點(diǎn)v0到終點(diǎn)vi 的最短路徑的長(zhǎng)度。初始狀態(tài)：若從源點(diǎn)v0到頂點(diǎn)vi有邊，則disti為該邊上的權(quán)值；若從源點(diǎn)v0到頂點(diǎn)vi 沒(méi)有邊，則disti為+ 。一般情況下，假設(shè) S 是已求得的最短路徑的終點(diǎn)的集合，則可證明：下一條最短路徑必然是從v0 出發(fā)，中間只經(jīng)過(guò)S中的頂點(diǎn)便可到達(dá)的那些頂點(diǎn)vx (vx V-S )的路徑中的一條。每次求得一條最短路徑之后，其終點(diǎn)vk 加入集合S，然后對(duì)所有的vi V-S，修改其disti值。6、兩點(diǎn)之間的最短路徑問(wèn)題單源最短路徑問(wèn)題 (Dijkstra算法)算法實(shí)現(xiàn)： （ Dijkstra.cpp & Dijkstra.gif） 初始化： S v0 ; distj Edge0j, j = 1, 2, , n-1; / n為圖中頂點(diǎn)個(gè)數(shù) 求出最短路徑的長(zhǎng)度： distk min disti , i V- S ; S S U k ; 修改： disti min disti, distk