《數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏第7章PPT課件》由會(huì)員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏第7章PPT課件（114頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、2021/6/71第七章第七章圖圖2021/6/72【課前思考】【課前思考】1.同學(xué)們有沒(méi)有發(fā)現(xiàn)現(xiàn)在的十字路口的交通燈已從過(guò)去的一對(duì)改為三對(duì)，同學(xué)們有沒(méi)有發(fā)現(xiàn)現(xiàn)在的十字路口的交通燈已從過(guò)去的一對(duì)改為三對(duì)，即每個(gè)方向的直行、左拐和右拐能否通行都有相應(yīng)的交通燈指明。你能否即每個(gè)方向的直行、左拐和右拐能否通行都有相應(yīng)的交通燈指明。你能否對(duì)某個(gè)丁字路口的對(duì)某個(gè)丁字路口的6條通路畫(huà)出和第一章緒論中介紹的條通路畫(huà)出和第一章緒論中介紹的五叉路口交通管理五叉路口交通管理示意圖示意圖相類(lèi)似的圖？相類(lèi)似的圖？同學(xué)們一定可以畫(huà)出如下所示類(lèi)似的圖形。2.如果每次讓三條路同時(shí)通行，那么從圖看出哪些路可以同時(shí)通行？如果每

2、次讓三條路同時(shí)通行，那么從圖看出哪些路可以同時(shí)通行？同時(shí)可通行的路為：(AB,BC,CA),(AB,BC,BA),(AB,AC,CA),(CB,CA,BC)2021/6/73【學(xué)習(xí)目標(biāo)】【學(xué)習(xí)目標(biāo)】1領(lǐng)會(huì)圖的類(lèi)型定義。2熟悉圖的各種存儲(chǔ)結(jié)構(gòu)及其構(gòu)造算法，了解各種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)及其選用原則。3熟練掌握?qǐng)D的兩種遍歷算法。4理解各種圖的應(yīng)用問(wèn)題的算法。2021/6/74【重點(diǎn)和難點(diǎn)】【重點(diǎn)和難點(diǎn)】圖的應(yīng)用極為廣泛，而且圖的各種應(yīng)用問(wèn)題的算法都比較經(jīng)典，因此本章重點(diǎn)在于理解各種圖的算法及其應(yīng)用場(chǎng)合?！局R(shí)點(diǎn)】【知識(shí)點(diǎn)】圖的類(lèi)型定義、圖的存儲(chǔ)表示、圖的深度優(yōu)先搜索遍歷和圖的廣度優(yōu)先搜索遍歷、無(wú)向網(wǎng)的最小

3、生成樹(shù)、最短路徑、拓?fù)渑判?、關(guān)鍵路徑。2021/6/75【學(xué)習(xí)指南】【學(xué)習(xí)指南】離散數(shù)學(xué)中的圖論是專(zhuān)門(mén)研究圖性質(zhì)的一個(gè)數(shù)學(xué)分離散數(shù)學(xué)中的圖論是專(zhuān)門(mén)研究圖性質(zhì)的一個(gè)數(shù)學(xué)分支，但圖論注重研究圖的純數(shù)學(xué)性質(zhì)，而數(shù)據(jù)結(jié)構(gòu)中對(duì)支，但圖論注重研究圖的純數(shù)學(xué)性質(zhì)，而數(shù)據(jù)結(jié)構(gòu)中對(duì)圖的討論則側(cè)重于在計(jì)算機(jī)中如何表示圖以及如何實(shí)現(xiàn)圖的討論則側(cè)重于在計(jì)算機(jī)中如何表示圖以及如何實(shí)現(xiàn)圖的操作和應(yīng)用等。圖是較線性表和樹(shù)更為復(fù)雜的數(shù)據(jù)圖的操作和應(yīng)用等。圖是較線性表和樹(shù)更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，因此和線性表、樹(shù)不同，雖然在遍歷圖的同時(shí)可結(jié)構(gòu)，因此和線性表、樹(shù)不同，雖然在遍歷圖的同時(shí)可以對(duì)頂點(diǎn)或弧進(jìn)行各種操作，但更多圖的應(yīng)用問(wèn)題如求

