1、7.1 抽象數(shù)據(jù)類型圖的定義抽象數(shù)據(jù)類型圖的定義7.2 圖的存儲(chǔ)表示圖的存儲(chǔ)表示7.3 圖的遍歷圖的遍歷7.4 最小生成樹最小生成樹7.5 重（雙）連通圖和關(guān)節(jié)點(diǎn)重（雙）連通圖和關(guān)節(jié)點(diǎn)7.6 兩點(diǎn)之間的最短路徑問(wèn)題兩點(diǎn)之間的最短路徑問(wèn)題7.7 拓?fù)渑判蛲負(fù)渑判?.8 關(guān)鍵路徑關(guān)鍵路徑 圖圖是由一個(gè)是由一個(gè)頂點(diǎn)集頂點(diǎn)集 V 和一個(gè)和一個(gè)弧集弧集 R構(gòu)成構(gòu)成的數(shù)據(jù)結(jié)構(gòu)。的數(shù)據(jù)結(jié)構(gòu)。 Graph = (V, R )其中，VR| v,wV 且 P(v,w) 表示從 v 到 w 的一條弧，并稱 v 為弧頭弧頭，w 為弧尾弧尾。 謂詞 P(v,w) 定義了弧 的意義或信息。圖的結(jié)構(gòu)定義圖的結(jié)構(gòu)定義: 由于

2、“弧”是有方向的，因此稱由頂點(diǎn)集和弧集構(gòu)成的圖為有向圖有向圖。EACBD例如例如: :G1 = (V1, VR1)其中V1=A, B, C, D, EVR1=, , , , , , 若VR 必有VR, 則稱 (v,w) 為頂點(diǎn) v 和頂點(diǎn) w 之間存在一條邊邊。BCAFED由頂點(diǎn)集和邊集構(gòu)成的圖稱作無(wú)向圖無(wú)向圖。例如: G2=(V2,VR2)V2=A, B, C, D, E, FVR2=(A, B), (A, E), (B, E), (C, D), (D, F), (B, F), (C, F) 名詞和術(shù)語(yǔ)名詞和術(shù)語(yǔ)網(wǎng)、子圖 完全圖、稀疏圖、稠密圖鄰接點(diǎn)、度、入度、出度路徑、路徑長(zhǎng)度、簡(jiǎn)單路徑、

3、簡(jiǎn)單回路連通圖、連通分量、強(qiáng)連通圖、強(qiáng)連通分量生成樹、生成森林ABECFAEABBC設(shè)圖G=(V,VR) 和圖 G=(V,VR),且 VV, VRVR,則稱 G 為 G 的子圖子圖。1597211132 弧或邊帶權(quán)的圖分別稱作有向網(wǎng)有向網(wǎng)或無(wú)向網(wǎng)無(wú)向網(wǎng)。假設(shè)圖中有 n 個(gè)頂點(diǎn)，e 條邊，則 含有 e=n(n-1)/2 條邊的無(wú)向圖稱作完全圖完全圖; 含有 e=n(n-1) 條弧的有向圖稱作 有向完全圖有向完全圖; 若邊或弧的個(gè)數(shù) enlogn，則稱作稀疏圖稀疏圖，否則稱作稠密圖稠密圖。 假若頂點(diǎn)v 和頂點(diǎn)w 之間存在一條邊，則稱頂點(diǎn)v 和w 互為鄰接點(diǎn)鄰接點(diǎn)，例如例如: :ID(B) = 3I

4、D(A) = 2 邊(v,w) 和頂點(diǎn)v 和w 相關(guān)聯(lián)關(guān)聯(lián)。 和頂點(diǎn)v 關(guān)聯(lián)的邊的數(shù)目邊的數(shù)目定義為邊的度度。ACDFEB右側(cè)圖中頂點(diǎn)的出度出度: : 以頂點(diǎn)v 為弧尾的弧的數(shù)目;ABECF對(duì)有向圖來(lái)說(shuō)對(duì)有向圖來(lái)說(shuō)，頂點(diǎn)的入度入度: : 以頂點(diǎn)v為弧頭的弧的數(shù)目。頂點(diǎn)的度度( (TD)=)=出度出度( (OD)+)+入度入度( (ID) )例如例如: :ID(B) = 2OD(B) = 1TD(B) = 3由于弧有方向性，則有入度入度和出度出度之分設(shè)圖G=(V,VR)中的一個(gè)頂點(diǎn)序列 u=vi,0,vi,1, , vi,m=w中，(vi,j-1,vi,j)VR 1jm,則稱從頂點(diǎn)u 到頂點(diǎn)w

