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

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

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

V1

131

V2

0232

V3

13

V4

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

A

141

B

0452

C

353

D

254

E

015

F

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

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

從v0到各終點的D值和最短路徑的求解過程

i=1

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

∞

∞

∞

∞

∞

無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)

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