數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏課件第7章

1、10/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章第七章第七章圖圖10/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章【課前思考】【課前思考】1. 同學(xué)們有沒有發(fā)現(xiàn)現(xiàn)在的十字路口的交通燈已從過去的一對改為三對，同學(xué)們有沒有發(fā)現(xiàn)現(xiàn)在的十字路口的交通燈已從過去的一對改為三對，即每個方向的直行、左拐和右拐能否通行都有相應(yīng)的交通燈指明。你能否即每個方向的直行、左拐和右拐能否通行都有相應(yīng)的交通燈指明。你能否對某個丁字路口的對某個丁字路口的6條通路畫出和第一章緒論中介紹的條通路畫出和第一章緒論中介紹的五叉路口交通管理五叉路口交通管理示意圖示意圖相類似的圖？相類似的圖？同學(xué)們一定可以畫出如下所示類似的圖形。2.

2、如果每次讓三條路同時通行，那么從圖看出哪些路可以同時通行？如果每次讓三條路同時通行，那么從圖看出哪些路可以同時通行？同時可通行的路為：(ab,bc,ca),(ab,bc,ba),(ab,ac,ca),(cb,ca,bc)10/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章【學(xué)習(xí)目標(biāo)】【學(xué)習(xí)目標(biāo)】 1領(lǐng)會圖的類型定義。2熟悉圖的各種存儲結(jié)構(gòu)及其構(gòu)造算法，了解各種存儲結(jié)構(gòu)的特點(diǎn)及其選用原則。3熟練掌握圖的兩種遍歷算法。4理解各種圖的應(yīng)用問題的算法。10/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章【重點(diǎn)和難點(diǎn)】【重點(diǎn)和難點(diǎn)】 圖的應(yīng)用極為廣泛，而且圖的各種應(yīng)用問題的算法都比較經(jīng)典，因此本章重點(diǎn)在于理解各

3、種圖的算法及其應(yīng)用場合。【知識點(diǎn)】【知識點(diǎn)】 圖的類型定義、圖的存儲表示、圖的深度優(yōu)先搜索遍歷和圖的廣度優(yōu)先搜索遍歷、無向網(wǎng)的最小生成樹、最短路徑、拓?fù)渑判?、關(guān)鍵路徑。10/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章【學(xué)習(xí)指南】【學(xué)習(xí)指南】 離散數(shù)學(xué)中的圖論是專門研究圖性質(zhì)的一個數(shù)學(xué)分離散數(shù)學(xué)中的圖論是專門研究圖性質(zhì)的一個數(shù)學(xué)分支，但圖論注重研究圖的純數(shù)學(xué)性質(zhì)，而數(shù)據(jù)結(jié)構(gòu)中對支，但圖論注重研究圖的純數(shù)學(xué)性質(zhì)，而數(shù)據(jù)結(jié)構(gòu)中對圖的討論則側(cè)重于在計算機(jī)中如何表示圖以及如何實(shí)現(xiàn)圖的討論則側(cè)重于在計算機(jī)中如何表示圖以及如何實(shí)現(xiàn)圖的操作和應(yīng)用等。圖是較線性表和樹更為復(fù)雜的數(shù)據(jù)圖的操作和應(yīng)用等。圖是較線性表

4、和樹更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，因此和線性表、樹不同，雖然在遍歷圖的同時可結(jié)構(gòu)，因此和線性表、樹不同，雖然在遍歷圖的同時可以對頂點(diǎn)或弧進(jìn)行各種操作，但更多圖的應(yīng)用問題如求以對頂點(diǎn)或弧進(jìn)行各種操作，但更多圖的應(yīng)用問題如求最小生成樹和最短路徑等在圖論的研究中都早已有了特最小生成樹和最短路徑等在圖論的研究中都早已有了特定算法，在本章中主要是介紹它們在計算機(jī)中的具體實(shí)定算法，在本章中主要是介紹它們在計算機(jī)中的具體實(shí)現(xiàn)。這些算法乍一看都比較難，應(yīng)多對照具體圖例的存現(xiàn)。這些算法乍一看都比較難，應(yīng)多對照具體圖例的存儲結(jié)構(gòu)進(jìn)行學(xué)習(xí)。而圖遍歷的兩種搜索路徑和樹遍歷的儲結(jié)構(gòu)進(jìn)行學(xué)習(xí)。而圖遍歷的兩種搜索路徑和樹遍歷的兩種搜