5、之間存在一條路徑路徑。路徑上邊的數(shù)目稱作路徑長(zhǎng)度路徑長(zhǎng)度。ABECF如如: :從A到F長(zhǎng)度為 3 的路徑A,B,C,F簡(jiǎn)單路徑簡(jiǎn)單路徑:指序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑。簡(jiǎn)單回路簡(jiǎn)單回路:指序列中第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑。若圖G中任意兩個(gè)頂點(diǎn)之間都有路徑相通，則稱此圖為連通圖連通圖;若無(wú)向圖為非連通圖，則圖中各個(gè)極大連通子圖稱作此圖的連通連通分量分量。BACDFEBACDFE 若任意兩個(gè)頂點(diǎn)之間都存在一條有向路徑，則稱此有向圖為強(qiáng)連通強(qiáng)連通。ABECFABECF對(duì)有向，對(duì)有向，否則，其各個(gè)強(qiáng)連通子圖稱作它的強(qiáng)連通分量強(qiáng)連通分量。 假設(shè)一個(gè)連通圖有 n 個(gè)頂點(diǎn)和 e 條邊，其中 n-1 條

6、邊和 n 個(gè)頂點(diǎn)構(gòu)成一個(gè)極小連通子圖，稱該極小連通子圖為此連通圖的生成樹生成樹。對(duì)非連通圖，則稱由各個(gè)連通分量的生成樹的集合為此非連通圖的生成森林生成森林。BACDFE結(jié)構(gòu)的建立和銷毀結(jié)構(gòu)的建立和銷毀插入或刪除頂點(diǎn)插入或刪除頂點(diǎn)對(duì)鄰接點(diǎn)的操作對(duì)鄰接點(diǎn)的操作對(duì)頂點(diǎn)的訪問(wèn)操作對(duì)頂點(diǎn)的訪問(wèn)操作遍歷遍歷插入和刪除弧插入和刪除弧基本操作基本操作CreatGraph(&G, V, VR): / 按定義(V, VR) 構(gòu)造圖DestroyGraph(&G): / 銷毀圖結(jié)構(gòu)的建立和銷毀結(jié)構(gòu)的建立和銷毀對(duì)頂點(diǎn)的訪問(wèn)操作對(duì)頂點(diǎn)的訪問(wèn)操作LocateVex(G, u); / 若G中存在頂點(diǎn)u，則返回該頂點(diǎn)在 /

7、圖中“位置位置” ；否則返回其它信。GetVex(G, v); / 返回 v 的值。PutVex(&G, v, value); / 對(duì) v 賦值value。對(duì)鄰接點(diǎn)的操作對(duì)鄰接點(diǎn)的操作FirstAdjVex(G, v); / 返回 v 的“第一個(gè)鄰接點(diǎn)第一個(gè)鄰接點(diǎn)” 。若該頂點(diǎn)/在 G 中沒(méi)有鄰接點(diǎn)，則返回“空”。NextAdjVex(G, v, w); / 返回 v 的（相對(duì)于 w 的） “下一個(gè)鄰接下一個(gè)鄰接/ 點(diǎn)點(diǎn)”。若 w 是 v 的最后一個(gè)鄰接點(diǎn)，則/ 返回“空”。插入或刪除頂點(diǎn)插入或刪除頂點(diǎn)InsertVex(&G, v); /在圖G中增添新頂點(diǎn)v。DeleteVex(&G, v)

