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

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