《數(shù)據(jù)結(jié)構(gòu)》課件第7章 圖

1、第7章 圖學(xué)習(xí)要點(diǎn): 熟悉圖的各種存儲(chǔ)結(jié)構(gòu)及其構(gòu)造算法了解實(shí)際問題的求解效率與采用何種存儲(chǔ)結(jié)構(gòu)和算法的密切聯(lián)系熟練掌握?qǐng)D的兩種搜索路徑的遍歷：深度優(yōu)先搜索和廣度優(yōu)先搜索應(yīng)用圖的遍歷算法求解各種簡(jiǎn)單路徑問題，如關(guān)鍵路徑、最短路徑等7.1 圖的定義和基本術(shù)語7.1.1 圖的定義圖形結(jié)構(gòu)：較線性表和樹更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。結(jié)點(diǎn)之間的關(guān)系是任意的，圖中任意兩個(gè)數(shù)據(jù)元素都可能相關(guān)。圖的結(jié)構(gòu)定義：圖：是由一個(gè)頂點(diǎn)集 V 和一個(gè)頂點(diǎn)間的關(guān)系集合組成的數(shù)據(jù)結(jié)構(gòu)。Graph = (V , VR)其中，V = x | x 某個(gè)數(shù)據(jù)對(duì)象，是頂點(diǎn)的有窮非空集合；VR = (x, y) | x, y V 或 VR = |

2、 x, y V & Path (x, y) 是頂點(diǎn)之間關(guān)系的有窮集合，也叫做邊(edge)或弧(Arc)集合。Path (x, y)表示從 x 到 y 的一條單向通路, 它是有方向的?！盎　笔怯蟹较虻?，稱由頂點(diǎn)集和弧集構(gòu)成的圖為有向圖。例如：G1 = (V1, VR1)是一個(gè)有向圖。EACBD其中V1=A, B, C, D, EVR1=, , , , 弧尾弧頭若VR 必有VR, 則稱 (v,w) 為頂點(diǎn)v 和頂點(diǎn) w 之間存在一條邊。由頂點(diǎn)集和邊集構(gòu)成的圖稱作無向圖。 例如： G2=(V2,VR2) 其中，V2=A, B, C, D, E, F VR2=, , , , , , B CA D F

3、 E抽象數(shù)據(jù)類型定義：ADT Graph 數(shù)據(jù)對(duì)象V：V是頂點(diǎn)集。 數(shù)據(jù)關(guān)系R：R=VR， VR=| v, wV且P(v, w)， 表示從v到w的弧，謂詞P(v, w)定義了弧 的意義或信息 基本操作P：結(jié)構(gòu)的建立和銷毀對(duì)頂點(diǎn)的訪問操作插入或刪除頂點(diǎn)插入和刪除對(duì)鄰接點(diǎn)的操作遍歷ADT Graph7.1.2 基本術(shù)語有(無)向網(wǎng)：弧(邊)上帶權(quán)的圖。子圖：設(shè)圖G=(V,VR) 和圖 G=(V,VR),且 VV, VRVR，則稱 G 為 G 的子圖。ABECF1597211132AEFBBC假設(shè)圖中有n個(gè)頂點(diǎn)，e條邊，則含有 e=n(n-1)/2條邊的無向圖稱作完全圖；含有 e=n(n-1)條弧的