8、; / 刪除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)先深度優(yōu)先遍歷圖G，并對(duì)每/個(gè)頂點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。BFSTraverse(G, v, Visit(); /從頂點(diǎn)v起廣度優(yōu)先廣度優(yōu)先遍歷圖G，并對(duì)每/個(gè)頂點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。7.2 圖的存儲(chǔ)表示圖的存儲(chǔ)表示一、一、圖的數(shù)組(鄰接矩陣)存儲(chǔ)表示

9、二、圖的鄰接表存儲(chǔ)表示三、有向圖的十字鏈表存儲(chǔ)表示 四、無(wú)向圖的鄰接多重表存儲(chǔ)表示Aij=0 (i,j)VR1 (i,j)VR一、一、圖的數(shù)組(鄰接矩陣)存儲(chǔ)表示BACDFE定義定義:矩陣的元素為矩陣的元素為010010100010000101001001110000011100有向圖的鄰接矩陣有向圖的鄰接矩陣為非對(duì)稱矩陣為非對(duì)稱矩陣ABECF0 1 0 0 10 0 1 0 00 0 0 1 01 1 0 0 00 0 1 0 0typedef struct ArcCell / 弧的定義弧的定義 VRType adj; / VRType是頂點(diǎn)關(guān)系類型。 / 對(duì)無(wú)權(quán)圖，用1或0表示相鄰否； /

10、 對(duì)帶權(quán)圖，則為權(quán)值類型。 InfoType *info; / 該弧相關(guān)信息的指針 ArcCell, AdjMatrixMAX_VERTEX_NUM MAX_VERTEX_NUM;typedef struct / 圖的定義圖的定義 VertexType / 頂點(diǎn)信息 vexsMAX_VERTEX_NUM; AdjMatrix arcs; / 弧的信息 int vexnum, arcnum; / 頂點(diǎn)數(shù)，弧數(shù) GraphKind kind; / 圖的種類標(biāo)志 MGraph;DBACFE二、圖的鄰接表二、圖的鄰接表 存儲(chǔ)表示存儲(chǔ)表示 A 1 4 B 0 4 5 C 3 5 D 2 5 E 0 1

11、F 1 2 30 1 2 3 4 5有向圖的鄰接表有向圖的鄰接表1 4230 120 1 2 3 4 A B C D EABECF可見，在有向圖的鄰接表中不易找到指向該頂點(diǎn)的弧ABECD有向圖的逆鄰接表有向圖的逆鄰接表A B C D E 303420 01234在有向圖的鄰接表中，對(duì)每個(gè)頂點(diǎn)，鏈接的是指向該頂點(diǎn)的弧typedef struct ArcNode int adjvex; / 該弧所指向的頂點(diǎn)的位置 struct ArcNode *nextarc; / 指向下一條弧的指針 InfoType *info; / 該弧相關(guān)信息的指針 ArcNode;adjvex nextarc info弧

12、的結(jié)點(diǎn)結(jié)構(gòu)弧的結(jié)點(diǎn)結(jié)構(gòu)typedef struct VNode VertexType data; / 頂點(diǎn)信息 ArcNode *firstarc; / 指向第一條依附該頂點(diǎn)的弧 VNode, AdjListMAX_VERTEX_NUM; data firstarc頂點(diǎn)的結(jié)點(diǎn)結(jié)構(gòu)頂點(diǎn)的結(jié)點(diǎn)結(jié)構(gòu)typedef struct AdjList vertices; int vexnum, arcnum; int kind; / 圖的種類標(biāo)志 ALGraph;圖的結(jié)構(gòu)定義圖的結(jié)構(gòu)定義(鄰接表)三、有向圖的十字鏈表存儲(chǔ)表示三、有向圖的十字鏈表存儲(chǔ)表示 ABCABC0 1 20 2 0 12 1 2 0 弧

13、的結(jié)點(diǎn)結(jié)構(gòu)弧的結(jié)點(diǎn)結(jié)構(gòu)弧尾頂點(diǎn)位置 弧頭頂點(diǎn)位置 弧的相關(guān)信息指向下一個(gè)有相同弧尾有相同弧尾的結(jié)點(diǎn)指向下一個(gè)有相同弧頭有相同弧頭的結(jié)點(diǎn)typedef struct ArcBox / 弧弧的結(jié)構(gòu)表示的結(jié)構(gòu)表示 int tailvex, headvex; InfoType *info; struct ArcBox *hlink, *tlink; VexNode;tailvexheadvexhlink tlinkinfo頂點(diǎn)的結(jié)點(diǎn)結(jié)構(gòu)頂點(diǎn)的結(jié)點(diǎn)結(jié)構(gòu)頂點(diǎn)信息數(shù)據(jù) 指向該頂點(diǎn)的第一條入弧第一條入弧指向該頂點(diǎn)的第一條出弧第一條出弧typedef struct VexNode / 頂點(diǎn)的結(jié)構(gòu)表示頂點(diǎn)的結(jié)構(gòu)表

14、示 VertexType data; ArcBox *firstin, *firstout; VexNode;datafirstinfirstouttypedef struct VexNode xlistMAX_VERTEX_NUM; / 頂點(diǎn)結(jié)點(diǎn)(表頭向量) int vexnum, arcnum; /有向圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù) OLGraph;有向圖的結(jié)構(gòu)表示有向圖的結(jié)構(gòu)表示(十字鏈表十字鏈表)四、無(wú)向圖的鄰接多重表存儲(chǔ)表示typedef struct Ebox VisitIf mark; / 訪問(wèn)標(biāo)記 int ivex, jvex; /該邊依附的兩個(gè)頂點(diǎn)的位置 struct EBox *il

