廣東省汕頭市金山中學高中信息技術 競賽班數(shù)據(jù)結(jié)構(gòu)專項培訓教程 08圖教案.doc

8 圖8.1 圖的基本概念圖： 圖是數(shù)據(jù)結(jié)構(gòu)G(V，E)，其中V是結(jié)點的有窮非空集合，結(jié)點的偶對為邊，E是邊的集合。圖中的結(jié)點又稱為頂點。12345圖8.1.1無向圖與有向圖：如果圖中每條邊都是沒有方向的，則稱為無向圖；無向圖中的邊表示圖中頂點的無序?qū)?，即（u , v）和（v , u）表示同一條邊。如圖8.1.1為一個無向圖，它的頂點集和邊集分別為：V（G1） 1 , 2 , 3 , 4 , 5 E（G1）(1, 2) , (1, 4) , (2, 3) , (2, 5) , (3, 4) , (3, 5)1234圖8.1.2如果圖中每條邊都是有方向的，則稱其為有向圖；有向圖的邊表示圖中頂點的有序偶對；在有向圖中，箭頭表示邊的方向。如圖8.1.2為一個有向圖，該圖的頂點集和邊集分別為：V（G2） 1 , 2 , 3 , 4 E（G2）(1, 2) , (1, 3) , (2, 4) , (3, 2) , (4, 3) 度、入度、出度：在一個有向圖中，把以結(jié)點V為終點的弧的數(shù)目稱為V的入度；把以結(jié)點V為始點的弧的數(shù)目稱為V的出度。 入度和出度之和為該的結(jié)點的度。 如圖8.1.2中，頂點V3的入度為2，出度為1，度為3。路徑 、路徑長度： 圖中從VS到VP 的一條路徑是指一串由頂點所成的連續(xù)序列VS , Vi1 ,Vi2 , Vin , VP ，且其中 (VP , Vi1) , (Vi1 ,Vi2) , , (Vin , VP) 都是E上的邊。路徑上所包含邊的數(shù)目稱為路徑長度。簡單路徑、簡單回路：如果一條路徑的頂點序列中，頂點不重復出現(xiàn)，則稱此路徑為簡單路徑。起點和終點相同的路徑稱為 回路或環(huán)。除了第一個頂點和最后一個頂點之外，其余頂點不重復出現(xiàn)的回路稱為簡單回路。連通圖、強連通圖：在無向圖G1中，若從頂點Vt到Vs有路徑，則稱Vt 和Vs是連通的。如果對于圖中任意兩個頂點都是連通的，則稱G1為連通圖。 在有向圖G2中，如果每一對頂點Vi , Vj ， 從Vi到Vj和從Vj到Vi都存在路徑，則稱G2為強連通圖。子圖、生成子圖：在圖G（V，E）和圖G=（V , E）中，若V V， E E，則稱圖G是圖G的子圖。若VV，E E，則子圖G=（V , E）是圖G的一個生成子圖。 如圖8.1.3所示。12345123412345圖G的一個子圖圖G的一個生成子圖【圖8.1.3】連通分量、強連通分量：所謂連通分量是指一個無向圖中的極大連通子圖。有向圖中的極大強連通分量稱作強連通分量。這里“極大”的含義是：對該子圖中再加入其它結(jié)點，它便不再是連通的。無向圖G1G1的三個連通分量【圖8.1.4】V3V4V2V1有向圖G2V3V4V2V1G2的兩個強連通分量生成樹、生成森林：一個連通圖的生成樹是含有圖中所有頂點的一個極小連通生成子圖，首先它是原連通圖的生成子圖，其次它是連通的并且有最少的邊數(shù)。一棵含n個頂點的生成樹有且僅有n1條邊，因為一個有n個頂點的圖，如果少于n1條邊則為非連通圖，如果多于n1條邊則一定有環(huán)。但有n1條邊的圖不一定是生成樹。一個有向圖的生成森林是這樣一個生成子圖，它由若干棵互不相交的有根有向樹組成。有根有向樹是這樣一個有向圖，它恰有一個結(jié)點的入度為零，其余結(jié)點的入度為1，并且如果略去此圖中邊的方向，處理成無向圖后，圖是連通的。G3的一棵生成樹【圖8.1.5】 G3ABFECDAFEBDC【圖8.1.6】 一個有向圖及其生成森林ABCD359116網(wǎng)絡：若圖的每條邊都帶有一個權(quán)，則稱這種帶權(quán)圖為網(wǎng)絡。通常權(quán)是具有某種實際意義的數(shù)，比如，它們可以表示兩個頂點之間的距離、耗費等。 8.2 圖的存儲結(jié)構(gòu)8.2.1 鄰接矩陣1 頂點i和j之間有邊（或?。┫噙B0 反之鄰接矩陣是表示結(jié)點間相鄰關系的矩陣。若G是一個具有n個結(jié)點的圖，則G的鄰接矩陣是如下定義的nn矩陣： A i , j = 13245【圖8.2.1】 G1例如，圖8.2.1的G1的鄰接矩陣為A1：0 1 1 1 11 0 0 1 01 0 0 0 11 1 0 0 11 0 1 1 0A1 無向圖的鄰接矩陣為對稱矩陣！帶權(quán)的圖，其鄰接矩陣中值為1的元素可以用邊上的權(quán)來代替。有時還可根據(jù)需要，將網(wǎng)的鄰接矩陣中的所有的0用代替。如圖8.2.2。1423563548155679【圖8.2.2】 G2 5 7 4 8 9 5 6 5 3 1 A2 在實際編程中， 如何表示？ 8.2.2 鄰接表鄰接表是圖的一種鏈式存儲結(jié)構(gòu)。為圖中每一個頂點建立一個單鏈表，該頂點為表頭，后面連接與表頭結(jié)點有邊相連的結(jié)點。如圖8.2.3，G1、G2的鄰接表分別為：234514152513411234513245G1235166123456451236548169【圖8.2.3】 G28.3 圖的遍歷圖的遍歷就是從圖中某一頂點出發(fā)訪遍圖中其余頂點，且使每一個頂點僅被訪問一次。圖的遍歷使實現(xiàn)圖的其它算法的基礎。和樹的遍歷類似，對圖也有深度和寬度兩種遍歷，也可分別稱為深度優(yōu)先搜索和廣度優(yōu)先搜索。8.3.1 深度優(yōu)先搜索深度優(yōu)先搜索可以看出是樹的先根序遍歷的推廣。假定初始狀態(tài)時，圖G中所有結(jié)點都未被訪問過，那么從某個結(jié)點v0出發(fā)的深度優(yōu)先搜索圖G的遞歸過程可以描述為：1 訪問結(jié)點v0 （對v打上已訪問標記）依次從v0的未訪問的鄰接點出發(fā)，深度優(yōu)先搜索圖G直至圖中與V0有路徑相通的頂點都被訪問到；2 若此時圖中尚有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作起點，重復上述過程，直至圖中所有頂點都被訪問過為止。s 請思考上述過程與連通圖、非連通圖的關系?！緢D8.3.1】請寫出圖8.3.1，從頂點V1 出發(fā)進行深度搜索，得到的頂點訪問序列：參考答案：V1 V2 V4 V7 V3 V5 V8 V9 V6 V10 V12 V11數(shù)據(jù)結(jié)構(gòu)說明：n ：頂點數(shù)W1.n,1.n：圖的鄰接矩陣visited1.n：頂點訪問標志從Vi出發(fā)，深度優(yōu)先搜索的遞歸過程如下：Procedure dfs( v0 : integer ); var i:integer; beginvisit( v0); 對頂點v0的某種操作，如write(v0) visitedv0:=true;for i:=1 to n do if (Wv0,i0) and (visitedi=false) then dfs(i); end;如果是一個連通圖，以上過程就已經(jīng)遍歷全圖，但我們還應考慮非連通圖的情況，對整個圖進行深度遍歷的算法如下：Procedure traver; var i : integer;beginfor i:=1 to n do visited i :=false;for i:=1 to n do if visited i :=false then dfs( i ); end;8.3.2 廣度優(yōu)先搜索廣度優(yōu)先搜索類似于樹的按層次遍歷的過程。假定初始時圖中所有結(jié)點都未被訪問過，那么從某個結(jié)點v0出發(fā)的廣度優(yōu)先搜索過程可以描述為： 1訪問了V0之后，依次訪問V0的各個未曾被訪問的鄰接點然后分別從這些鄰接點出發(fā)，廣度搜索圖G3 若此時圖中尚有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作起點，重復上述過程，直至圖中所有頂點都被訪問為止。對于圖8.3.1，從頂點V1 出發(fā)進行廣度搜索，得到的頂點訪問序列是：V1 V2 V3 V4 V5 V6 V7 V8 V9 V10 V11 V12 廣度搜索的過程是以V0為起始點，由近至遠，依次訪問和V0有路徑相通且路徑長度為1，2， 的頂點。為了順次訪問路徑長度為2、3、 的頂點，需設 （隊列 / 棧 ？）存儲1、2、 的頂點。從Vi出發(fā)，進行廣度搜索的過程如下：Procedure bfs( v0 : integer); var q:array 1.n of integer; front , rear , i , v : integer;beginvisit( v0); 對頂點v0的某種操作，如打印 visitedv0:=true;q1:=v0; v0入隊 front:=1; rear:=1;while front0) and (visitedi=false) then begin visitedi:=true; rear:=rear+1; 入隊 qrear:=i; end;end; whileend;對整個圖進行廣度遍歷的算法如下：Procedure traver; var i : integer;beginfor i:=1 to n do visited i :=false;for i:=1 to n do if visited i :=false then bfs( i ); end;【練習8-1】從文件讀入n個城市的汽車交通圖，用C i , j 表示從城市i到城市j是否有直達汽車，C i , j =1 城市i到城市j有單向直達汽車0 城市i到城市j無單向直達汽車請編制程序，輸出從各城市出發(fā)乘汽車（包括轉(zhuǎn)車）可以到達的所有城市。輸入格式 輸入文件名：city.in 第1行為整數(shù)n，代表n個城市第2行到n1行為nn的矩陣C輸出格式 輸出文件名：city.out 第1行為城市數(shù)n 第2到n+1行：第1個整數(shù)i，后面的整數(shù)代表從第i個城市出發(fā)可直達的城市；輸入輸出舉例輸入：輸出：60 0 1 0 0 00 0 0 0 1 01 0 0 0 0 10 0 0 0 0 10 1 0 0 0 00 0 0 1 0 061 3 4 62 53 1 4 64 65 26 48.4 最小代價生成樹前面已經(jīng)提到，一個連通圖的生成樹是一個極小連通子圖，它包含原圖的所有結(jié)點，并且有盡可能少的邊。（請先復習8.1中的“生成樹”及其相關概念）遍歷一個連通圖可以得到圖的一棵生成樹。圖的生成樹不是唯一的，采用不同的遍歷方法，從不同的頂點出發(fā)，可能得到不同的生成樹。如果是帶權(quán)的連通圖，不同的生成樹會使生成樹的權(quán)值總和不同。一棵生成樹的權(quán)值總和稱為該生成樹的代價，具有最小代價的生成樹稱為最小代價生成樹。1452631417193138491216 例如，在n個村之間修水渠，左圖表示了幾個村的位置，以及各村之間修水渠的長度，當然，我們希望用最少的資金，也就是選擇其中n-1條水渠，既連通各個村子，又使總的長度最少。在建立最小代價生成樹時，以最小代價為原則，且必須滿足下列限制：(1) 只能使用原圖中的邊，且僅能使用n-1邊；(2) 所用的邊不能形成環(huán)路最小代價生成樹的生成方法主要有兩種：Kruskal算法和Prim算法。8.4.1 Kruskal算法基本思想：(1) 將整個圖的所有邊的權(quán)值從小到大排列(2) 取出權(quán)值最小者開始進行試連接，若連接結(jié)果不會造成環(huán)路則成立，否則不進行連接；14526314349161452631417193138491216 例：設E為圖G的邊集，則求圖G的最小代價生成樹的算法如下：begin side0; 最小生成樹的邊數(shù)初始化 while ( side ee ( j ) 則 ee( j ) ee ( i )w ( i , j ) ； 若最后得到的拓撲序列中頂點的個數(shù)小于網(wǎng)中頂點數(shù)n，說明網(wǎng)中存在環(huán)，算法終止；否則進入下一步驟。2 從匯點vn出發(fā)，令le( n ) = ee ( n )，按逆拓撲排序求其余頂點的最遲開始時間le ( j )，與拓撲排序不同的是，它查找出度為零的結(jié)點輸出，刪除其所有入邊。請考慮一下編程技巧？3 根據(jù)ee和le的值，對每條邊ak = ( vi , vj )，計算e (k) 和 l (k)： e (k ) = ee ( i ) ， l ( k ) = le ( j ) 若 l (k)e(k) = w (k) ，則ak是關鍵活動。另外，若網(wǎng)中有幾條關鍵路徑，那么單是提高一條關鍵路徑上的關鍵活動的速度，還不能縮短整個工期，而必須同時提高幾條關鍵路徑上的活動速度?！揪毩暋磕呈┕り牻ㄔ煲蛔鶚欠康墓ば蛴衝個，各工序的時間及相互間依賴關系已知（由文件讀入），請確定其中的關鍵工序。輸入格式： 輸入文件名： build.in 第1行： （整數(shù)） n， 代表n個工序；第2行到n1行： （若干個整數(shù)） i X V1 V2 V3 i為工序序號，X為工序時間，V1 V2 V3 為工序i所依賴的先序工序輸出格式：輸出文件名： build.out 第1行： （整數(shù)） m， 關鍵工序的數(shù)目第2到第m1行： Ki，關鍵工序的序號輸入輸出舉例：輸入：輸出：111 62 43 54 1 15 1 26 2 37 9 4 58 8 4 59 4 610 2 711 4 8 94148118.7 最短路徑在交通網(wǎng)絡中經(jīng)常遇到這樣的問題：兩地之間是否有路可通？在已有的幾條通路的情況下，哪一條最短？我們可以把交通網(wǎng)絡表示成帶權(quán)的圖，結(jié)點代表城鎮(zhèn)，邊代表城鎮(zhèn)間的公路，邊上的權(quán)代表公路的長度。上述問題就是在帶權(quán)圖中求最短路徑的問題。 最短路徑問題包括：1指定的兩結(jié)點之間的最短路徑2某結(jié)點到其它各結(jié)點的最短路徑3任意兩結(jié)點之間的最短路徑8.7.1 單源最短路徑給定帶權(quán)有向圖G和源點v0，求從v0到G中其余各頂點的最短路徑。【Dijkstra算法】設一有向圖G，求指定出發(fā)點v0到圖中所有其它結(jié)點的最短路徑的算法思想如下：1 設結(jié)點集合S，存已確定最短路徑的結(jié)點，初始時為空集；設結(jié)點集合U，存未確定最短路徑的結(jié)點，初始時存圖中的全部結(jié)點；設一維數(shù)組D，D j 存v0到vj的暫時最短路徑長度，初始時除v0為0外，其余均為無窮大； 設數(shù)組T，T i 存結(jié)點vi 到v0的最短路徑上最臨近vi的一個前驅(qū)結(jié)點；2 選擇vj，使得 D j = Min D i | viU 即在未確定最短路徑的集合U中，選擇一個D j 值最小的結(jié)點vj， 移進集合S。第一次移進U的是v0；3 將vj移進S后，對U中各結(jié)點的D值和T值進行修正： 如果 D j + w j , k D k （w j , k 為邊( vj , vk )上的權(quán)） 則 D k D j + w j , k ， T k j即：若v0至vk的路徑上加入vj 后，使路徑長度比原來更短，則修改vk的D值為加入vj后v0至vk的路徑長度，并且修改其前趨結(jié)點為vj ；4 重復2、