4、有向圖稱作有向完全圖；若邊或弧的個(gè)數(shù) enlogn，則稱作稀疏圖，否則稱作稠密圖。假若頂點(diǎn)v和頂點(diǎn)w之間存在一條邊，則稱頂點(diǎn)v和w互為鄰接點(diǎn)；邊(v,w)和頂點(diǎn)v及w相關(guān)聯(lián)；和頂點(diǎn)v關(guān)聯(lián)的邊的數(shù)目定義為頂點(diǎn)的度(TD)。例如： TD(A) = 2 TD(B) = 3ACDFEB對(duì)有向圖來說，頂點(diǎn)的出度(OD): 以頂點(diǎn)v為弧尾的弧的數(shù)目；頂點(diǎn)的入度(ID): 以頂點(diǎn)v為弧頭的弧的數(shù)目。頂點(diǎn)的度(TD)=出度(OD)+入度(ID)例如：OD(B) = 1 ID(B) = 2 TD(B) = 3設(shè)圖G=(V,VR)中的一個(gè)頂點(diǎn)序列 u=vi,0,vi,1, , vi,m=w中，(vi,j-1,vi

5、,j)VR，1jm，則稱從頂點(diǎn)u 到頂點(diǎn)w 之間存在一條路徑。ABECF有n個(gè)頂點(diǎn)，e條邊或弧的圖，滿足：路徑上邊的數(shù)目稱作路徑長(zhǎng)度。例如：從A到F且長(zhǎng)度為3的路徑為： A,B,C,F，A,E,C,F簡(jiǎn)單路徑：序列中頂點(diǎn)不重復(fù)出現(xiàn) 的路徑。簡(jiǎn)單回路：序列中只有第一個(gè)頂點(diǎn)和最后 一個(gè)頂點(diǎn)相同的回路。如，A,B,C,F,A若圖G中任意兩個(gè)頂點(diǎn)之間都有路徑相通，則稱此圖為連通圖；若無向圖為非連通圖，則圖中各個(gè)極大連通子圖稱作此圖的連通分量。ABECF對(duì)有向圖來說，若任意兩個(gè)頂點(diǎn)之間都存在一條有向路徑，則稱此有向圖為強(qiáng)連通圖。否則，其各個(gè)強(qiáng)連通子圖稱作它的強(qiáng)連通分量。BACDFEBACDFEABECF

6、ABECF假設(shè)一個(gè)連通圖有 n 個(gè)頂點(diǎn)和 e 條邊，其中 n-1 條邊和 n 個(gè)頂點(diǎn)構(gòu)成一個(gè)極小連通子圖，稱該極小連通子圖為此連通圖的生成樹。對(duì)非連通圖，則稱各個(gè)連通分量的生成樹的集合為此非連通圖的生成森林。BACDFEABEFCDABECDF比較：連通分量和生成樹！非連通圖的極大連通子圖連通圖的極小連通子圖7.2.1 圖的數(shù)組(鄰接矩陣)存儲(chǔ)表示鄰接矩陣 (Adjacency Matrix)頂點(diǎn)信息：記錄各個(gè)頂點(diǎn)信息的頂點(diǎn)表。邊或弧信息：各個(gè)頂點(diǎn)之間關(guān)系的鄰接矩陣。設(shè)圖 A = (V, E)是一個(gè)有 n 個(gè)頂點(diǎn)的圖，則圖的鄰接矩陣是一個(gè)二維數(shù)組 A.edgenn，定義：無向圖的鄰接矩陣是對(duì)稱

7、的，有向圖的鄰接矩陣可能是不對(duì)稱的。7.2 圖的存儲(chǔ)結(jié)構(gòu)無向圖：有向圖：BACDFEABECFABCDEF012345ABCDE01234C語言形式描述：typedef enumDG, DN, UDG, UDN GraphKind;typedef struct ArcCell / 邊/弧的定義 VRType adj; / VRType是頂點(diǎn)關(guān)系類型。 / 對(duì)無權(quán)圖，用1或0表示相鄰否；對(duì)帶權(quán)圖，則為權(quán)值類型。 InfoType *info; / 該弧相關(guān)信息的指針ArcCell, AdjMatrixMAX_VERTEX_NUM MAX_VERTEX_NUM;typedef struct / 圖