15、ink, *jlink; InfoType *info; / 該邊信息指針 EBox;邊的結(jié)構(gòu)表示邊的結(jié)構(gòu)表示typedef struct / 鄰接多重表鄰接多重表 VexBox adjmulistMAX_VERTEX_NUM; int vexnum, edgenum; AMLGraph;頂點(diǎn)的結(jié)構(gòu)表示頂點(diǎn)的結(jié)構(gòu)表示typedef struct VexBox VertexType data; EBox *firstedge; / 指向第一條依附該頂點(diǎn)的邊 VexBox;無(wú)向圖的結(jié)構(gòu)表示無(wú)向圖的結(jié)構(gòu)表示7.3 圖的遍歷圖的遍歷 從圖中某個(gè)頂點(diǎn)出發(fā)游歷圖，訪遍圖中其余頂點(diǎn)，并且使圖中的每個(gè)頂點(diǎn)僅被

16、訪問(wèn)一次的過(guò)程。深度優(yōu)先搜索深度優(yōu)先搜索廣度優(yōu)先搜索廣度優(yōu)先搜索遍歷應(yīng)用舉例遍歷應(yīng)用舉例 從圖中某個(gè)頂點(diǎn)頂點(diǎn)V0 出發(fā)，訪問(wèn)此頂點(diǎn)，然后依次從依次從V0的的各個(gè)未被訪問(wèn)的各個(gè)未被訪問(wèn)的鄰鄰接點(diǎn)出發(fā)深度優(yōu)先搜索遍歷圖接點(diǎn)出發(fā)深度優(yōu)先搜索遍歷圖，直至圖中所有和V0有路徑相通的頂點(diǎn)都被訪問(wèn)到。一、深度優(yōu)先搜索遍歷圖一、深度優(yōu)先搜索遍歷圖連通圖的深度優(yōu)先搜索遍歷連通圖的深度優(yōu)先搜索遍歷SG1SG2SG3W1、W2和W3 均為 V 的鄰接點(diǎn)，SG1、SG2 和 SG3 分別為含頂點(diǎn)W1、W2和W3 的子圖。訪問(wèn)頂點(diǎn) V ;for (W1、W2、W3 ) 若該鄰接點(diǎn)W未被訪問(wèn)， 則從它出發(fā)進(jìn)行深度優(yōu)先搜索