5、索路徑極為相似，應(yīng)將兩者的算法對照學(xué)習(xí)以便兩種搜索路徑極為相似，應(yīng)將兩者的算法對照學(xué)習(xí)以便提高學(xué)習(xí)的效果。提高學(xué)習(xí)的效果。本章必須完成的算法設(shè)計題為本章必須完成的算法設(shè)計題為 : 7.7,7.9,7.10,7.12,7.14,7.15,7.2210/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章7.1 圖的定義與術(shù)語圖的定義與術(shù)語7.2 圖的存儲表示圖的存儲表示7.3 圖的遍歷圖的遍歷7.4 最小生成樹最小生成樹7.5 重（雙）連通圖和關(guān)節(jié)點(diǎn)重（雙）連通圖和關(guān)節(jié)點(diǎn)7.6 兩點(diǎn)之間的最短路徑問題兩點(diǎn)之間的最短路徑問題7.7 拓?fù)渑判蛲負(fù)渑判?.8 關(guān)鍵路徑關(guān)鍵路徑10/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏

6、)課件第7章 圖圖是由一個是由一個頂點(diǎn)集頂點(diǎn)集 v 和一個和一個弧集弧集 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 的一條弧，并稱 v 為弧頭弧頭，w 為弧尾弧尾。 謂詞 p(v,w) 定義了弧 的意義或信息。圖的結(jié)構(gòu)定義圖的結(jié)構(gòu)定義:7.1 圖的定義與術(shù)語圖的定義與術(shù)語10/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章 由于“弧”是有方向的，因此稱由頂點(diǎn)集和弧集構(gòu)成的圖為有向圖有向圖。 ab e c d例如例如: :g1 = (v1, vr1)其中v1=a, b, c, d, evr1=, , , , ,

7、 , 10/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章若vr 必有vr, 則稱 (v,w) 為頂點(diǎn)v 和頂點(diǎn) w 之間存在一條邊邊。 b ca d f e由頂點(diǎn)集和邊集構(gòu)成的圖稱作無向圖無向圖。例如: g2=(v2,vr2)v2=a, b, c, d, e, fvr2=(a,b),(a,e),(b,e),(c,d),(d,f), (b,f),(c,f)10/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章名詞和術(shù)語名詞和術(shù)語網(wǎng)、子圖 完全圖、稀疏圖、稠密圖鄰接點(diǎn)、度、入度、出度路徑、路徑長度、簡單路徑、簡單回路連通圖、連通分量、強(qiáng)連通圖、強(qiáng)連通分量生成樹、生成森林10/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏

8、)課件第7章abecfaefbbc設(shè)圖g=(v,vr) 和圖 g=(v,vr),且 vv, vrvr,則稱 g 為 g 的子圖子圖。1597211132 弧或邊帶權(quán)的圖分別稱作有向網(wǎng)有向網(wǎng)或無向網(wǎng)無向網(wǎng)。c10/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章假設(shè)圖中有 n 個頂點(diǎn)，e 條邊，則 含有 e=n(n-1)/2 條邊的無向圖稱作完全圖完全圖； 含有 e=n(n-1) 條弧的有向圖稱作 有向完全圖有向完全圖； 若邊或弧的個數(shù) enlogn，則稱作稀疏圖稀疏圖，否則稱作稠密圖稠密圖。10/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章 假若頂點(diǎn)v 和頂點(diǎn)w 之間存在一條邊，則稱頂點(diǎn)v 和w 互為

