計(jì)算機(jī)軟件技術(shù)基礎(chǔ) 第3版 課件 第5章 圖

第5章圖2本章主要內(nèi)容5.1圖的基本概念5.2圖的存儲(chǔ)結(jié)構(gòu)5.3圖的遍歷5.4圖的應(yīng)用235.1圖的基本概念圖的定義圖的相關(guān)術(shù)語(yǔ)3圖的定義圖(Graph)是由兩個(gè)集合V(G)和E(G)所組成的，記為：G＝（V，E）。其中，G表示一個(gè)圖，V是圖G中頂點(diǎn)的集合，E是圖G中邊的集合。BCAFED45圖的表示（1）BCAFED例如:G1=(V1,E1)V1={A,B,C,D,E,F}E1={(A,B),(A,E),(B,E),(B,F),(C,D),(C,F),(D,F)}圖的表示（2）EACBD其中V2={A,B,C,D,E}E1={<A,B>,<A,E>,<B,C>,<C,D>,<D,A>,<D,B>,<E,C>}G2=(V2,E2)67圖的相關(guān)術(shù)語(yǔ)有向圖、無(wú)向圖完全圖、稠密圖、稀疏圖頂點(diǎn)的度、入度、出度邊的權(quán)、網(wǎng)圖路徑、路徑長(zhǎng)度、簡(jiǎn)單路徑回路、簡(jiǎn)單回路子圖、連通圖、強(qiáng)連通圖78有向圖與無(wú)向圖8EACBDBCAFED兩頂點(diǎn)間邊稱為“弧”9完全圖、稠密圖和稀疏圖完全圖任意兩個(gè)頂點(diǎn)間都由一條邊（?。┫噙B接無(wú)向完全圖具有n(n-1)/2條邊有向完全圖具有n(n-1)條弧稠密圖稀疏圖910頂點(diǎn)的度、入度和出度頂點(diǎn)的度某個(gè)頂點(diǎn)V的邊（?。?shù)目，記作TD(v)入度有向圖中，以某點(diǎn)V為終點(diǎn)的弧的數(shù)目,記作ID(v)出度有向圖中，以某點(diǎn)V為起點(diǎn)的弧的數(shù)目,記作OD(v)10EACBDTD(v)=ID(v)+OD(v)11邊的權(quán)和網(wǎng)圖權(quán)與邊有關(guān)的數(shù)據(jù)信息網(wǎng)圖弧或邊帶權(quán)的圖分別稱作有向網(wǎng)或無(wú)向網(wǎng)。11ABECF159721113212路徑、路徑長(zhǎng)度、簡(jiǎn)單路徑路徑從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的序列路徑長(zhǎng)度路徑上邊的數(shù)目簡(jiǎn)單路徑序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑BCAFED13回路和簡(jiǎn)單回路回路路徑序列中第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑簡(jiǎn)單回路路徑序列中第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的簡(jiǎn)單路徑14子圖、連通圖和強(qiáng)連通圖子圖設(shè)圖G=(V,{VR})和圖G=(V,{VR}),且VV,VRVR,則稱G為G的子圖。連通圖圖中任意兩個(gè)頂點(diǎn)之間都有路徑相通強(qiáng)連通圖對(duì)于有向圖，若任意兩個(gè)頂點(diǎn)之間都存在一條有向路徑，則稱此有向圖為強(qiáng)連通圖14連通圖舉例15V1V4V2V5V6V3V1V4V2V5V6強(qiáng)連通圖16ABECFAECABE5.2圖的存儲(chǔ)結(jié)構(gòu)鄰接矩陣表示法鄰接表表示法175.2.1鄰接矩陣定義:矩陣的元素為18Aij={0(i,j)VR1(i,j)VR為對(duì)稱矩陣有向圖鄰接矩陣表示非對(duì)稱矩陣19ABDCE0101000100000010010011000ABCDE有向圖鄰接矩陣表示網(wǎng)圖20鄰接矩陣表示方法特點(diǎn)無(wú)向圖是對(duì)稱矩陣

有向圖不一定是對(duì)稱矩陣判斷任意兩個(gè)點(diǎn)的鄰接關(guān)系容易適用于稠密圖215.2.2鄰接表用n個(gè)單鏈表和一個(gè)數(shù)組表示220

V1

131

V2

0232

V3

13

V4

01V1V4V2V35.2.2鄰接表用n個(gè)單鏈表和一個(gè)數(shù)組表示230

A

141

B

0452

C

353

D

254

E

015

F

123BADFEC有向圖的鄰接表在有向圖的鄰接表中不易找到指向該頂點(diǎn)的弧，即難以確定某個(gè)頂點(diǎn)的入度。24有向圖的逆鄰接表25在有向圖的逆鄰接表中，每個(gè)頂點(diǎn)鏈接的是指向該頂點(diǎn)的弧。

5.3圖的遍歷遍歷從圖中某個(gè)頂點(diǎn)出發(fā)訪問(wèn)圖中每個(gè)頂點(diǎn)一次且僅一次的過(guò)程圖遍歷形式深度優(yōu)先搜索廣度優(yōu)先搜索26深度優(yōu)先搜索步驟1）設(shè)立指針P，使P指向結(jié)點(diǎn)Vi;2）訪問(wèn)P指向的結(jié)點(diǎn)Vi，然后修改指針P，使之指向與Vi結(jié)點(diǎn)相鄰接的且尚未被訪問(wèn)的結(jié)點(diǎn)。3）若P不空，則重復(fù)步驟2；否則執(zhí)行步驟4；4）沿著剛才方位的次序，反向回溯到一個(gè)尚有鄰接頂點(diǎn)未被訪問(wèn)過(guò)的頂點(diǎn)，并使P指向該尚未被訪問(wèn)的頂點(diǎn)，然后重復(fù)步驟2，直至所有的頂點(diǎn)均被訪問(wèn)為止。深度優(yōu)先搜索舉例28achdfkebg訪問(wèn)次序:abchdekfgachkfedbg016234578廣度優(yōu)先搜索步驟訪問(wèn)V1后，依次訪問(wèn)V1的相鄰點(diǎn)的所有鄰接頂點(diǎn)W1,W2,W3…..Wi;再按W1,W2,W3…..Wi的順序，訪問(wèn)其中的每個(gè)頂點(diǎn)的所有未被訪問(wèn)過(guò)的鄰接頂點(diǎn)；再按剛才的訪問(wèn)次序，依次訪問(wèn)它們的所有未未被訪問(wèn)的鄰接頂點(diǎn)；依次類推，直到圖中所有頂點(diǎn)都被訪問(wèn)過(guò)為止。29廣度優(yōu)先搜索舉例訪問(wèn)次序：acdefhkbg30abchdekfgachkfedbg0162345785.4圖的應(yīng)用生成樹(shù)和最小生成樹(shù)最短路徑問(wèn)題AOV網(wǎng)與拓?fù)渑判?15.4.1生成樹(shù)和最小生成樹(shù)生成樹(shù)定義設(shè)G=(V,E)為連通圖，則從圖中任一頂點(diǎn)出發(fā)遍歷圖時(shí)，必定將E(G)分成兩個(gè)集合A(G)和B(G)，其中A(G)是遍歷圖過(guò)程中歷經(jīng)的邊的集合；B(G)是剩余的邊的集合。A(G)和圖G中所有頂點(diǎn)一起構(gòu)成連通圖G的極小連通子圖，稱A(G)是連通圖的一棵生成樹(shù)。325.4.1生成樹(shù)和最小生成樹(shù)最小生成樹(shù)定義如果無(wú)向連通圖是一個(gè)網(wǎng)，那么，它的所有生成樹(shù)中必有一棵邊的權(quán)值總和最小的生成樹(shù)，我則稱這棵生成樹(shù)為最小生成樹(shù)，簡(jiǎn)稱為最小生成樹(shù)。33普里姆（Prim）算法設(shè)網(wǎng)G＝（V，E）是連通圖，其中V為網(wǎng)圖中所有頂點(diǎn)的集合，E為網(wǎng)圖中所有帶權(quán)邊的集合。設(shè)置兩個(gè)新的集合U和T，其中集合U用于存放G的最小生成樹(shù)中的頂點(diǎn)，集合T存放G的最小生成樹(shù)中的邊。令集合U的初值為U＝{v1}（假設(shè)構(gòu)造最小生成樹(shù)時(shí)，從頂點(diǎn)v1出發(fā)），集合T的初值為T(mén)＝{}。Prim算法的思想是，從所有u∈U，v∈V－U（其中V-U為V的補(bǔ)集）的點(diǎn)中，選取具有最小權(quán)值的邊（u，v），將頂點(diǎn)v加入集合U中，將邊（u，v）加入集合T中，如此不斷重復(fù)，直到U＝V時(shí)，最小生成樹(shù)構(gòu)造完畢，這時(shí)集合T中包含了最小生成樹(shù)的所有邊。34普里姆（Prim）算法舉例35克魯斯卡爾算法36克魯斯卡爾算法的基本思想為使生成樹(shù)上邊的權(quán)值之和達(dá)到最小，則應(yīng)使生成樹(shù)中每一條邊的權(quán)值盡可能地小?？唆斔箍査惴ň唧w做法:先構(gòu)造一個(gè)只含n個(gè)頂點(diǎn)的子圖SG，然后從權(quán)值最小的邊開(kāi)始，若它的添加不使SG中產(chǎn)生回路，則在SG上加上這條邊，如此重復(fù)，直至加上n-1條邊為止?？唆斔箍査惴ㄅe例數(shù)組下標(biāo)0123456789頂點(diǎn)編號(hào)4232241115頂點(diǎn)編號(hào)5344662566權(quán)值4566111416192133375.4.2最短路徑A到B的最短路徑是：在點(diǎn)A到點(diǎn)B的所有路徑中，邊的權(quán)值之和最短的那一條路徑。路徑上的第一個(gè)頂點(diǎn)為源點(diǎn)，最后一個(gè)頂點(diǎn)為終點(diǎn)。常見(jiàn)最短路徑問(wèn)題從一個(gè)源點(diǎn)到其他各點(diǎn)的最短路徑每一對(duì)頂點(diǎn)間的最短路徑38從一個(gè)源點(diǎn)到其他各點(diǎn)的最短路徑迪杰斯特拉（Dijkstra）算法的基本思想：依最短路徑的長(zhǎng)度遞增的次序求得各條路徑。①．路徑長(zhǎng)度上第一條最短路徑為：在這條路徑上，必定只含一條弧，并且這條弧的權(quán)值最小。假設(shè)這個(gè)頂點(diǎn)為v1②．下一條路徑長(zhǎng)度次短的路徑為：它只可能有兩種情況：或者是直接從源點(diǎn)到該點(diǎn)(只含一條弧)；或者是從源點(diǎn)經(jīng)過(guò)頂點(diǎn)v1，再到達(dá)該頂點(diǎn)(由兩條弧組成)。假設(shè)這個(gè)頂點(diǎn)為v2.39迪杰斯特拉算法③．再下一條路徑長(zhǎng)度次短的路徑為:可能有三種情況：或者是直接從源點(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)到該點(diǎn)(只含一條弧)；或者是從源點(diǎn)經(jīng)過(guò)已求得最短路徑的頂點(diǎn)，再到達(dá)該頂點(diǎn)。40最短路徑舉例41終點(diǎn)