4、以對(duì)頂點(diǎn)或弧進(jìn)行各種操作，但更多圖的應(yīng)用問(wèn)題如求最小生成樹(shù)和最短路徑等在圖論的研究中都早已有了特最小生成樹(shù)和最短路徑等在圖論的研究中都早已有了特定算法，在本章中主要是介紹它們?cè)谟?jì)算機(jī)中的具體實(shí)定算法，在本章中主要是介紹它們?cè)谟?jì)算機(jī)中的具體實(shí)現(xiàn)。這些算法乍一看都比較難，應(yīng)多對(duì)照具體圖例的存現(xiàn)。這些算法乍一看都比較難，應(yīng)多對(duì)照具體圖例的存儲(chǔ)結(jié)構(gòu)進(jìn)行學(xué)習(xí)。而圖遍歷的兩種搜索路徑和樹(shù)遍歷的儲(chǔ)結(jié)構(gòu)進(jìn)行學(xué)習(xí)。而圖遍歷的兩種搜索路徑和樹(shù)遍歷的兩種搜索路徑極為相似，應(yīng)將兩者的算法對(duì)照學(xué)習(xí)以便兩種搜索路徑極為相似，應(yīng)將兩者的算法對(duì)照學(xué)習(xí)以便提高學(xué)習(xí)的效果。提高學(xué)習(xí)的效果。本章必須完成的算法設(shè)計(jì)題為本章必須完成的

5、算法設(shè)計(jì)題為:7.7,7.9,7.10,7.12,7.14,7.15,7.222021/6/767.1 圖的定義與術(shù)語(yǔ)圖的定義與術(shù)語(yǔ)7.2 圖的存儲(chǔ)表示圖的存儲(chǔ)表示7.3 圖的遍歷圖的遍歷7.4 最小生成樹(shù)最小生成樹(shù)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)鍵路徑2021/6/77 圖圖是由一個(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,VR)其中，VR|v,wV 且 P(v,w)表示從 v 到 w 的一條弧，并稱(chēng) v 為弧頭弧頭，w

6、為弧尾弧尾。謂詞 P(v,w)定義了弧 的意義或信息。圖的結(jié)構(gòu)定義圖的結(jié)構(gòu)定義:7.1 圖的定義與術(shù)語(yǔ)圖的定義與術(shù)語(yǔ)2021/6/78 由于“弧”是有方向的，因此稱(chēng)由頂點(diǎn)集和弧集構(gòu)成的圖為有向圖有向圖。AB E C D例如例如:G1=(V1,VR1)其中V1=A,B,C,D,EVR1=,2021/6/79若VR 必有VR,則稱(chēng)(v,w)為頂點(diǎn)v 和頂點(diǎn) w 之間存在一條邊邊。B CA D F E由頂點(diǎn)集和邊集構(gòu)成的圖稱(chēng)作無(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)2021/6/7

7、10名詞和術(shù)語(yǔ)名詞和術(shù)語(yǔ)網(wǎng)、子圖 完全圖、稀疏圖、稠密圖鄰接點(diǎn)、度、入度、出度路徑、路徑長(zhǎng)度、簡(jiǎn)單路徑、簡(jiǎn)單回路連通圖、連通分量、強(qiáng)連通圖、強(qiáng)連通分量生成樹(shù)、生成森林2021/6/711ABECFAEFBBC設(shè)圖G=(V,VR)和圖 G=(V,VR),且 VV,VRVR,則稱(chēng) G 為 G 的子圖子圖。1597211132 弧或邊帶權(quán)的圖分別稱(chēng)作有向網(wǎng)有向網(wǎng)或無(wú)向網(wǎng)無(wú)向網(wǎng)。C2021/6/712假設(shè)圖中有 n 個(gè)頂點(diǎn)，e 條邊，則 含有 e=n(n-1)/2 條邊的無(wú)向圖稱(chēng)作完全圖完全圖；含有 e=n(n-1)條弧的有向圖稱(chēng)作 有向完全圖有向完全圖；若邊或弧的個(gè)數(shù) enlogn，則稱(chēng)作稀疏圖稀疏

8、圖，否則稱(chēng)作稠密圖稠密圖。2021/6/713 假若頂點(diǎn)v 和頂點(diǎn)w 之間存在一條邊，則稱(chēng)頂點(diǎn)v 和w 互為鄰接點(diǎn)鄰接點(diǎn)，ACDFE例如例如:ID(B)=3ID(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ù)目定義為頂點(diǎn)v的度度。B2021/6/714頂點(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)=32021/6/715設(shè)圖G=(V,VR)中的一個(gè)頂點(diǎn)序列 u=vi,0,vi,1

