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

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ù)目稱為路徑長度。簡單路徑、簡單回路：如果一條路徑的頂點序列中，頂點不重復(fù)出現(xiàn)，則稱此路徑為簡單路徑。起點和終點相同的路徑稱為 回路或環(huán)。除了第一個頂點和最后一個頂點之外，其余頂點不重復(fù)出現(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)絡(luò)：若圖的每條邊都帶有一個權(quán)，則稱這種帶權(quán)圖為網(wǎng)絡(luò)。通常權(quán)是具有某種實際意義的數(shù)，比如，它們可以表示兩個頂點之間的距離、耗費等。 8.2 圖的存儲結(jié)構(gòu)8.2.1 鄰接矩陣1 頂點i和j之間有邊（或弧）相連0 反之鄰接矩陣是表示結(jié)點間相鄰關(guān)系的矩陣。若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)圖的其它算法的基礎(chǔ)。和樹的遍歷類似，對圖也有深度和寬度兩種遍歷，也可分別稱為深度優(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 若此時圖中尚有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作起點，重復(fù)上述過程，直至圖中所有頂點都被訪問過為止。s 請思考上述過程與連通圖、非連通圖的關(guān)系?！緢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)遍歷全圖，但我們還應(yī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 若此時圖中尚有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作起點，重復(fù)上述過程，直至圖中所有頂點都被訪問為止。對于圖8.3.1，從頂點v1 出發(fā)進行廣度搜索，得到的頂點訪問序列是：v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 v12 廣度搜索的過程是以v0為起始點，由近至遠，依次訪問和v0有路徑相通且路徑長度為1，2， 的頂點。為了順次訪問路徑長度為2、3、 的頂點，需設(shè) （隊列 / 棧 ？）存儲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é)點，并且有盡可能少的邊。（請先復(fù)習8.1中的“生成樹”及其相關(guān)概念）遍歷一個連通圖可以得到圖的一棵生成樹。圖的生成樹不是唯一的，采用不同的遍歷方法，從不同的頂點出發(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 例：設(shè)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是關(guān)鍵活動。另外，若網(wǎng)中有幾條關(guān)鍵路徑，那么單是提高一條關(guān)鍵路徑上的關(guān)鍵活動的速度，還不能縮短整個工期，而必須同時提高幾條關(guān)鍵路徑上的活動速度?！揪毩暋磕呈┕り牻ㄔ煲蛔鶚欠康墓ば蛴衝個，各工序的時間及相互間依賴關(guān)系已知（由文件讀入），請確定其中的關(guān)鍵工序。輸入格式： 輸入文件名： 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， 關(guān)鍵工序的數(shù)目第2到第m1行： ki，關(guān)鍵工序的序號輸入輸出舉例：輸入：輸出：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é)點代表城鎮(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算法】設(shè)一有向圖g，求指定出發(fā)點v0到圖中所有其它結(jié)點的最短路徑的算法思想如下：1 設(shè)結(jié)點集合s，存已確定最短路徑的結(jié)點，初始時為空集；設(shè)結(jié)點集合u，存未確定最短路徑的結(jié)點，初始時存圖中的全部結(jié)點；設(shè)一維數(shù)組d，d j 存v0到vj的暫時最短路徑長度，初始時除v0為0外，其余均為無窮大； 設(shè)數(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 重復(fù)2、