從v0到各終點(diǎn)的D值和最短路徑的求解過(guò)程

i=1

i=2i=3i=4i=5V1

∞

∞

∞

∞

∞

無(wú)V210(v0,v2)

V3

∞60(v0,v2,v3)50(v0,v4,v3)

V430(v0,v4)30(v0,v4)

V5100(v0,v5)100(v0,v5)90(v0,v4,v5)60(v0,v4,v3,v5)

每一對(duì)頂點(diǎn)之間的最短路徑方法一每次以一個(gè)頂點(diǎn)為源點(diǎn)，重復(fù)調(diào)用迪杰斯特拉算法便可求得到每對(duì)一頂點(diǎn)的最短路徑方法二弗洛伊德（Floyd）算法42弗洛伊德算法假設(shè)求從頂點(diǎn)vi到vj的最短路徑如果從vi到vj有弧，則從vi到vj存在一條長(zhǎng)度為edges[i][j]的路徑，該路徑不一定是最短路徑，尚需進(jìn)行n次試探。首先考慮路徑（vi,v0,vj）是否存在（即判別弧（vi,v0）和(v0,vj)是否存在）。如果存在，則比較（vi,vj）和（vi,v0,vj）的路徑長(zhǎng)度取長(zhǎng)度較短者為從vi到vj的中間頂點(diǎn)的序號(hào)不大于0的最短路徑。43弗洛伊德算法假如在路徑上再增加一個(gè)頂點(diǎn)v1，也就是說(shuō)，如果（vi,…,v1）和（v1,…,vj）分別是當(dāng)前找到的中間頂點(diǎn)的序號(hào)不大于0的最短路徑，那么（vi,…,v1,…,vj）就有可能是從vi到vj的中間頂點(diǎn)的序號(hào)不大于1的最短路徑。將它和已經(jīng)得到的從vi到vj中間頂點(diǎn)序號(hào)不大于0的最短路徑相比較，從中選出中間頂點(diǎn)的序號(hào)不大于1的最短路徑之后，再增加一個(gè)頂點(diǎn)v2，繼續(xù)進(jìn)行試探。44弗洛伊德算法在一般情況下，若（vi,…,vk）和（vk,…,vj）分別是從vi到vk和從vk到vj的中間頂點(diǎn)的序號(hào)不大于k-1的最短路徑，則將（vi,…,vk,…,vj）和已經(jīng)得到的從vi到vj且中間頂點(diǎn)序號(hào)不大于k-1的最短路徑相比較，其長(zhǎng)度較短者便是從vi到vj的中間頂點(diǎn)的序號(hào)不大于k的最短路徑。在經(jīng)過(guò)n次比較后，最后求得的必是從vi到vj的最短路徑。45弗洛伊德算法舉例465.4.3AOV網(wǎng)與拓?fù)渑判蚧顒?dòng)一個(gè)工程可以分為若干個(gè)子工程，這些子工程就稱為活動(dòng)AOV網(wǎng)以圖中的頂點(diǎn)來(lái)表示活動(dòng)，有向邊表示活動(dòng)之間的優(yōu)先關(guān)系，則這樣活動(dòng)在頂點(diǎn)上的有向圖稱為AOV網(wǎng)47拓?fù)渑判蛲負(fù)溆行蛐蛄袑?duì)于一個(gè)AOV網(wǎng)，構(gòu)造其所有頂點(diǎn)的線性序列，使此序列不僅保持網(wǎng)中每個(gè)頂點(diǎn)間原有的先后關(guān)系，而且是原來(lái)沒(méi)有先后關(guān)系的頂點(diǎn)之間也建立起人為的先后關(guān)系。這樣的