17、遍歷。Vw1w3w2從上頁(yè)的圖解可見從上頁(yè)的圖解可見:1. 從深度優(yōu)先搜索遍歷連通圖的過(guò)程類似于樹的先根遍歷;解決的辦法是:為每個(gè)頂點(diǎn)設(shè)立一個(gè) “訪問(wèn)標(biāo)志 visitedw”;2. 如何判別V的鄰接點(diǎn)是否被訪問(wèn)？void DFS(Graph G, int v) / 從頂點(diǎn)從頂點(diǎn)v出發(fā)，出發(fā)，深度優(yōu)先搜索遍歷連通圖深度優(yōu)先搜索遍歷連通圖 G visitedv = TRUE; VisitFunc(v); for(w=FirstAdjVex(G, v); w!=0; w=NextAdjVex(G,v,w) if (!visitedw) DFS(G, w); / 對(duì)v的尚未訪問(wèn)的鄰接頂點(diǎn)w / 遞歸調(diào)

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

19、V-w3, V-w5 的路徑長(zhǎng)度為2;V-w6, V-w4 的路徑長(zhǎng)度為3。w1Vw2w7w6w3w8w5w4 從圖中的某個(gè)頂點(diǎn)V0出發(fā)，并在訪問(wèn)此頂點(diǎn)之后依次訪問(wèn)V0的所有未被訪問(wèn)未被訪問(wèn)過(guò)的鄰接點(diǎn)，之后按這些頂點(diǎn)被訪問(wèn)的先后次按這些頂點(diǎn)被訪問(wèn)的先后次序依次訪問(wèn)它們的鄰接點(diǎn)序依次訪問(wèn)它們的鄰接點(diǎn)，直至圖中所有和V0有路徑相通的頂點(diǎn)都被訪問(wèn)到。 若此時(shí)圖中尚有頂點(diǎn)未被訪問(wèn),則另選圖中一個(gè)未曾被訪問(wèn)的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪問(wèn)到為止。 void BFSTraverse(Graph G, Status (*Visit)(int v) for (v=0; vG.vexnum

20、; +v) visitedv = FALSE; /初始化訪問(wèn)標(biāo)志 InitQueue(Q); / 置空的輔助隊(duì)列Q for ( v=0; vnext = Q.rear-next = NULL;void EnQueue( LinkQueue& Q, QelemType e ) p = new QNode; p-data = e; p-next = NULL; p-priou = Q.front; Q.rear-next = p; Q.rear = p;void DeQueue( LinkQueue& Q, QelemType& e ) Q.front = Q.front-next; e = Q.

21、front-data7.4 (連通網(wǎng)的連通網(wǎng)的)最小生成樹最小生成樹 假設(shè)要在 n 個(gè)城市之間建立通訊聯(lián)絡(luò)網(wǎng)，則連通 n 個(gè)城市只需要修建 n-1條線路，如何在最節(jié)省經(jīng)費(fèi)的前如何在最節(jié)省經(jīng)費(fèi)的前提下建立提下建立這個(gè)通訊網(wǎng)通訊網(wǎng)？問(wèn)題：?jiǎn)栴}： 構(gòu)造網(wǎng)的一棵最小生成樹，即： 在 e 條帶權(quán)的邊中選取 n-1 條邊（不構(gòu)成回路），使“權(quán)值之和權(quán)值之和”為最小。算法二：（克魯斯卡爾算法）算法二：（克魯斯卡爾算法）該問(wèn)題等價(jià)于：該問(wèn)題等價(jià)于：算法一：（普里姆算法）算法一：（普里姆算法） 取圖中任意一個(gè)頂點(diǎn) v 作為生成樹的根，之后往生成樹上添加新的頂點(diǎn) w。在添加在添加的頂點(diǎn)的頂點(diǎn) w 和已經(jīng)在生成樹上

22、的頂點(diǎn)和已經(jīng)在生成樹上的頂點(diǎn)v 之間之間必定存在一條邊，并且該邊的權(quán)值在所有必定存在一條邊，并且該邊的權(quán)值在所有連通頂點(diǎn)連通頂點(diǎn) v 和和 w 之間的邊中取值最小之間的邊中取值最小。之后繼續(xù)往生成樹上添加頂點(diǎn)，直至生成樹上含有 n-1 個(gè)頂點(diǎn)為止。普里姆算法的基本思想普里姆算法的基本思想:abcdegf195141827168213127例如例如: :aedcbgf148531621所得生成樹權(quán)值和 = 14+8+3+5+16+21 = 67 在生成樹的構(gòu)造過(guò)程中，圖中 n 個(gè)頂點(diǎn)分屬兩個(gè)集合：已落在生成樹上的頂點(diǎn)集 U 和尚未落在生成樹上的頂點(diǎn)集V-U ，則應(yīng)在所有連通在所有連通U中頂點(diǎn)和中

23、頂點(diǎn)和V-U中中頂點(diǎn)的邊中選取權(quán)值最小的邊頂點(diǎn)的邊中選取權(quán)值最小的邊。 一般情況下所添加的頂點(diǎn)應(yīng)滿足下列條件:UV-U 設(shè)置一個(gè)輔助數(shù)組，對(duì)當(dāng)前設(shè)置一個(gè)輔助數(shù)組，對(duì)當(dāng)前VU集集中的每個(gè)頂點(diǎn)，記錄和頂點(diǎn)集中的每個(gè)頂點(diǎn)，記錄和頂點(diǎn)集U中頂點(diǎn)中頂點(diǎn)相連接的代價(jià)最小的邊：相連接的代價(jià)最小的邊：struct VertexType adjvex; / U集中的頂點(diǎn)序號(hào) VRType lowcost; / 邊的權(quán)值 closedgeMAX_VERTEX_NUM;abcdegf195141827168213127closedge0123456AdjvexLowcostaedcbaaa19141814例如例如:

24、e12ee8168d3dd7213c5 5 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 27void MiniSpanTree_P(MGraph G, VertexType u) /用普里姆算法從頂點(diǎn)u出發(fā)構(gòu)造網(wǎng)G的最小生成樹 k = LocateVex ( G, u ); for ( j=0; jG.vexnum; +j ) / 輔助數(shù)組初始化 if (j!=k) closedgej = u, G.arcskj.adj ; closedgek.lowco

25、st = 0; / 初始，Uu for (i=0; iG.vexnum; +i) 繼續(xù)向生成樹上添加頂點(diǎn)繼續(xù)向生成樹上添加頂點(diǎn); k = minimum(closedge); / 求出加入生成樹的下一個(gè)頂點(diǎn)(k) printf(closedgek.adjvex, G.vexsk); / 輸出生成樹上一條邊 closedgek.lowcost = 0; / 第k頂點(diǎn)并入U(xiǎn)集 for (j=0; jG.vexnum; +j) /修改其它頂點(diǎn)的最小邊 if (G.arcskj.adj closedgej.lowcost) closedgej = G.vexsk, G.arcskj.adj ; 具體做

26、法具體做法: 先構(gòu)造一個(gè)只含 n 個(gè)頂點(diǎn)的子圖 SG，然后從權(quán)值最小的邊開始，若它的添加不使SG 中產(chǎn)生回路，則在 SG 上加上這條邊，如此重復(fù)，直至加上 n-1 條邊為止。考慮問(wèn)題的出發(fā)點(diǎn)考慮問(wèn)題的出發(fā)點(diǎn): 為使生成樹上邊的權(quán)值之和達(dá)到最小，則應(yīng)使生成樹中每一條邊的權(quán)值盡可能地小。克魯斯卡爾算法的基本思想：克魯斯卡爾算法的基本思想：abcdegf195141827168213127aedcbgf148531621例如例如: :7121819算法描述算法描述:構(gòu)造非連通圖 ST=( V, ); k = i = 0; / k 計(jì)選中的邊數(shù) while (kadjvex; DFSArticul(G

27、, v); / 從第v頂點(diǎn)出發(fā)深度優(yōu)先搜索 if (count nextarc) void DFSArticul(ALGraph G, int v0) / 從第v0個(gè)頂點(diǎn)出發(fā)深度優(yōu)先遍歷圖 G, / 查找并輸出關(guān)節(jié)點(diǎn) / DFSArticulmin =visitedv0 = +count; / v0是第是第count個(gè)訪問(wèn)的頂點(diǎn)個(gè)訪問(wèn)的頂點(diǎn), 并設(shè)并設(shè)lowv0的初值為的初值為min / 檢查v0的每個(gè)鄰接點(diǎn)lowv0 = min; w = p-adjvex; / w為v0的鄰接頂點(diǎn) if (visitedw = 0) / w未曾被訪問(wèn) DFSArticul(G, w); / 返回前求得low

28、w else / w是回邊上的頂點(diǎn)if (loww =visitedv0) printf(v0, G.verticesv0.data); /輸出關(guān)節(jié)點(diǎn)輸出關(guān)節(jié)點(diǎn)if (visitedw min) min = visitedw;7.6 兩點(diǎn)之間的兩點(diǎn)之間的 最短路徑問(wèn)題最短路徑問(wèn)題 求從某個(gè)源點(diǎn)到其余各點(diǎn)的求從某個(gè)源點(diǎn)到其余各點(diǎn)的最短路徑最短路徑 每一對(duì)頂點(diǎn)之間的最短路徑每一對(duì)頂點(diǎn)之間的最短路徑 求求從源點(diǎn)到其余各點(diǎn)的最短路徑從源點(diǎn)到其余各點(diǎn)的最短路徑的算法的基本思想的算法的基本思想: 依依最短路徑的長(zhǎng)度最短路徑的長(zhǎng)度遞增的次序求得遞增的次序求得各條路徑各條路徑源點(diǎn)源點(diǎn)v1其中，從源點(diǎn)到從源點(diǎn)到

29、頂點(diǎn)頂點(diǎn)v的最短路徑的最短路徑是所有最短路徑中長(zhǎng)度最短者。v2 在這條路徑上，必定只含一條弧，并且這條弧的權(quán)值最小。 下一條路徑長(zhǎng)度次短的最短路徑最短路徑的特點(diǎn):路徑長(zhǎng)度最短的最短路徑最短路徑的特點(diǎn): 它只可能有兩種情況:或者是直接從源點(diǎn)到該點(diǎn)(只含一條弧)； 或者是，從源點(diǎn)經(jīng)過(guò)頂點(diǎn)v1，再到達(dá)該頂點(diǎn)(由兩條弧組成)。其余最短路徑的特點(diǎn)：再下一條路徑長(zhǎng)度次短的最短路徑最短路徑的特點(diǎn): 它可能有三種情況：或者是，直接從源點(diǎn)到該點(diǎn)(只含一條弧)； 或者是，從源點(diǎn)經(jīng)過(guò)頂點(diǎn)v1，再到達(dá)該頂點(diǎn)(由兩條弧組成)；或者是，從源點(diǎn)經(jīng)過(guò)頂點(diǎn)v2，再到達(dá)該頂點(diǎn)。 它或者是直接從源點(diǎn)到該點(diǎn)(只含一條弧)； 或者是，

30、從源點(diǎn)經(jīng)過(guò)已求得最短路徑的頂點(diǎn)，再到達(dá)該頂點(diǎn)。求最短路徑的迪杰斯特拉算法：一般情況下，Distk = 或者 = + 設(shè)置輔助數(shù)組Dist，其中每個(gè)分量Distk 表示 當(dāng)前所求得的從源點(diǎn)到其余各頂點(diǎn) k 的最短路徑。1）在所有從源點(diǎn)出發(fā)的弧中選取一條權(quán)值最小的弧，即為第一條最短路徑。2）修改其它各頂點(diǎn)的Distk值。假設(shè)求得最短路徑的頂點(diǎn)為u，若若 Distu+G.arcsukDistk則將 Distk 改為 Distu+G.arcsukINFINITYkvarcsGkDist0.V0和k之間存在弧V0和k之間不存在弧其中的最小值即為最短路徑的長(zhǎng)度其中的最小值即為最短路徑的長(zhǎng)度。求每一對(duì)頂點(diǎn)之

31、間的最短路徑弗洛伊德算法的基本思想是： 從 vi 到 vj 的所有可能存在的路徑中，選出一條長(zhǎng)度最短的路徑若存在，則存在路徑vi,vj / 路徑中不含其它頂點(diǎn)若,存在，則存在路徑vi,v1,vj / 路徑中所含頂點(diǎn)序號(hào)不大于1若vi,v2, v2,vj存在， 則存在一條路徑vi, , v2, vj / 路徑中所含頂點(diǎn)序號(hào)不大于2 依次類推，則 vi 至 vj 的最短路徑應(yīng)是上述這些路徑中，路徑長(zhǎng)度最小者。7.7 拓?fù)渑判蛲負(fù)渑判?問(wèn)題問(wèn)題: 假設(shè)以有向圖表示一個(gè)工程的施工圖或程序的數(shù)據(jù)流圖，則圖中不允許出現(xiàn)回路。 檢查有向圖中是否存在回路的方法之一，是對(duì)有向圖進(jìn)行拓?fù)渑判蛲負(fù)渑判颉：沃^何謂“拓