9、,vi,m=w中，(vi,j-1,vi,j)VR 1jm,則稱(chēng)從頂點(diǎn)u 到頂點(diǎn)w 之間存在一條路徑路徑。路徑上邊(或弧)的數(shù)目稱(chēng)作路徑長(zhǎng)度路徑長(zhǎng)度。ABECF如如:長(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)相同的路徑而其余頂點(diǎn)不重復(fù)。2021/6/716若圖G中任意兩個(gè)頂點(diǎn)之間都有路徑相通，則稱(chēng)此圖為連通圖連通圖；若無(wú)向圖為非連通圖，則圖中各個(gè)極大連通子圖稱(chēng)作此圖的連通連通分量分量。BACDFEBACDFE2021/6/717 若任意兩個(gè)頂點(diǎn)之間都存在一條有向路徑，則稱(chēng)此有向圖為強(qiáng)連通圖強(qiáng)連通圖。ABECFABEC

10、F對(duì)有向圖，對(duì)有向圖，否則，其各個(gè)強(qiáng)連通子圖稱(chēng)作它的強(qiáng)連通分量強(qiáng)連通分量。2021/6/718 假設(shè)一個(gè)連通圖有 n 個(gè)頂點(diǎn)和 e 條邊，其中 n-1 條邊和 n 個(gè)頂點(diǎn)構(gòu)成一個(gè)極小連通子圖，稱(chēng)該極小連通子圖為此連通圖的生成樹(shù)生成樹(shù)。對(duì)非連通圖，則稱(chēng)由各個(gè)連通分量的生成樹(shù)的集合為此非連通圖的生成森林生成森林。BACDFE2021/6/719結(jié)構(gòu)的建立和銷(xiāo)毀結(jié)構(gòu)的建立和銷(xiāo)毀插入或刪除頂點(diǎn)插入或刪除頂點(diǎn)對(duì)鄰接點(diǎn)的操作對(duì)鄰接點(diǎn)的操作對(duì)頂點(diǎn)的訪問(wèn)操作對(duì)頂點(diǎn)的訪問(wèn)操作遍歷遍歷插入和刪除弧插入和刪除弧基本操作基本操作2021/6/720CreatGraph(&G,V,VR):/按定義(V,VR)構(gòu)造圖De