8、的定義 VertexType vexsMAX_VERTEX_NUM; / 頂點(diǎn)信息 AdjMatrix arcs; / 邊/弧的信息 (關(guān)系的鄰接矩陣) int vexnum, arcnum; / 頂點(diǎn)數(shù)，邊/弧數(shù) GraphKind kind; / 圖的種類標(biāo)志 MGraph;借助于鄰接矩陣容易求得頂點(diǎn)的度：在無向圖中,統(tǒng)計(jì)第i行(列)1的個(gè)數(shù)可得頂點(diǎn)i的度。即：在有向圖中統(tǒng)計(jì)第i行1的個(gè)數(shù)可得頂點(diǎn)i的出度;統(tǒng)計(jì)第j列1的個(gè)數(shù)可得頂點(diǎn)j的入度。TD(v1)=2TD(v6)=3OD(v1)=2ID(v1)=1則，TD(v1)=2+1=3網(wǎng)的鄰接矩陣：Status createUDN(Mgrap

9、h &G) /采用鄰接矩陣表示法, 構(gòu)造無向網(wǎng) scanf(&G.vexnum,&G.arcnum,&IncInfo); /讀入頂點(diǎn)數(shù)、邊 /數(shù)和相關(guān)信息 for (i=0;iG.vexnum;+i scanf(&G.vexsi); /構(gòu)造頂點(diǎn)表 for (i=0;iG.vexnum;+i) for (j=0;jG.vexnum;+j) G.arcsij=INFINITY,NULL; /初始化鄰接矩陣 for (k=0;kG.arcnum;+k) /構(gòu)造鄰接矩陣 Sacnf(&v1,&v2,&w); /輸入一條邊依附的頂點(diǎn)及權(quán)值 i=LocateVex(G, v1); j=LocateVex(

10、G, v2); /確定v1和v2在G中的位置 G.arcsij.adj=w; /弧的權(quán)值 If (IncInfo) Input(*G.); G.arcsji=G.arcsij; /置對(duì)稱弧 Return OK;7.2.2 圖的鄰接表存儲(chǔ)表示只存儲(chǔ)圖中已有的弧或邊的信息：對(duì)圖中的每個(gè)頂點(diǎn)都建立一個(gè)單鏈表來存儲(chǔ)所有依附于該頂點(diǎn)的弧或邊。無向圖：第i個(gè)單鏈表中的結(jié)點(diǎn)表示依附于頂點(diǎn)vi的邊。有向圖：第i個(gè)單鏈表中的結(jié)點(diǎn)表示以頂點(diǎn)vi為尾的弧。對(duì)圖中所有頂點(diǎn)使用一個(gè)一維數(shù)組來存放單鏈表中每個(gè)結(jié)點(diǎn)由三個(gè)域組成鄰接點(diǎn)域(adjvex):指示與頂點(diǎn)vi鄰接的點(diǎn)在圖中的位置；鏈域(next

11、arc):指示下一條邊或弧的結(jié)點(diǎn)；數(shù)據(jù)域(info):存儲(chǔ)和邊或弧相關(guān)的信息，如權(quán)值等。C語言類型描述：表(弧/邊)結(jié)點(diǎn)：typedef struct ArcNode int adjvex; / 依附于該邊的另一頂點(diǎn)(弧頭)的位置 struct ArcNode *nextarc; / 指向下一條弧的指針 InfoType *info; / 該弧相關(guān)信息的指針 ArcNode;頭結(jié)點(diǎn)：typedef struct VNode VertexType data; / 頂點(diǎn)信息 ArcNode *firstarc; / 指向第一條依附該頂點(diǎn)的弧 VNode, AdjListMAX_VERTEX_NUM

12、;adjvex nextarc info data firstarc圖的結(jié)構(gòu)定義：typedef struct AdjList vertices; int vexnum, arcnum; int kind; / 圖的種類標(biāo)志 ALGraph;0 A 1 41 B 0 4 52 C 3 53 D 2 54 E 0 15 F 1 2 3BACDFE鏈表中結(jié)點(diǎn)的個(gè)數(shù)就是該頂點(diǎn)的度數(shù)！有向圖：ABECD1 4230 120 1 2 3 4 A B C D E在有向圖的鄰接表中不易找到指向該頂點(diǎn)的弧。A B C D E 30342001234有向圖的逆鄰接表鏈表中結(jié)點(diǎn)的個(gè)數(shù)就是該頂點(diǎn)的 出度！7.2.3

13、 有向圖的十字鏈表存儲(chǔ)表示將有向圖的鄰接表和逆鄰接表結(jié)合起來的一種鏈表。從橫向上看是鄰接表，從縱向上看是逆鄰接表。ABCABC0 1 20 2 0 12 1 2 0 C語言類型描述：typedef struct ArcBox / 弧的結(jié)構(gòu)表示 int tailvex, headvex; InfoType *info; struct ArcBox *hlink, *tlink; VexNode;弧的結(jié)點(diǎn)結(jié)構(gòu)弧尾頂點(diǎn)位置 弧頭頂點(diǎn)位置 弧的相關(guān)信息指向下一個(gè)有相同弧尾的結(jié)點(diǎn)指向下一個(gè)有相同弧頭的結(jié)點(diǎn)typedef struct VexNode / 頂點(diǎn)的結(jié)構(gòu)表示 VertexType data;

14、ArcBox *firstin, *firstout; VexNode;頂點(diǎn)的結(jié)點(diǎn)結(jié)構(gòu)頂點(diǎn)信息數(shù)據(jù) 指向該頂點(diǎn)的第一條入弧指向該頂點(diǎn)的第一條出弧datafirstinfirstout有向圖的結(jié)構(gòu)表示(十字鏈表)：typedef struct VexNode xlistMAX_VERTEX_NUM; / 頂點(diǎn)結(jié)點(diǎn)(表頭向量) int vexnum, arcnum; /有向圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù) OLGraph;只要輸入n個(gè)頂點(diǎn)的信息和e條弧的信息，便可建立該有向圖的十字鏈表。Status CreateDG(OLGraph &G) /采用十字鏈表存儲(chǔ)表示，構(gòu)造有向圖G（G.kind=DG). sca