32、撲排序拓?fù)渑判颉保繉?duì)有向圖進(jìn)行如下操作: 按照有向圖給出的次序關(guān)系，將圖中頂點(diǎn)排成一個(gè)線性序列，對(duì)于有向圖中沒(méi)有限定次序關(guān)系的頂點(diǎn)，則可以人為加上任意的次序關(guān)系。例如：對(duì)于下列有向圖BDAC可求得拓?fù)溆行蛐蛄校?A B C D 或 A C B D由此所得頂點(diǎn)的線性序列稱之為拓?fù)溆行蛐蛄蠦DAC反之，對(duì)于下列有向圖不能求得它的拓?fù)溆行蛐蛄小Ｒ驗(yàn)閳D中存在一個(gè)回路 B, C, D如何進(jìn)行拓?fù)渑判颍咳绾芜M(jìn)行拓?fù)渑判颍恳弧挠邢驁D中選取一個(gè)沒(méi)有前驅(qū)沒(méi)有前驅(qū) 的頂點(diǎn)，并輸出之; 重復(fù)上述兩步，直至圖空，或者圖不空但找不到無(wú)前驅(qū)的頂點(diǎn)為止。二、從有向圖中刪去此頂點(diǎn)以及所刪去此頂點(diǎn)以及所 有以它為尾的弧有以它