11、stroyGraph(&G):/銷(xiāo)毀圖結(jié)構(gòu)的建立和銷(xiāo)毀結(jié)構(gòu)的建立和銷(xiāo)毀2021/6/721對(duì)頂點(diǎn)的訪問(wèn)操作對(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。2021/6/722對(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)”

12、。若 w 是 v 的最后一個(gè)鄰接點(diǎn)，則/返回“空”。2021/6/723插入或刪除頂點(diǎn)插入或刪除頂點(diǎn)InsertVex(&G,v);/在圖G中增添新頂點(diǎn)v。DeleteVex(&G,v);/刪除G中頂點(diǎn)v及其相關(guān)的弧。2021/6/724插入和刪除弧插入和刪除弧InsertArc(&G,v,w);/在G中增添弧，若G是無(wú)向的，/則還增添對(duì)稱(chēng)弧。DeleteArc(&G,v,w);/在G中刪除弧，若G是無(wú)向的，/則還刪除對(duì)稱(chēng)弧。2021/6/725遍遍 歷歷DFSTraverse(G,v,Visit();/從頂點(diǎn)v起深度優(yōu)先深度優(yōu)先遍歷圖G，并對(duì)每/個(gè)頂點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。BFST

13、raverse(G,v,Visit();/從頂點(diǎn)v起廣度優(yōu)先廣度優(yōu)先遍歷圖G，并對(duì)每/個(gè)頂點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。2021/6/7267.2 圖的存儲(chǔ)表示圖的存儲(chǔ)表示一、一、圖的數(shù)組(鄰接矩陣)存儲(chǔ)表示二、圖的鄰接表存儲(chǔ)表示三、有向圖的十字鏈表存儲(chǔ)表示 四、無(wú)向圖的鄰接多重表存儲(chǔ)表示2021/6/727Aij=0 (i,j)VR1 (i,j)VR一、一、圖的數(shù)組(鄰接矩陣)存儲(chǔ)表示BACDFE定義定義:矩陣的元素為矩陣的元素為0100101000100001010010011100000111002021/6/728有向圖的鄰接矩陣有向圖的鄰接矩陣為非對(duì)稱(chēng)矩陣為非對(duì)稱(chēng)矩陣ABECF0

14、 1 0 0 10 0 1 0 00 0 0 1 01 1 0 0 00 0 1 0 02021/6/729typedef struct ArcCell /弧的定義弧的定義 VRType adj;/VRType是頂點(diǎn)關(guān)系類(lèi)型。/對(duì)無(wú)權(quán)圖，用1或0表示相鄰否；/對(duì)帶權(quán)圖，則為權(quán)值類(lèi)型。InfoType *info;/該弧相關(guān)信息的指針 ArcCell,AdjMatrixMAX_VERTEX_NUM MAX_VERTEX_NUM;2021/6/730typedef struct /圖的定義圖的定義 VertexType /頂點(diǎn)信息 vexsMAX_VERTEX_NUM;AdjMatrix arcs

15、;/弧的信息 int vexnum,arcnum;/頂點(diǎn)數(shù)，弧數(shù) GraphKind kind;/圖的種類(lèi)標(biāo)志 MGraph;2021/6/7310 A 1 41 B 0 4 52 C 3 53 D 2 54 E 0 15 F 1 2 3BACDFE二、圖的鄰接表二、圖的鄰接表 存儲(chǔ)表示存儲(chǔ)表示2021/6/7321 4230 120 1 2 3 4 A B C D E有向圖的鄰接表有向圖的鄰接表ABECD可見(jiàn)，在有向圖的鄰接表中不易找到指向該頂點(diǎn)的弧。2021/6/733ABECD有向圖的逆鄰接表有向圖的逆鄰接表A B C D E 303420 01234在有向圖的鄰接表中，對(duì)每個(gè)頂點(diǎn)，鏈接

16、的是指向該頂點(diǎn)的弧。2021/6/734typedef struct ArcNode int adjvex;/該弧所指向的頂點(diǎn)的位置 struct ArcNode *nextarc;/指向下一條弧的指針 InfoType *info;/該弧相關(guān)信息的指針 ArcNode;adjvex nextarc info弧的結(jié)點(diǎn)結(jié)構(gòu)弧的結(jié)點(diǎn)結(jié)構(gòu)2021/6/735typedef struct VNode VertexType data;/頂點(diǎn)信息 ArcNode *firstarc;/指向第一條依附該頂點(diǎn)的弧 VNode,AdjListMAX_VERTEX_NUM;data firstarc頂點(diǎn)的結(jié)點(diǎn)結(jié)構(gòu)

17、頂點(diǎn)的結(jié)點(diǎn)結(jié)構(gòu)2021/6/736typedef struct AdjList vertices;int vexnum,arcnum;int kind;/圖的種類(lèi)標(biāo)志 ALGraph;圖的結(jié)構(gòu)定義圖的結(jié)構(gòu)定義2021/6/737三、有向圖的十字鏈表存儲(chǔ)表示三、有向圖的十字鏈表存儲(chǔ)表示 弧的結(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 *hli

18、nk,*tlink;VexNode;2021/6/738頂點(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)表示 VertexType data;ArcBox *firstin,*firstout;VexNode;2021/6/739typedef 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)表示(十字鏈表十字鏈表)

19、2021/6/740四、無(wú)向圖的鄰接多重表存儲(chǔ)表示typedef struct Ebox VisitIf mark;/訪問(wèn)標(biāo)記 int ivex,jvex;/該邊依附的兩個(gè)頂點(diǎn)的位置 struct EBox *ilink,*jlink;/分別指向依附這兩個(gè)頂點(diǎn)的下一條邊 InfoType *info;/該邊信息指針 EBox;邊的結(jié)構(gòu)表示邊的結(jié)構(gòu)表示2021/6/741typedef struct /鄰接多重表鄰接多重表 VexBox adjmulistMAX_VERTEX_NUM;int vexnum,edgenum;AMLGraph;頂點(diǎn)的結(jié)構(gòu)表示頂點(diǎn)的結(jié)構(gòu)表示typedef struct

20、 VexBox VertexType data;EBox *firstedge;/指向第一條依附該頂點(diǎn)的邊 VexBox;無(wú)向圖的結(jié)構(gòu)表示無(wú)向圖的結(jié)構(gòu)表示2021/6/7427.3 圖的遍歷圖的遍歷 從圖中某個(gè)頂點(diǎn)出發(fā)游歷圖，訪遍圖中其余頂點(diǎn)，并且使圖中的每個(gè)頂點(diǎn)僅被訪問(wèn)一次的過(guò)程。深度優(yōu)先搜索深度優(yōu)先搜索廣度優(yōu)先搜索廣度優(yōu)先搜索遍歷應(yīng)用舉例遍歷應(yīng)用舉例2021/6/743 從圖中某個(gè)頂點(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)先搜索遍歷圖一、深

21、度優(yōu)先搜索遍歷圖連通圖的深度優(yōu)先搜索遍歷連通圖的深度優(yōu)先搜索遍歷2021/6/744Vw1SG1SG2SG3W1、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)先搜索遍歷。w2w3w22021/6/745從上頁(yè)的圖解可見(jiàn)從上頁(yè)的圖解可見(jiàn):1.從深度優(yōu)先搜索遍歷連通圖的過(guò)程類(lèi)似于樹(shù)的先根遍歷；解決的辦法是：為每個(gè)頂點(diǎn)設(shè)立一個(gè)“訪問(wèn)標(biāo)志 visitedw”。2.如何判別V的鄰接點(diǎn)是否被訪問(wèn)？2021/6/746void DFS(Graph G,int v)/從頂點(diǎn)從

22、頂點(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)用DFS/DFS2021/6/747 首先將圖中每個(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)先搜索遍歷2021/6/748void DFSTraverse(Graph

23、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,V-w3,V-w5 的路徑長(zhǎng)度為2；V-w6,V-w4 的路徑長(zhǎng)度為3。w1Vw2w7w6w3w8w5w42021/6/751 從圖中的某個(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)它們的鄰

24、接點(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)到為止。2021/6/752 void BFSTraverse(Graph G,Status(*Visit)(int v)for(v=0;vG.vexnum;+v)visitedv=FALSE;/初始化訪問(wèn)標(biāo)志 InitQueue(Q);/置空的輔助隊(duì)列Q for(v=0;vnext=Q.rear-next=NULLvoid EnQueue(LinkQueue&Q,QelemType e)p=(QueuePtr)malloc(sizeof

25、(QNode);p-data=e;p-next=NULL;p-prior=Q.front Q.rear-next=p;Q.rear=p;void DeQueue(LinkQueue&Q,QelemType&e)Q.front=Q.front-next;e=Q.front-data2021/6/7637.4 (連通網(wǎng)的連通網(wǎng)的)最小生成樹(shù)最小生成樹(shù) 假設(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)栴}：2021/6/764 構(gòu)造網(wǎng)的一棵最小生成樹(shù)，即：在 e 條帶權(quán)的邊中選取 n-

26、1 條邊（不構(gòu)成回路），使“權(quán)值之和權(quán)值之和”為最小。算法二：（克魯斯卡爾算法）算法二：（克魯斯卡爾算法）該問(wèn)題等價(jià)于：該問(wèn)題等價(jià)于：算法一：（普里姆算法）算法一：（普里姆算法）2021/6/765 取圖中任意一個(gè)頂點(diǎn) v 作為生成樹(shù)的根，之后往生成樹(shù)上添加新的頂點(diǎn) w。在待添在待添加的頂點(diǎn)加的頂點(diǎn) w 和已經(jīng)在生成樹(shù)上的頂點(diǎn)和已經(jīng)在生成樹(shù)上的頂點(diǎn)v 之之間必定存在一條邊，并且該邊的權(quán)值在所間必定存在一條邊，并且該邊的權(quán)值在所有連通頂點(diǎn)有連通頂點(diǎn) v 和和 w 之間的邊中取值最小之間的邊中取值最小。之后繼續(xù)往生成樹(shù)上添加頂點(diǎn)，直至生成樹(shù)上含有 n個(gè)頂點(diǎn)為止。普里姆算法的基本思想普里姆算法的基本

27、思想:2021/6/766abcdegf例如例如:195141827168213ae12dcbgf7148531621所得生成樹(shù)權(quán)值和=14+8+3+5+16+21=672021/6/767 在生成樹(shù)的構(gòu)造過(guò)程中，圖中 n 個(gè)頂點(diǎn)分屬兩個(gè)集合：已落在生成樹(shù)上的頂點(diǎn)集 U 和尚未落在生成樹(shù)上的頂點(diǎn)集V-U，則應(yīng)在所有連通在所有連通U中頂點(diǎn)和中頂點(diǎn)和V-U中中頂點(diǎn)的邊中選取權(quán)值最小的邊頂點(diǎn)的邊中選取權(quán)值最小的邊。一般情況下所添加的頂點(diǎn)應(yīng)滿(mǎn)足下列條件:2021/6/768 設(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)相連接

28、的代價(jià)最小的邊：相連接的代價(jià)最小的邊：struct VertexType adjvex;/U集中的頂點(diǎn)序號(hào) VRType lowcost;/邊的權(quán)值 closedgeMAX_VERTEX_NUM;2021/6/769abcdegf195141827168213ae12dcb7closedge0123456AdjvexLowcostaaa19141814例如例如:e12ee8168d3dd7213c5 52021/6/770void MiniSpanTree_P(MGraph G,VertexType u)/用普里姆算法從頂點(diǎn)u出發(fā)構(gòu)造網(wǎng)G的最小生成樹(shù) k=LocateVex(G,u);for(

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

30、 closedgej.lowcost)closedgej=G.vexsk,G.arcskj.adj;2021/6/772具體做法具體做法:先構(gòu)造一個(gè)只含 n 個(gè)頂點(diǎn)的子圖 SG，然后從權(quán)值最小的邊開(kāi)始，若它的添加不使SG 中產(chǎn)生回路，則在 SG 上加上這條邊，如此重復(fù)，直至加上 n-1 條邊為止?？紤]問(wèn)題的出發(fā)點(diǎn)考慮問(wèn)題的出發(fā)點(diǎn):為使生成樹(shù)上邊的權(quán)值之和達(dá)到最小，則應(yīng)使生成樹(shù)中每一條邊的權(quán)值盡可能地小?？唆斔箍査惴ǖ幕舅枷耄嚎唆斔箍査惴ǖ幕舅枷耄?021/6/773abcdegf195141827168213ae12dcbgf7148531621例如例如:71218192021/6/7

31、74算法描述算法描述:構(gòu)造非連通圖 ST=(V,);k=i=0;/k 計(jì)選中的邊數(shù) while(kadjvex;DFSArticul(G,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;2021/6/786 w=p-adjvex;/w為v0的鄰接頂點(diǎn) if(

32、visitedw=0)/w未曾被訪問(wèn) DFSArticul(G,w);/返回前求得loww 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;2021/6/7877.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)之間的最短路徑 2021/6/788 求求從源點(diǎn)到其余各點(diǎn)的最短路徑從源點(diǎn)到其余各點(diǎn)的最短路徑的算法的基本思想的算法的基本思想:依

33、依最短路徑的長(zhǎng)度最短路徑的長(zhǎng)度遞增的次序求得遞增的次序求得各條路徑各條路徑源點(diǎn)源點(diǎn)v1其中，從源點(diǎn)到從源點(diǎn)到頂點(diǎn)頂點(diǎn)v的最短路徑的最短路徑是所有路徑中長(zhǎng)度最短者。v22021/6/789 在這條路徑上，必定只含一條弧，并且這條弧的權(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)(由兩條弧組成)。2021/6/790其余最短路徑的特點(diǎn)：再下一條路徑長(zhǎng)度次短的最短路徑最短路徑的特點(diǎn):它可能有三種情況：或者是直接從源點(diǎn)到該點(diǎn)(只含一條弧)；或者是從源點(diǎn)經(jīng)過(guò)頂點(diǎn)v

34、1，再到達(dá)該頂點(diǎn)(由兩條弧組成)；或者是從源點(diǎn)經(jīng)過(guò)頂點(diǎn)v2，再到達(dá)該頂點(diǎn)。它或者是直接從源點(diǎn)到該點(diǎn)(只含一條弧)；或者是從源點(diǎn)經(jīng)過(guò)已求得最短路徑的頂點(diǎn)，再到達(dá)該頂點(diǎn)。2021/6/791求最短路徑的迪杰斯特拉算法：一般情況下，Distk=或者=+。設(shè)置輔助數(shù)組Dist，其中每個(gè)分量Distk 表示 當(dāng)前所求得的從源點(diǎn)到其余各頂點(diǎn) k 的最短路徑。2021/6/7921）在所有從源點(diǎn)出發(fā)的弧中選取一條權(quán)值最小的弧，即為第一條最短路徑。2）修改其它各頂點(diǎn)的Distk值。假設(shè)求得最短路徑的頂點(diǎn)為u，若若 Distu+G.arcsukDistk則將 Distk 改為 Distu+G.arcsuk。IN

35、FINITYkvarcsGkDist0.V0和k之間存在弧V0和k之間不存在弧其中的最小值即為最短路徑的長(zhǎng)度其中的最小值即為最短路徑的長(zhǎng)度。2021/6/793求每一對(duì)頂點(diǎn)之間的最短路徑弗洛伊德算法的基本思想是：從 vi 到 vj 的所有可能存在的路徑中，選出一條長(zhǎng)度最短的路徑。2021/6/794若存在，則存在路徑vi,vj /路徑中不含其它頂點(diǎn)若,存在，則存在路徑vi,v1,vj /路徑中所含頂點(diǎn)序號(hào)不大于1若vi,v2,v2,vj存在，則存在一條路徑vi,v2,vj /路徑中所含頂點(diǎn)序號(hào)不大于2 依次類(lèi)推，則 vi 至 vj 的最短路徑應(yīng)是上述這些路徑中，路徑長(zhǎng)度最小者。2021/6/7

36、957.7 拓?fù)渑判蛲負(fù)渑判?問(wèn)題問(wèn)題:假設(shè)以有向圖表示一個(gè)工程的施工圖或程序的數(shù)據(jù)流圖，則圖中不允許出現(xiàn)回路。檢查有向圖中是否存在回路的方法之一，是對(duì)有向圖進(jìn)行拓?fù)渑判蛲負(fù)渑判颉?021/6/796何謂何謂“拓?fù)渑判蛲負(fù)渑判颉?？?duì)有向圖進(jìn)行如下操作：按照有向圖給出的次序關(guān)系，將圖中頂點(diǎn)排成一個(gè)線性序列，對(duì)于有向圖中沒(méi)有限定次序關(guān)系的頂點(diǎn)，則可以人為加上任意的次序關(guān)系。2021/6/797例如：對(duì)于下列有向圖BDAC可求得拓?fù)溆行蛐蛄校篈 B C D 或 A C B D由此所得頂點(diǎn)的線性序列稱(chēng)之為拓?fù)溆行蛐蛄?021/6/798BDAC反之，對(duì)于下列有向圖不能求得它的拓?fù)溆行蛐蛄?。因?yàn)閳D中存在