15、nf(&G.vexnum,&G.arcnum,&IncInfo); /IncInfo為0則各弧不含其它信息。 for (I=0;IG.vexnum;+I) /構(gòu)造表頭向量 scanf(&G.xlistI.data); /輸入頂點(diǎn)值 G.xlistI.firstin=NULL;G.xlistI.firstout=NULL; /初始化指針 for (k=0;kinfo); /若弧含有相關(guān)信息，則輸入特點(diǎn)：容易求得頂點(diǎn)的出度和入度。建立十字鏈表的時(shí)間復(fù)雜度和建立鄰接表是相同的。7.2.4 無向圖的鄰接多重表存儲(chǔ)表示為了便于在搜索無向圖的過程中對(duì)邊進(jìn)行操作，常采用無向圖的鄰接多重表作為存儲(chǔ)結(jié)構(gòu)。邊的結(jié)

16、點(diǎn)結(jié)構(gòu)：typedef struct Ebox VisitIf mark; / 訪問標(biāo)記 int ivex, jvex; /該邊依附的兩個(gè)頂點(diǎn)的位置 struct EBox *ilink, *jlink; InfoType *info; / 該邊信息指針 EBox;Mark ivex ilink jvex jlink info頂點(diǎn)的結(jié)構(gòu)表示：typedef struct VexBox VertexType data; EBox *firstedge; / 指向第一條依附該頂點(diǎn)的邊 VexBox;無向圖的結(jié)構(gòu)表示：typedef struct / 鄰接多重表 VexBox adjmulistMA

17、X_VERTEX_NUM; int vexnum, edgenum; AMLGraph;鄰接多重表和鄰接表的差別：同一條邊在鄰接表中用兩個(gè)結(jié)點(diǎn)表示；在鄰接多重表中只用一個(gè)結(jié)點(diǎn)。7.3 圖的遍歷從圖中某個(gè)頂點(diǎn)出發(fā)游歷圖，訪遍圖中其余頂點(diǎn)，并且使圖中的每個(gè)頂點(diǎn)僅被訪問一次的過程。7.3.1 深度優(yōu)先搜索連通圖的深度優(yōu)先搜索遍歷： 從圖中某個(gè)頂點(diǎn)v0出發(fā)，訪問此頂點(diǎn)，然后依次從v0的各個(gè)未被訪問的鄰接點(diǎn)出發(fā)深度優(yōu)先搜索遍歷圖，直至圖中所有和v0有路徑相通的頂點(diǎn)都被訪問到。以某個(gè)頂點(diǎn)的鄰接頂點(diǎn)數(shù)作為循環(huán)控制例如：W1、W2和W3均為V的鄰接點(diǎn)，SG1、SG2和 SG3分別為含頂點(diǎn)W1、W2和W3的子圖