9、鄰接點(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的度度。b10/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章頂點(diǎn)的出度出度: : 以頂點(diǎn)v為弧尾的弧的數(shù)目；abecf對有向圖來說對有向圖來說，頂點(diǎn)的入度入度: : 以頂點(diǎn)v為弧頭的弧的數(shù)目。頂點(diǎn)的度度( (td)=)=出度出度( (od)+)+入度入度( (id) )例如例如: :id(b) = 2od(b) = 1td(b) = 310/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章設(shè)圖g=(v,vr)中的一個頂點(diǎn)序列 u=vi,0,

10、vi,1, , vi,m=w中，(vi,j-1,vi,j)vr 1jm,則稱從頂點(diǎn)u 到頂點(diǎn)w 之間存在一條路徑路徑。路徑上邊(或弧)的數(shù)目稱作路徑長度路徑長度。abecf如如: :長度為3的路徑a,b,c,f簡單路徑簡單路徑:序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑。簡單回路簡單回路:序列中第一個頂點(diǎn)和最后一個頂點(diǎn)相同的路徑而其余頂點(diǎn)不重復(fù)。10/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章若圖g中任意兩個頂點(diǎn)之間都有路徑相通，則稱此圖為連通圖連通圖；若無向圖為非連通圖，則圖中各個極大連通子圖稱作此圖的連通連通分量分量。bacdfebacdfe10/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章 若任意兩個頂點(diǎn)

11、之間都存在一條有向路徑，則稱此有向圖為強(qiáng)連通圖強(qiáng)連通圖。abecfabecf對有向圖，對有向圖，否則，其各個強(qiáng)連通子圖稱作它的強(qiáng)連通分量強(qiáng)連通分量。10/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章 假設(shè)一個連通圖有 n 個頂點(diǎn)和 e 條邊，其中 n-1 條邊和 n 個頂點(diǎn)構(gòu)成一個極小連通子圖，稱該極小連通子圖為此連通圖的生成樹生成樹。對非連通圖，則稱由各個連通分量的生成樹的集合為此非連通圖的生成森林生成森林。bacdfe10/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章結(jié)構(gòu)的建立和銷毀結(jié)構(gòu)的建立和銷毀插入或刪除頂點(diǎn)插入或刪除頂點(diǎn)對鄰接點(diǎn)的操作對鄰接點(diǎn)的操作對頂點(diǎn)的訪問操作對頂點(diǎn)的訪問操作遍歷遍歷

12、插入和刪除弧插入和刪除弧基本操作基本操作10/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章creatgraph(&g, v, vr): / 按定義(v, vr) 構(gòu)造圖destroygraph(&g): / 銷毀圖結(jié)構(gòu)的建立和銷毀結(jié)構(gòu)的建立和銷毀10/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章對頂點(diǎn)的訪問操作對頂點(diǎn)的訪問操作locatevex(g, u); / 若g中存在頂點(diǎn)u，則返回該頂點(diǎn)在 / 圖中“位置位置” ；否則返回其它信息。getvex(g, v); / 返回 v 的值。putvex(&g, v, value); / 對 v 賦值value。10/29/202

13、1數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章對鄰接點(diǎn)的操作對鄰接點(diǎn)的操作firstadjvex(g, v); / 返回 v 的“第一個鄰接點(diǎn)第一個鄰接點(diǎn)”。若該頂點(diǎn)/在 g 中沒有鄰接點(diǎn)，則返回“空”。nextadjvex(g, v, w); / 返回 v 的（相對于 w 的） “下一個鄰接下一個鄰接/ 點(diǎn)點(diǎn)”。若 w 是 v 的最后一個鄰接點(diǎn)，則/ 返回“空”。10/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章插入或刪除頂點(diǎn)插入或刪除頂點(diǎn)insertvex(&g, v); /在圖g中增添新頂點(diǎn)v。deletevex(&g, v); / 刪除g中頂點(diǎn)v及其相關(guān)的弧。10/29/2021數(shù)據(jù)結(jié)構(gòu)

14、(嚴(yán)蔚敏)課件第7章插入和刪除弧插入和刪除弧insertarc(&g, v, w); / 在g中增添弧，若g是無向的， /則還增添對稱弧。deletearc(&g, v, w); /在g中刪除弧，若g是無向的， /則還刪除對稱弧。10/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章遍遍 歷歷dfstraverse(g, v, visit(); /從頂點(diǎn)v起深度優(yōu)先深度優(yōu)先遍歷圖g，并對每/個頂點(diǎn)調(diào)用函數(shù)visit一次且僅一次。bfstraverse(g, v, visit(); /從頂點(diǎn)v起廣度優(yōu)先廣度優(yōu)先遍歷圖g，并對每/個頂點(diǎn)調(diào)用函數(shù)visit一次且僅一次。10/29/2021

15、數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章7.2 圖的存儲表示圖的存儲表示一、一、圖的數(shù)組(鄰接矩陣)存儲表示二、圖的鄰接表存儲表示三、有向圖的十字鏈表存儲表示 四、無向圖的鄰接多重表存儲表示10/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章aij=0 (i,j)vr1 (i,j)vr一、一、圖的數(shù)組(鄰接矩陣)存儲表示bacdfe定義定義:矩陣的元素為矩陣的元素為01001010001000010100100111000001110010/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章有向圖的鄰接矩陣有向圖的鄰接矩陣為非對稱矩陣為非對稱矩陣abecf0 1 0 0 10 0 1 0 00 0 0 1 01 1

16、0 0 00 0 1 0 010/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章typedef struct arccell / 弧的定義弧的定義 vrtype adj; / vrtype是頂點(diǎn)關(guān)系類型。 / 對無權(quán)圖，用1或0表示相鄰否； / 對帶權(quán)圖，則為權(quán)值類型。 infotype *info; / 該弧相關(guān)信息的指針 arccell, adjmatrixmax_vertex_num max_vertex_num;10/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章typedef struct / 圖的定義圖的定義 vertextype / 頂點(diǎn)信息 vexsmax_vertex_num; ad

17、jmatrix arcs; / 弧的信息 int vexnum, arcnum; / 頂點(diǎn)數(shù)，弧數(shù) graphkind kind; / 圖的種類標(biāo)志 mgraph;10/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章0 a 1 41 b 0 4 52 c 3 53 d 2 54 e 0 15 f 1 2 3bacdfe二、圖的鄰接表二、圖的鄰接表 存儲表示存儲表示10/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章1 4230 120 1 2 3 4 a b c d e有向圖的鄰接表有向圖的鄰接表abecd可見，在有向圖的鄰接表中不易找到指向該頂點(diǎn)的弧。10/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章

18、abecd有向圖的逆鄰接表有向圖的逆鄰接表a b c d e 303420 01234在有向圖的鄰接表中，對每個頂點(diǎn)，鏈接的是指向該頂點(diǎn)的弧。10/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章typedef 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)10/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章typedef struct vnode vertext

19、ype 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)10/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章typedef struct adjlist vertices; int vexnum, arcnum; int kind; / 圖的種類標(biāo)志 algraph;圖的結(jié)構(gòu)定義圖的結(jié)構(gòu)定義10/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章三、有向圖的十字鏈表存儲表示三、有向圖的十字鏈表存儲表示 弧的結(jié)點(diǎn)結(jié)構(gòu)弧的結(jié)點(diǎn)結(jié)構(gòu)弧尾頂點(diǎn)位置 弧頭頂點(diǎn)

20、位置 弧的相關(guān)信息指向下一個有相同弧尾有相同弧尾的結(jié)點(diǎn)指向下一個有相同弧頭有相同弧頭的結(jié)點(diǎn)typedef struct arcbox / 弧弧的結(jié)構(gòu)表示的結(jié)構(gòu)表示 int tailvex, headvex; infotype *info; struct arcbox *hlink, *tlink; vexnode;10/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章頂點(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 *

21、firstin, *firstout; vexnode;10/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章typedef 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)表示(十字鏈表十字鏈表)10/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章四、無向圖的鄰接多重表存儲表示typedef struct ebox visitif mark; / 訪問標(biāo)記 int ivex, jvex; /該邊依附的兩個頂點(diǎn)的位置 struct ebox *

22、ilink, *jlink; /分別指向依附這兩個頂點(diǎn)的下一條邊 infotype *info; / 該邊信息指針 ebox;邊的結(jié)構(gòu)表示邊的結(jié)構(gòu)表示10/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章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;無向圖的結(jié)構(gòu)表示無向圖的結(jié)構(gòu)表示10/

23、29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章7.3 圖的遍歷圖的遍歷 從圖中某個頂點(diǎn)出發(fā)游歷圖，訪遍圖中其余頂點(diǎn)，并且使圖中的每個頂點(diǎn)僅被訪問一次的過程。深度優(yōu)先搜索深度優(yōu)先搜索廣度優(yōu)先搜索廣度優(yōu)先搜索遍歷應(yīng)用舉例遍歷應(yīng)用舉例10/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章 從圖中某個頂點(diǎn)v0 出發(fā)，訪問此頂點(diǎn)，然后依次從依次從v0的各個未被訪問的鄰的各個未被訪問的鄰接點(diǎn)出發(fā)深度優(yōu)先搜索遍歷圖接點(diǎn)出發(fā)深度優(yōu)先搜索遍歷圖，直至圖中所有和v0有路徑相通的頂點(diǎn)都被訪問到。一、深度優(yōu)先搜索遍歷圖一、深度優(yōu)先搜索遍歷圖連通圖的深度優(yōu)先搜索遍歷連通圖的深度優(yōu)先搜索遍歷10/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課

24、件第7章vw1sg1sg2sg3w1、w2和w3 均為 v 的鄰接點(diǎn)，sg1、sg2 和 sg3 分別為含頂點(diǎn)w1、w2和w3 的子圖。訪問頂點(diǎn) v ：for (w1、w2、w3 ) 若該鄰接點(diǎn)w未被訪問， 則從它出發(fā)進(jìn)行深度優(yōu)先搜索遍歷。w2w3w210/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章從上頁的圖解可見從上頁的圖解可見:1. 從深度優(yōu)先搜索遍歷連通圖的過程類似于樹的先根遍歷；解決的辦法是：為每個頂點(diǎn)設(shè)立一個 “訪問標(biāo)志 visitedw”。2. 如何判別v的鄰接點(diǎn)是否被訪問？10/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章void dfs(graph g, int v) / 從頂點(diǎn)

25、從頂點(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); / 對v的尚未訪問的鄰接頂點(diǎn)w / 遞歸調(diào)用dfs / dfs10/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章 首先將圖中每個頂點(diǎn)的訪問標(biāo)志設(shè)為 false, 之后搜索圖中每個頂點(diǎn)，如果未被訪問，則以該頂點(diǎn)為起始點(diǎn)，進(jìn)行深度優(yōu)先搜索遍歷，否則繼續(xù)檢查下一頂點(diǎn)。非連通圖的深度優(yōu)先搜索遍歷非連通圖的深度優(yōu)先搜索遍歷1

26、0/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章void dfstraverse(graph g, status (*visit)(int v) / 對圖對圖 g 作深度優(yōu)先遍歷。作深度優(yōu)先遍歷。 visitfunc = visit; for (v=0; vg.vexnum; +v) visitedv = false; / 訪問標(biāo)志數(shù)組初始化 for (v=0; vw1, v-w2, v-w8 的路徑長度為1；v-w7, v-w3, v-w5 的路徑長度為2；v-w6, v-w4 的路徑長度為3。w1vw2w7w6w3w8w5w410/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章 從圖中的某個頂點(diǎn)

27、v0出發(fā)，并在訪問此頂點(diǎn)之后依次訪問v0的所有未被訪問未被訪問過的鄰接點(diǎn)，之后按這些頂點(diǎn)被訪問的先后次按這些頂點(diǎn)被訪問的先后次序依次訪問它們的鄰接點(diǎn)序依次訪問它們的鄰接點(diǎn)，直至圖中所有和v0有路徑相通的頂點(diǎn)都被訪問到。 若此時圖中尚有頂點(diǎn)未被訪問，則另選圖中一個未曾被訪問的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問到為止。10/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章 void bfstraverse(graph g, status (*visit)(int v) for (v=0; vg.vexnum; +v) visitedv = false; /初始化訪問標(biāo)志 initque

28、ue(q); / 置空的輔助隊(duì)列q for ( v=0; vnext = q.rear-next = nullvoid enqueue( linkqueue& q, qelemtype e ) p = (queueptr) malloc (sizeof(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-d

29、ata10/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章7.4 (連通網(wǎng)的連通網(wǎng)的)最小生成樹最小生成樹 假設(shè)要在 n 個城市之間建立通訊聯(lián)絡(luò)網(wǎng)，則連通 n 個城市只需要修建 n-1條線路，如何在最節(jié)省經(jīng)費(fèi)的前如何在最節(jié)省經(jīng)費(fèi)的前提下建立提下建立這個通訊網(wǎng)通訊網(wǎng)？問題：問題：10/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章 構(gòu)造網(wǎng)的一棵最小生成樹，即： 在 e 條帶權(quán)的邊中選取 n-1 條邊（不構(gòu)成回路），使“權(quán)值之和權(quán)值之和”為最小。算法二：（克魯斯卡爾算法）算法二：（克魯斯卡爾算法）該問題等價于：該問題等價于：算法一：（普里姆算法）算法一：（普里姆算法）10/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)

30、課件第7章 取圖中任意一個頂點(diǎn) v 作為生成樹的根，之后往生成樹上添加新的頂點(diǎn) w。在待添在待添加的頂點(diǎn)加的頂點(diǎn) w 和已經(jīng)在生成樹上的頂點(diǎn)和已經(jīng)在生成樹上的頂點(diǎn)v 之之間必定存在一條邊，并且該邊的權(quán)值在所間必定存在一條邊，并且該邊的權(quán)值在所有連通頂點(diǎn)有連通頂點(diǎn) v 和和 w 之間的邊中取值最小之間的邊中取值最小。之后繼續(xù)往生成樹上添加頂點(diǎn)，直至生成樹上含有 n個頂點(diǎn)為止。普里姆算法的基本思想普里姆算法的基本思想:10/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章abcdegf例如例如: :195141827168213ae12dcbgf7148531621所得生成樹權(quán)值和= 14+8+3+5+

31、16+21 = 6710/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章 在生成樹的構(gòu)造過程中，圖中 n 個頂點(diǎn)分屬兩個集合：已落在生成樹上的頂點(diǎn)集 u 和尚未落在生成樹上的頂點(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)滿足下列條件:10/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章 設(shè)置一個輔助數(shù)組，對當(dāng)前設(shè)置一個輔助數(shù)組，對當(dāng)前vu集集中的每個頂點(diǎn)，記錄和頂點(diǎn)集中的每個頂點(diǎn)，記錄和頂點(diǎn)集u中頂點(diǎn)中頂點(diǎn)相連接的代價最小的邊：相連接的代價最小的邊：struct vertextype adjvex;

32、/ u集中的頂點(diǎn)序號 vrtype lowcost; / 邊的權(quán)值 closedgemax_vertex_num;10/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章abcdegf195141827168213ae12dcb7closedge0123456adjvexlowcostaaa19141814例如例如:e12ee8168d3dd7213c5 510/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章void minispantree_p(mgraph g, vertextype u) /用普里姆算法從頂點(diǎn)u出發(fā)構(gòu)造網(wǎng)g的最小生成樹 k = locatevex ( g, u ); for ( j=

33、0; jg.vexnum; +j ) / 輔助數(shù)組初始化 if (j!=k) closedgej = u, g.arcskj.adj ; closedgek.lowcost = 0; / 初始，uu for (i=0; ig.vexnum; +i) 繼續(xù)向生成樹上添加頂點(diǎn)繼續(xù)向生成樹上添加頂點(diǎn);10/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章 k = minimum(closedge); / 求出加入生成樹的下一個頂點(diǎn)(k) printf(closedgek.adjvex, g.vexsk); / 輸出生成樹上一條邊 closedgek.lowcost = 0; / 第k頂點(diǎn)并入u集 for

34、(j=0; jg.vexnum; +j) /修改其它頂點(diǎn)的最小邊 if (g.arcskj.adj closedgej.lowcost) closedgej = g.vexsk, g.arcskj.adj ; 10/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章具體做法具體做法: 先構(gòu)造一個只含 n 個頂點(diǎn)的子圖 sg，然后從權(quán)值最小的邊開始，若它的添加不使sg 中產(chǎn)生回路，則在 sg 上加上這條邊，如此重復(fù)，直至加上 n-1 條邊為止?？紤]問題的出發(fā)點(diǎn)考慮問題的出發(fā)點(diǎn): 為使生成樹上邊的權(quán)值之和達(dá)到最小，則應(yīng)使生成樹中每一條邊的權(quán)值盡可能地小。克魯斯卡爾算法的基本思想：克魯斯卡爾算法的基本思想：

35、10/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章abcdegf195141827168213ae12dcbgf7148531621例如例如: :712181910/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章算法描述算法描述:構(gòu)造非連通圖 st=( v, ); k = i = 0; / k 計選中的邊數(shù) while (kadjvex; dfsarticul(g, v); / 從第v頂點(diǎn)出發(fā)深度優(yōu)先搜索 if (count nextarc) void dfsarticul(algraph g, int v0) / 從第v0個頂點(diǎn)出發(fā)深度優(yōu)先遍歷圖 g, / 查找并輸出關(guān)節(jié)點(diǎn) / dfsarticu

36、lmin =visitedv0 = +count; / v0是第是第count個訪問的頂點(diǎn)個訪問的頂點(diǎn), 并設(shè)并設(shè)lowv0的初值為的初值為min / 檢查v0的每個鄰接點(diǎn)lowv0 = min;10/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章 w = p-adjvex; / w為v0的鄰接頂點(diǎn) if (visitedw = 0) / w未曾被訪問 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

37、) min = visitedw;10/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章7.6 兩點(diǎn)之間的兩點(diǎn)之間的 最短路徑問題最短路徑問題 求從某個源點(diǎn)到其余各點(diǎn)的求從某個源點(diǎn)到其余各點(diǎn)的最短路徑最短路徑 每一對頂點(diǎn)之間的最短路徑每一對頂點(diǎn)之間的最短路徑 10/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章 求求從源點(diǎn)到其余各點(diǎn)的最短路徑從源點(diǎn)到其余各點(diǎn)的最短路徑的算法的基本思想的算法的基本思想: 依依最短路徑的長度最短路徑的長度遞增的次序求得遞增的次序求得各條路徑各條路徑源點(diǎn)源點(diǎn)v1其中，從源點(diǎn)到從源點(diǎn)到頂點(diǎn)頂點(diǎn)v的最短路徑的最短路徑是所有路徑中長度最短者。v210/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏

38、)課件第7章 在這條路徑上，必定只含一條弧，并且這條弧的權(quán)值最小。 下一條路徑長度次短的最短路徑最短路徑的特點(diǎn)：路徑長度最短的最短路徑最短路徑的特點(diǎn)： 它只可能有兩種情況：或者是直接從源點(diǎn)到該點(diǎn)(只含一條弧)； 或者是從源點(diǎn)經(jīng)過頂點(diǎn)v1，再到達(dá)該頂點(diǎn)(由兩條弧組成)。10/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章其余最短路徑的特點(diǎn)：再下一條路徑長度次短的最短路徑最短路徑的特點(diǎn): 它可能有三種情況：或者是直接從源點(diǎn)到該點(diǎn)(只含一條弧)； 或者是從源點(diǎn)經(jīng)過頂點(diǎn)v1，再到達(dá)該頂點(diǎn)(由兩條弧組成)；或者是從源點(diǎn)經(jīng)過頂點(diǎn)v2，再到達(dá)該頂點(diǎn)。 它或者是直接從源點(diǎn)到該點(diǎn)(只含一條弧)； 或者是從源點(diǎn)經(jīng)過已

39、求得最短路徑的頂點(diǎn)，再到達(dá)該頂點(diǎn)。10/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章求最短路徑的迪杰斯特拉算法：一般情況下，distk = 或者 = + 。 設(shè)置輔助數(shù)組dist，其中每個分量distk 表示 當(dāng)前所求得的從源點(diǎn)到其余各頂點(diǎn) k 的最短路徑。10/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章1）在所有從源點(diǎn)出發(fā)的弧中選取一條權(quán)值最小的弧，即為第一條最短路徑。2）修改其它各頂點(diǎn)的distk值。假設(shè)求得最短路徑的頂點(diǎn)為u，若若 distu+g.arcsukdistk則將 distk 改為 distu+g.arcsuk。infinitykvarcsgkdist0.v0和k之間存在弧v0和

40、k之間不存在弧其中的最小值即為最短路徑的長度其中的最小值即為最短路徑的長度。10/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章求每一對頂點(diǎn)之間的最短路徑弗洛伊德算法的基本思想是： 從 vi 到 vj 的所有可能存在的路徑中，選出一條長度最短的路徑。10/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章若存在，則存在路徑vi,vj / 路徑中不含其它頂點(diǎn)若,存在，則存在路徑vi,v1,vj / 路徑中所含頂點(diǎn)序號不大于1若vi,v2, v2,vj存在， 則存在一條路徑vi, , v2, vj / 路徑中所含頂點(diǎn)序號不大于2 依次類推，則 vi 至 vj 的最短路徑應(yīng)是上述這些路徑中，路徑長度最小者。10

41、/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章7.7 拓?fù)渑判蛲負(fù)渑判?問題問題: 假設(shè)以有向圖表示一個工程的施工圖或程序的數(shù)據(jù)流圖，則圖中不允許出現(xiàn)回路。 檢查有向圖中是否存在回路的方法之一，是對有向圖進(jìn)行拓?fù)渑判蛲負(fù)渑判颉?0/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章何謂何謂“拓?fù)渑判蛲負(fù)渑判颉保繉τ邢驁D進(jìn)行如下操作： 按照有向圖給出的次序關(guān)系，將圖中頂點(diǎn)排成一個線性序列，對于有向圖中沒有限定次序關(guān)系的頂點(diǎn)，則可以人為加上任意的次序關(guān)系。10/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章例如：對于下列有向圖bdac可求得拓?fù)溆行蛐蛄校?a b c d 或 a c b d由此所得頂點(diǎn)的線性序列