37、一個(gè)回路 B,C,D2021/6/799如何進(jìn)行拓?fù)渑判颍咳绾芜M(jìn)行拓?fù)渑判?？一、從有向圖中選取一個(gè)沒(méi)有前驅(qū)沒(méi)有前驅(qū) 的頂點(diǎn)，并輸出之；重復(fù)上述兩步，直至圖空，或者圖不空但找不到無(wú)前驅(qū)的頂點(diǎn)為止。二、從有向圖中刪去此頂點(diǎn)以及所刪去此頂點(diǎn)以及所 有以它為尾的弧有以它為尾的弧；2021/6/7100abcghdfeabhcdgfe在算法中需要用定量的描述替代定性的概念在算法中需要用定量的描述替代定性的概念 沒(méi)有前驅(qū)的頂點(diǎn)沒(méi)有前驅(qū)的頂點(diǎn) 入度為零的頂點(diǎn)入度為零的頂點(diǎn)刪除頂點(diǎn)及以它為尾的弧刪除頂點(diǎn)及以它為尾的弧 弧頭頂點(diǎn)的入度減弧頭頂點(diǎn)的入度減12021/6/7101取入度為零的頂點(diǎn)v;while(v0

38、)printf(v);+m;w:=FirstAdj(v);while(w0)inDegreew-;w:=nextAdj(v,w);取下一個(gè)入度為零的頂點(diǎn)v;if mn printf(“圖中有回路”);算法描述算法描述2021/6/7102 為避免每次都要搜索入度為零的頂點(diǎn)，在算法中設(shè)置一個(gè)“棧?！?，以保存“入度為零”的頂點(diǎn)。CountInDegree(G,indegree);/對(duì)各頂點(diǎn)求入度InitStack(S);for(i=0;iG.vexnum;+i)if(!indegreei)Push(S,i);/入度為零的頂點(diǎn)入棧2021/6/7103count=0;/對(duì)輸出頂點(diǎn)計(jì)數(shù)while(!E

39、mptyStack(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(“圖中有回路”)2021/6/71047.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è)工程的完成期限的。2021/6/7105abcdefghk64521187244

40、例如例如:“關(guān)鍵活動(dòng)”指的是：該弧上的權(quán)值增加權(quán)值增加 將使有向圖上的最長(zhǎng)路徑的長(zhǎng)度增加。最長(zhǎng)路徑的長(zhǎng)度增加。整個(gè)工程完成的時(shí)間為：從有向圖的源點(diǎn)源點(diǎn)到匯點(diǎn)匯點(diǎn)的最長(zhǎng)路徑。源點(diǎn)匯點(diǎn)61742021/6/7106 如何求關(guān)鍵活動(dòng)？如何求關(guān)鍵活動(dòng)？“事件(頂點(diǎn))”的 最早發(fā)生時(shí)間 ve(j)ve(j)=從源點(diǎn)到頂點(diǎn)j的最長(zhǎng)路徑長(zhǎng)度；“事件(頂點(diǎn))”的 最遲發(fā)生時(shí)間 vl(k)vl(k)=從頂點(diǎn)k到匯點(diǎn)的最短路徑長(zhǎng)度。2021/6/7107 假設(shè)第 i 條弧為 則 對(duì)第 i 項(xiàng)活動(dòng)言 “活動(dòng)(弧)”的 最早開(kāi)始時(shí)間 ee(i)ee(i)=ve(j)；“活動(dòng)(弧)”的 最遲開(kāi)始時(shí)間 el(i)el(i

41、)=vl(k)dut()；2021/6/7108 事件發(fā)生時(shí)間的計(jì)算公式：ve(源點(diǎn))=0；ve(k)=Maxve(j)+dut()j為所有以k為弧頭的頂點(diǎn)集 vl(匯點(diǎn))=ve(匯點(diǎn))；vl(j)=Minvl(k)dut()k為所有以j為弧尾的頂點(diǎn)集2021/6/7109abcdefghk64521187244a b c d efg h kvevl0000000006457115 715 14 1818181818181818181816 1486610807拓?fù)溆行蛐蛄型負(fù)溆行蛐蛄?a-d-f-c-b-e-h-g-k2021/6/7110a b c d efg h kvevl0645771