33、為尾的弧;abcghdfeabhcdgfe在算法中需要用定量的描述替代定性的概念在算法中需要用定量的描述替代定性的概念 沒(méi)有前驅(qū)的頂點(diǎn)沒(méi)有前驅(qū)的頂點(diǎn) 入度為零的頂點(diǎn)入度為零的頂點(diǎn)刪除頂點(diǎn)及以它為尾的弧刪除頂點(diǎn)及以它為尾的弧 弧頭頂點(diǎn)的入度減弧頭頂點(diǎn)的入度減1取入度為零的頂點(diǎn)v;while (v0) printf(v); +m; w:=FirstAdj(v); while (w0) inDegreew-; w:=nextAdj(v,w); 取下一個(gè)入度為零的頂點(diǎn)v;if mn printf(“圖中有回路”);算法描述算法描述 為避免每次都要搜索入度為零的頂點(diǎn)，在算法中設(shè)置一個(gè)“棧棧”，以保存“入

34、度為零”的頂點(diǎn)。CountInDegree(G,indegree); /對(duì)各頂點(diǎn)求入度InitStack(S);for ( i=0; iG.vexnum; +i) if (!indegreei) Push(S, i); /入度為零的頂點(diǎn)入棧count=0; /對(duì)輸出頂點(diǎn)計(jì)數(shù)while (!EmptyStack(S) Pop(S, v); +count; printf(v); for (w=FirstAdj(v); w; w=NextAdj(G,v,w) -indegree(w); / 弧頭頂點(diǎn)的入度減一 if (!indegreew) Push(S, w); /新產(chǎn)生的入度為零的頂點(diǎn)入棧 if (countG.vexnum) printf(“圖中有回路”)7.8 關(guān)鍵路徑關(guān)鍵路徑問(wèn)題問(wèn)題: 假設(shè)以有向網(wǎng)表示一個(gè)施工流圖，弧上的權(quán)值表示完成該項(xiàng)子工程所需時(shí)間。問(wèn)：哪些子工程項(xiàng)是“關(guān)鍵工程”？即：哪些子工程項(xiàng)將影響整個(gè)工程的完成期限的。整個(gè)工程完成的時(shí)間為：從有向圖的源點(diǎn)源點(diǎn)到匯點(diǎn)匯點(diǎn)的最長(zhǎng)路徑。abcdefghk64521187244例如例如: :“關(guān)鍵活動(dòng)”指的是：該弧上的權(quán)值增加權(quán)值增加 將使有向圖上的