42、稱之為拓?fù)溆行蛐蛄?0/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章bdac反之，對于下列有向圖不能求得它的拓?fù)溆行蛐蛄?。因?yàn)閳D中存在一個回路 b, c, d10/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章如何進(jìn)行拓?fù)渑判颍咳绾芜M(jìn)行拓?fù)渑判?？一、從有向圖中選取一個沒有前驅(qū)沒有前驅(qū) 的頂點(diǎn)，并輸出之； 重復(fù)上述兩步，直至圖空，或者圖不空但找不到無前驅(qū)的頂點(diǎn)為止。二、從有向圖中刪去此頂點(diǎn)以及所刪去此頂點(diǎn)以及所 有以它為尾的弧有以它為尾的?。?0/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章abcghdfeabhcdgfe在算法中需要用定量的描述替代定性的概念在算法中需要用定量的描述替代定性的概念 沒有

43、前驅(qū)的頂點(diǎn)沒有前驅(qū)的頂點(diǎn) 入度為零的頂點(diǎn)入度為零的頂點(diǎn)刪除頂點(diǎn)及以它為尾的弧刪除頂點(diǎn)及以它為尾的弧 弧頭頂點(diǎn)的入度減弧頭頂點(diǎn)的入度減110/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章取入度為零的頂點(diǎn)v;while (v0) printf(v); +m; w:=firstadj(v); while (w0) indegreew-; w:=nextadj(v,w); 取下一個入度為零的頂點(diǎn)v;if mn printf(“圖中有回路”);算法描述算法描述10/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章 為避免每次都要搜索入度為零的頂點(diǎn)，在算法中設(shè)置一個“棧?！保员４妗叭攵葹榱恪钡捻旤c(diǎn)。counti