42、5 14 181814161078660ab ac ad be ce df eg eh fh gk hk權(quán)權(quán)6 4 5 1 1 2 8 7 4 2 4el000645777 15 14141602366887 102021/6/7111 算法的實(shí)現(xiàn)要點(diǎn)算法的實(shí)現(xiàn)要點(diǎn):顯然，求ve的順序應(yīng)該是按拓?fù)溆行蛲負(fù)溆行虻拇涡?；?求vl的順序應(yīng)該是按拓?fù)淠嫘蛲負(fù)淠嫘虻拇涡颍灰驗(yàn)?拓?fù)淠嫘蛐蛄屑礊橥負(fù)溆行蛐蛄械?逆序列逆序列，因此 應(yīng)該在拓?fù)渑判虻倪^(guò)程中，另設(shè)一個(gè)“棧棧”記下拓?fù)溆行蛐蛄小?021/6/7112【本章小結(jié)】【本章小結(jié)】圖是一種比線性表和樹(shù)更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。在線性表圖是一種比線性表和樹(shù)更復(fù)雜

43、的數(shù)據(jù)結(jié)構(gòu)。在線性表中，數(shù)據(jù)元素之間僅有線性關(guān)系，每個(gè)數(shù)據(jù)元素只有一個(gè)中，數(shù)據(jù)元素之間僅有線性關(guān)系，每個(gè)數(shù)據(jù)元素只有一個(gè)直接前驅(qū)和一個(gè)直接后繼。在樹(shù)形結(jié)構(gòu)中，數(shù)據(jù)元素之間直接前驅(qū)和一個(gè)直接后繼。在樹(shù)形結(jié)構(gòu)中，數(shù)據(jù)元素之間存在著明顯的層次關(guān)系，并且每層的元素可能和下一層的存在著明顯的層次關(guān)系，并且每層的元素可能和下一層的多個(gè)元素（即其孩子結(jié)點(diǎn)）相鄰，但只能和上一層的一個(gè)多個(gè)元素（即其孩子結(jié)點(diǎn)）相鄰，但只能和上一層的一個(gè)元素（即其雙親結(jié)點(diǎn)）相關(guān)。而在圖形結(jié)構(gòu)中，結(jié)點(diǎn)之間元素（即其雙親結(jié)點(diǎn)）相關(guān)。而在圖形結(jié)構(gòu)中，結(jié)點(diǎn)之間的關(guān)系可以是任意的，圖中任意兩個(gè)元素之間都可能相鄰。的關(guān)系可以是任意的，圖中任意