18、。訪問頂點(diǎn) V; for (W1、W2、W3 ) 若該鄰接點(diǎn)W未被訪問， 則從它出發(fā)進(jìn)行深度 優(yōu)先搜索遍歷?？梢姡荷疃葍?yōu)先搜索遍歷連通圖的過程類似于樹的先根遍歷；如何判別V的鄰接點(diǎn)是否被訪問？ 解決的辦法是：為每個(gè)頂點(diǎn)設(shè)立一個(gè)“訪問標(biāo)志 visitedw”。Vw1SG1SG2SG3w2w3w2算法描述：void DFS(Graph G, int v) / 從頂點(diǎn)v出發(fā)，深度優(yōu)先搜索遍歷連通圖 G visitedv = TRUE; VisitFunc(v); for(w=FirstAdjVex(G, v); w!=0; w=NextAdjVex(G,v,w) if (!visitedw) DFS

19、(G, w); / 對(duì)v的尚未訪問的鄰接頂點(diǎn)w遞歸調(diào)用DFS / DFS非連通圖的深度優(yōu)先搜索遍歷： 首先，將圖中每個(gè)頂點(diǎn)的訪問標(biāo)志設(shè)為 FALSE；然后，搜索圖中每個(gè)頂點(diǎn)，如果未被訪問，則以該頂點(diǎn)為起始點(diǎn)，進(jìn)行深度優(yōu)先搜索遍歷，否則繼續(xù)檢查下一頂點(diǎn)。算法描述：void DFSTraverse(Graph G, Status (*Visit)(int v) / 對(duì)非連通圖 G 作深度優(yōu)先遍歷。 VisitFunc = Visit; for (v=0; vG.vexnum; +v) visitedv = FALSE; / 訪問標(biāo)志數(shù)組初始化 for (v=0; vw1, V-w2, V-w8 的

20、路徑長(zhǎng)度為1;V-w7, V-w3, V-w5 的路徑長(zhǎng)度為2;V-w6, V-w4 的路徑長(zhǎng)度為3。w1Vw2w7w6w3w8w5w4廣度優(yōu)先遍歷圖的實(shí)質(zhì)：通過邊或弧找鄰接點(diǎn)的過程！ 從圖中的某個(gè)頂點(diǎn)V0出發(fā)，并在訪問此頂點(diǎn)之后依次訪問V0的所有未被訪問過的鄰接點(diǎn)，之后按這些頂點(diǎn)被訪問的先后次序依次訪問它們的鄰接點(diǎn)，直至圖中所有和V0有路徑相通的頂點(diǎn)都被訪問到。算法描述：void BFSTraverse(Graph G, Status (*Visit)(int v) for (v=0; vG.vexnum; +v) visitedv = FALSE; /初始化訪問標(biāo)志 InitQueue(Q

21、); / 置空的輔助隊(duì)列Q for ( v=0; vG.vexnum; +v ) if ( !visitedv) / v 尚未訪問 . / BFSTraverse說明：使“先被訪問的頂點(diǎn)的鄰接點(diǎn)”先于“后被訪問的頂點(diǎn)的鄰接點(diǎn)”被訪問，因此，采用隊(duì)列來存放已被訪問過的頂點(diǎn)！visitedv = TRUE; Visit(v); / 訪問vEnQueue(Q, v); / v入隊(duì)列while (!QueueEmpty(Q) DeQueue(Q, u); / 隊(duì)頭元素出隊(duì)并置為u for(w=FirstAdjVex(G, u); w!=0; w=NextAdjVex(G,u,w) if ( ! vis

22、itedw) visitedw=TRUE; Visit(w); EnQueue(Q, w); / 訪問的頂點(diǎn)w入隊(duì)列 / if / while課后作業(yè)P47：7.32. 假設(shè)圖G采用鄰接表存儲(chǔ)，設(shè)計(jì)一個(gè)算法，輸出圖G中從頂點(diǎn)u到v的長(zhǎng)度為1的所有簡(jiǎn)單路徑。7.4 圖的連通性問題7.4.1 無向圖的連通分量和生成樹對(duì)非連通圖的遍歷，需從多個(gè)頂點(diǎn)出發(fā)進(jìn)行搜索。而每一次從一個(gè)新頂點(diǎn)出發(fā)搜索得到的頂點(diǎn)序列就是圖的各個(gè)連通分量中的頂點(diǎn)集。例如：非連通圖G3如下ABLMCFIDEGHJK按照P171圖7.14所示的鄰接表進(jìn)行深度優(yōu)先搜索：第一次調(diào)用DFS函數(shù)從A出發(fā)，得到序列： ALMJBFC第二次調(diào)用D

23、FS函數(shù)從D出發(fā)，得到序列： DE第三次調(diào)用DFS函數(shù)從G出發(fā)，得到序列： GKHIG3的三個(gè)連通分量：ABLMCFJIDEGHKABLMCFJIDEGHK以孩子兄弟鏈表作生成森林的存儲(chǔ)結(jié)構(gòu)，則可以形成非連通圖的生成森林。void DFSForest(MGraph g, CSTree &T)/建立無向圖G的深度優(yōu)先生成森林的(最左)孩子(右)兄弟鏈表T。T = NULL;for(v = 0; v g.vexNum; v+)visitedv = FALSE;q = T;for(v=0; v data = GetVex(g, v); /給該結(jié)點(diǎn)賦值p-firstChild = NULL;p-nex

24、tSibling = NULL;if(!p) T = p; /是第一棵生成樹的根(T的根)else q-nextSibling = p; /是其它生成樹的根(前一棵的根的“兄弟”)q = p; /q指示當(dāng)前生成樹的根DFSTree(g, v, p); /建立以p為根的生成樹void DFSTree(MGraph g, int v, CSTree *T) /從第V個(gè)頂點(diǎn)出發(fā)深度優(yōu)先遍歷圖G,建立以T為根的生成樹。visitedv = TRUE;first = TRUE; q = T;for(w = FirstAdjVex(g, v); w!=-1; w = NextAdjVex(g, v, w)

25、if(!visitedw). /* if */* for */p = (CSTree)malloc(sizeof(CSNode);p-data = GetVex(g, w);p-firstChild = NULL;p-nextSibling = NULL;if(first) /W是V的第一個(gè)未被訪問的鄰接頂點(diǎn)(*T)-firstChild = p; /是根的左孩子結(jié)點(diǎn)first = FALSE;else /W是V的其它未被訪問的鄰接頂點(diǎn) q-nextSibling = p;q = p;DFSTree(g, w, q);/從第W個(gè)頂點(diǎn)出發(fā)深度優(yōu)先遍歷圖G，建立子生成樹q。對(duì)連通圖進(jìn)行搜索時(shí)，搜索

26、過程中經(jīng)歷的所有邊和圖中所有的頂點(diǎn)構(gòu)成了連通圖的一個(gè)極小連通子圖，即連通圖的生成樹。深度優(yōu)先生成樹：廣度優(yōu)先生成樹：134251342513425生成樹的特點(diǎn)：n個(gè)頂點(diǎn)的連通子圖的生成樹是一個(gè)極小連通子圖，它包含圖中所有頂點(diǎn)和n-1條邊(但有n-1條邊的圖不一定是生成樹)。生成樹中任意兩個(gè)頂點(diǎn)間的路徑是唯一的。注：邊數(shù)n-1時(shí)，則形成環(huán)；邊數(shù)n-1時(shí)則不連通。對(duì)于非連通圖，其中的每一個(gè)連通分量都可以通過遍歷得到一棵生成樹，所有這些連通分量的生成樹就構(gòu)成了非連通圖的生成森林。7.4.2 有向圖的強(qiáng)連通分量深度優(yōu)先搜索求有向圖G的強(qiáng)連通分量步驟：在G上，從某個(gè)頂點(diǎn)出發(fā)沿以該頂點(diǎn)為尾的弧進(jìn)行深度優(yōu)先

27、搜索遍歷，并按其所有鄰接點(diǎn)的搜索都完成的順序?qū)㈨旤c(diǎn)排列起來。對(duì)DFSTraverse函數(shù)修改：在入口處加上count=0；在結(jié)束之前加上finished+count=v。在G上，從最后完成搜索的頂點(diǎn)(即finishedvexnum-1中的頂點(diǎn))出發(fā)，沿著以該頂點(diǎn)為頭的弧做逆向的深度優(yōu)先搜索遍歷，直至有向圖中所有頂點(diǎn)都被訪問為止。對(duì)DFSTraverse修改：第二個(gè)循環(huán)語句的邊界條件改為v從finishedvexnum-1至finished0。則，每一次調(diào)用DFS作逆向深度優(yōu)先遍歷所訪問到的頂點(diǎn)集就是有向圖G中一個(gè)強(qiáng)連通分量的頂點(diǎn)集。例如：V1V2V3V4V1V2V3V4010220233031

28、320123finished：13201230 1 2 323V1：v1, v3, v4V2：v27.4.3 最小生成樹問題： 假設(shè)要在 n 個(gè)城市之間建立通訊聯(lián)絡(luò)網(wǎng)，則連通 n 個(gè)城市只需要修建 n-1條線路，如何在最節(jié)省經(jīng)費(fèi)的前提下建立這個(gè)通訊網(wǎng)？該問題等價(jià)于： 構(gòu)造網(wǎng)的一棵最小生成樹，即：在e條帶權(quán)的邊中選取n-1條邊(不構(gòu)成回路)，使“權(quán)值之和”為最小。最小生成樹(MST)性質(zhì)： 假設(shè)N(V,E)是一個(gè)連通網(wǎng)，U是頂點(diǎn)集V的一個(gè)非空子集，若(u,v)是一條具有最小權(quán)值的邊，其中uU, vV-U,則必存在一棵包含邊(u,v)的最小生成樹。普里姆算法：基本思想：第一步：取圖中任意一個(gè)頂點(diǎn)

29、v 作為生成樹的根；第二步：往生成樹上添加新的頂點(diǎn)w。頂點(diǎn)w和已經(jīng)在生成樹上的頂點(diǎn)v之間必定存在一條邊，并且該邊的權(quán)值在所有連通頂點(diǎn)v和w之間的邊中取值最??；第三步：繼續(xù)往生成樹上添加頂點(diǎn)，直至生成樹上含有 n 個(gè)頂點(diǎn)為止。MST性質(zhì)例如：abcdegf195141827168213127aedcbgf148531621所得生成樹權(quán)值和= 14+8+3+5+16+21 = 67圖解構(gòu)造算法：123456123456165123456165575412345615554626515754263U=1, V-U=2, 3, 4, 5, 6U=1, 3, V-U=2, 4, 5, 6U=1, 3,

30、6, V-U=2, 4, 5123456155546212345615546212345615546212345615546233U=1, 3, 6, V-U=2, 4, 5U=1, 3, 6, 4, V-U=2, 5U=1, 3, 6, 4, 5, V-U=2U=1, 3, 6, 4, 2, V-U=5由上述圖解算法的過程知，構(gòu)造的最小生成樹不一定唯一，但最小生成樹的權(quán)值之和一定是相同的。12345615421234561542331234566515754263添加的頂點(diǎn)應(yīng)滿足下列條件：在生成樹的構(gòu)造過程中，圖中n個(gè)頂點(diǎn)分屬兩個(gè)集合：已落在生成樹上的頂點(diǎn)集 U；尚未落在生成樹上的頂點(diǎn)集V-U。應(yīng)在所有連通U中頂點(diǎn)和V-U中頂點(diǎn)的邊中選取權(quán)值最小的邊。UV-U設(shè)置一個(gè)輔助數(shù)組closedge，對(duì)當(dāng)前V-U集中的每個(gè)頂點(diǎn)，記錄和頂點(diǎn)集U中頂點(diǎn)相連接的代價(jià)最小的邊：struct VertexType adjvex; / U集中的頂點(diǎn)序號(hào) VRType l