44、ndegree(g,indegree); /對各頂點(diǎn)求入度initstack(s);for ( i=0; ig.vexnum; +i) if (!indegreei) push(s, i); /入度為零的頂點(diǎn)入棧10/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章count=0; /對輸出頂點(diǎn)計數(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)生的入度

45、為零的頂點(diǎn)入棧 if (countg.vexnum) printf(“圖中有回路”)10/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章7.8 關(guān)鍵路徑關(guān)鍵路徑問題問題: 假設(shè)以有向網(wǎng)表示一個施工流圖，弧上的權(quán)值表示完成該項(xiàng)子工程所需時間。問：哪些子工程項(xiàng)是“關(guān)鍵工程”？即：哪些子工程項(xiàng)將影響整個工程的完成期限的。10/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章abcdefghk64521187244例如例如: :“關(guān)鍵活動”指的是：該弧上的權(quán)值增加權(quán)值增加 將使有向圖上的最長路徑的長度增加。最長路徑的長度增加。整個工程完成的時間為：從有向圖的源點(diǎn)源點(diǎn)到匯點(diǎn)匯點(diǎn)的最長路徑。源點(diǎn)匯點(diǎn)617410/29/2021數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第7章 如何求關(guān)鍵活動？如何求關(guān)鍵活動？“事件(頂點(diǎn))” 的 最早發(fā)生時間 ve(j)ve(j) = 從源點(diǎn)到頂點(diǎn)j的最長路徑長度；“事件(頂點(diǎn))” 的 最遲發(fā)生時間