44、兩個(gè)元素之間都可能相鄰。和樹(shù)類(lèi)似，圖的遍歷是圖的一種主要操作，可以通過(guò)和樹(shù)類(lèi)似，圖的遍歷是圖的一種主要操作，可以通過(guò)遍歷判別圖中任意兩個(gè)頂點(diǎn)之間是否存在路徑、判別給定遍歷判別圖中任意兩個(gè)頂點(diǎn)之間是否存在路徑、判別給定的圖是否是連通圖并可求得非連通圖的各個(gè)連通分量，但的圖是否是連通圖并可求得非連通圖的各個(gè)連通分量，但對(duì)于帶權(quán)圖（網(wǎng)），其最小生成樹(shù)或最短路徑都取決于弧對(duì)于帶權(quán)圖（網(wǎng)），其最小生成樹(shù)或最短路徑都取決于弧或邊上的權(quán)值，則需要有特定的算法求解?；蜻吷系臋?quán)值，則需要有特定的算法求解。2021/6/7113重慶工商大學(xué)重慶工商大學(xué)計(jì)算計(jì)算機(jī)與信息工程學(xué)院機(jī)與信息工程學(xué)院部分資料從網(wǎng)絡(luò)收集整理而來(lái)，供大家參考，感謝您的關(guān)注！