數(shù)據(jù)結(jié)構(gòu)實(shí)用教程（C語(yǔ)言版）（第二版）06第六章 圖

第六章圖6.1圖的概念圖(Graph)——是一種結(jié)點(diǎn)之間為多對(duì)多關(guān)系的數(shù)據(jù)結(jié)構(gòu)。邏輯特征是：可以有任意個(gè)開始結(jié)點(diǎn)和任意個(gè)終端結(jié)點(diǎn)，其余各個(gè)結(jié)點(diǎn)可以有任意個(gè)前趨和任意個(gè)后繼。圖中的結(jié)點(diǎn)常稱為頂點(diǎn)。圖的邏輯結(jié)構(gòu)可以用二元組表示：

Graph＝(V,E)

V是頂點(diǎn)(vertex)的集合；

E是邊(edge)的集合。有向圖:若圖G中的每條邊都是有方向的，則稱圖G為有向圖。例

G1=(V1,E1)V1={v1,v2,v3}E1={<v1,v2>,<v2,v1>,<v2,v3>}G2=(V2,E2)V2={v1,v2,v3}E2={<v1,v2>,<v2,v1>,<v1,v3>,<v3,v1>,<v2,v3>,<v3,v2>}無(wú)向圖:若圖G中的每條邊都是沒有方向的，則圖G稱為無(wú)向圖。例

G3=(V3,E3)V3={v1,v2,v3,v4}E3={(v1,v2),(v1,v3),(v1,v4),(v2,v3),(v2,v4)}G4=(V4,E4)V4={v1,v2,v3}E4={(v1,v2),(v1,v3),(v2,v3)}簡(jiǎn)單圖：規(guī)定①圖中不允許同一條邊重復(fù)出現(xiàn)，②不允許出現(xiàn)頂點(diǎn)自身到自身的邊。有向完全圖：n個(gè)頂點(diǎn)的有向圖最大邊數(shù)是n(n-1)無(wú)向完全圖：n個(gè)頂點(diǎn)的無(wú)向圖最大邊數(shù)是n(n-1)/2鄰接點(diǎn)與關(guān)聯(lián)邊有向圖中，若<x,y>是有向圖中的一條邊，則頂點(diǎn)x和頂點(diǎn)y稱為鄰接點(diǎn)。稱x鄰接到y(tǒng)或y鄰接于x，同時(shí)稱邊<x,y>是頂點(diǎn)x和頂點(diǎn)y相關(guān)聯(lián)的邊；無(wú)向圖中，若（x,y）是無(wú)向圖中的一條邊，則頂點(diǎn)x和頂點(diǎn)y互為鄰接點(diǎn),并且稱邊(x,y)是頂點(diǎn)x和頂點(diǎn)y相關(guān)聯(lián)的邊。頂點(diǎn)的度有向圖中，頂點(diǎn)的度為入度與出度之和。入度：該頂點(diǎn)入邊的數(shù)目，出度：該頂點(diǎn)出邊的數(shù)目無(wú)向圖中，頂點(diǎn)的度為與該頂點(diǎn)相連的邊數(shù)。

子圖：設(shè)有圖G=(V,E)，如果滿足：V’V，E’E，E‘中邊所鄰接的點(diǎn)均在V’中出現(xiàn)，則G‘=(V’,E‘)也是一個(gè)圖，并且稱之為G的子圖。路徑：有向圖G=(V,E)中，若存在一個(gè)頂點(diǎn)序列vp,vi1,vi2,…vin,vq，使得<vp,vi1>,<vi1,vi2>,…,<vin,vq>均是圖中的邊，則稱此序列是從頂點(diǎn)vp到vq一條路徑。路徑長(zhǎng)度：該路徑上經(jīng)過邊的數(shù)目。簡(jiǎn)單路徑：序列中，除了第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)外，其余頂點(diǎn)不重復(fù)出現(xiàn)的路徑?；芈罚菏孜蚕嗤暮?jiǎn)單路徑。有根圖：若存在一個(gè)頂點(diǎn)v，從該頂點(diǎn)到其余各個(gè)頂點(diǎn)都有路

徑，則稱此圖為有根圖。連通：從頂點(diǎn)x到頂點(diǎn)y有一條路徑，則說(shuō)x和y是連通的。連通圖：圖中任意兩個(gè)頂點(diǎn)都是連通的叫連通圖。連通分量：無(wú)向圖G的極大連通子圖稱為G的連通分量。強(qiáng)連通圖：若G中任意兩個(gè)頂點(diǎn)都是強(qiáng)連通的，則稱圖G是強(qiáng)

連通圖。強(qiáng)連通分量：有向圖G的極大強(qiáng)連通子圖稱為G的強(qiáng)連通分量

權(quán)：與圖的邊相關(guān)的數(shù)值叫權(quán)值。網(wǎng)絡(luò)：邊上帶權(quán)的圖稱為網(wǎng)絡(luò)。6.2圖的存儲(chǔ)結(jié)構(gòu)鄰接矩陣——表示頂點(diǎn)之間鄰接關(guān)系的矩陣設(shè)G=(V,E）是具有n個(gè)頂點(diǎn)的圖，則G的鄰接矩陣是一個(gè)n階方陣A，A中元素的值aij可以定義為：特點(diǎn)：1、無(wú)向圖的鄰接矩陣對(duì)稱；有n個(gè)頂點(diǎn)的無(wú)向圖需存儲(chǔ)空間為n2；有向圖

鄰接矩陣不一定對(duì)稱；有n個(gè)頂點(diǎn)的有向圖需存儲(chǔ)空間為n2。2、無(wú)向圖中頂點(diǎn)Vi的度是鄰接矩陣A中第i行元素之和；有向圖中，頂點(diǎn)Vi

的出度是A中第i行元素之和，頂點(diǎn)Vi的入度是A中第i列元素之和。網(wǎng)的鄰接矩陣可定義為：鄰接矩陣存儲(chǔ)結(jié)構(gòu)C語(yǔ)言描述如下：#definen5 /*圖的頂點(diǎn)數(shù)*/#definee6 /*圖的邊數(shù)*/#definemax10000 /*設(shè)置一個(gè)極大數(shù)無(wú)窮大*/typedefcharvextype; /*頂點(diǎn)類型*/typedefintadjtype; /*權(quán)值類型*/typedefstruct{ vextypevertex[n+1]; /*頂點(diǎn)數(shù)組*/ adjtypeedge[n+1][n+1]; /*鄰接矩陣*/}adj_matrix;鄰接表鄰接表：是圖的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。1、頂點(diǎn)采用順序方式進(jìn)行存儲(chǔ)。2、用n個(gè)單鏈表來(lái)存儲(chǔ)圖中的邊，第i個(gè)單鏈表是所有與第i個(gè)頂點(diǎn)相關(guān)聯(lián)的邊鏈接而成的，稱此單鏈表為第i個(gè)頂點(diǎn)的邊表，邊表中的每個(gè)結(jié)點(diǎn)稱為邊表結(jié)點(diǎn)。3、在頂點(diǎn)的順序表中，每個(gè)元素增加一個(gè)指針域用來(lái)存放各個(gè)邊表的頭指針，稱此順序表為頂點(diǎn)表，而順序表中的每個(gè)元素稱為頂點(diǎn)表結(jié)點(diǎn)。頂點(diǎn)表和各頂點(diǎn)的邊表一起組成圖的鄰接表。鄰接表存儲(chǔ)結(jié)構(gòu)C語(yǔ)言描述如下：typedefstructnode{intadjvex;/*鄰接點(diǎn)域*/structnode*next;/*指針域*/}edgenode;/*定義邊表結(jié)點(diǎn)*/typedefstruct{vextypevertex;/*頂點(diǎn)域*/edgenode*link;/*指針域*/}vexnode;/*定義頂點(diǎn)表結(jié)點(diǎn)*/vexnodeadjlist[n+1];特點(diǎn)：

無(wú)向圖中頂點(diǎn)Vi的度為第i個(gè)單鏈表中的結(jié)點(diǎn)數(shù)；有向圖中頂點(diǎn)Vi的出度為第i個(gè)單鏈表中的結(jié)點(diǎn)個(gè)數(shù)，頂點(diǎn)Vi的入度為整個(gè)單鏈表中鄰接點(diǎn)域值是i的結(jié)點(diǎn)個(gè)數(shù)。逆鄰接表：有向圖中對(duì)每個(gè)結(jié)點(diǎn)建立以Vi終點(diǎn)的單鏈表邊集數(shù)組(edgesetarray)是圖的一種順序存儲(chǔ)方式，利用一維數(shù)組來(lái)存儲(chǔ)圖中所有的邊，數(shù)組中的每個(gè)元素用來(lái)存儲(chǔ)圖中的一條邊，包括：始點(diǎn)、終點(diǎn)的序號(hào)及權(quán)值，該數(shù)組中所含元素的個(gè)數(shù)要大于等于圖中邊的條數(shù)。邊集數(shù)組typedefstructedge{intfromvex; /*邊的始點(diǎn)域*/intendvex; /*邊的終點(diǎn)域*/intweight; /*邊的權(quán)值域*/}edgeset; /*定義邊集數(shù)組類型*/edgesetge[e+1]; /*邊集數(shù)組全局量*/6.3圖的遍歷深度優(yōu)先遍歷(DFS)：對(duì)于給定的圖G，假設(shè)初始時(shí)所有頂點(diǎn)均未被訪問過，則可從G中任選一頂點(diǎn)vi做為初始出發(fā)點(diǎn)，深度優(yōu)先搜索可定義為：訪問出發(fā)點(diǎn)vi，置訪問標(biāo)記為1，然后依次從vi的未被訪問過的鄰接點(diǎn)vj出發(fā)，繼續(xù)進(jìn)行深度優(yōu)先搜索，直至圖中所有和vi有路徑相通的頂點(diǎn)均被訪問過。很顯然圖的深度優(yōu)先搜索過程是遞歸的。它的特點(diǎn)是盡可能先對(duì)圖從縱深方向進(jìn)行搜索，故稱為深度優(yōu)先搜索。DFS序列為：v1，v2，v4，v8，v5，v3，v6，v7。深度優(yōu)先遍歷算法（遞歸算法）:voidDFS(inti){intj;printf("輸出序號(hào)為%d的頂點(diǎn):%c\n",i,adj->vertex[i]);visited[i]=1;/*標(biāo)記vi已經(jīng)訪問過*/for(j=1;j<=n;j++)/*依次搜索vi的鄰接點(diǎn)*/if((adj->edge[i][j])&&(!visited[j]))DFS(j);}voidDFSL(inti){edgenode*p;printf("輸出序號(hào)為%d的頂點(diǎn):%c\n",i,adjlist[i].vertex);visited[i]=1;/*標(biāo)記vi已經(jīng)訪問過*/p=adjlist[i].link;/*p為vi的邊表頭指針*/while(p)/*依次搜索vi的鄰接點(diǎn)*/{if(!visited[p->adjvex])DFSL(p->adjvex);p=p->next;}} 在鄰接矩陣及鄰接表上實(shí)現(xiàn)遍歷的過程：

廣度優(yōu)先遍歷(BFS)

對(duì)于給定圖G，假設(shè)初始時(shí)的所有頂點(diǎn)均未被訪問過，從圖G中任選一頂點(diǎn)vi為初始出發(fā)點(diǎn)，廣度優(yōu)先搜索遍歷可定義為：首先訪問出發(fā)點(diǎn)vi，接著依次訪問vi的所有的鄰接的未被訪問過的點(diǎn)w1，w2,…,wt，然后，再依次訪問與w1，w2,…,wt相鄰接的未被訪問過的頂點(diǎn)。依此類推，直至圖中所有和初始出發(fā)點(diǎn)vi有路徑相通的頂點(diǎn)都已訪問到為止。顯然，此方法的特點(diǎn)是盡可能先對(duì)橫向進(jìn)行搜索，故稱之為廣度優(yōu)先搜索。

BFS序列為：v1，v2，v3，v4，v5，v6，v7，v8廣度優(yōu)先遍歷算法

在廣度優(yōu)先遍歷中，先被訪問的頂點(diǎn)，其鄰接點(diǎn)亦先被訪問，所以在算法的實(shí)現(xiàn)中需要使用一個(gè)隊(duì)列，用來(lái)依次記住被訪問過的頂點(diǎn)。算法開始時(shí)，將初始點(diǎn)Vi訪問后插入隊(duì)列中，以后每從隊(duì)列中刪除一個(gè)元素，就依次訪問它的每一個(gè)未被訪問過的鄰接點(diǎn)，并令其進(jìn)隊(duì)。這樣當(dāng)隊(duì)列為空時(shí)，表明所有與初始點(diǎn)有路徑相通的頂點(diǎn)都已訪問完畢，算法到此結(jié)束。例1423512341342adjvexnext5543^^^adjvexnext551^51143^220123451fr遍歷序列：10123454fr遍歷序列：1401234543fr遍歷序列：143例1423512341342adjvexnext5543^^^adjvexnext551^51143^22012345432fr遍歷序列：143201234532fr遍歷序列：1432012345325fr遍歷序列：1432501234525fr遍歷序列：143250123455fr遍歷序列/p>

fr遍歷序列：14325例1423512341342vexdatafirstarc5543^^^adjvexnext551^51143^22鄰接表法廣度優(yōu)先：voidBFSL(intk)/*用adjlist存儲(chǔ)*/{inti;edgenode*p;SETNULL(Q);printf("序號(hào)%d的頂點(diǎn):%c\n",k,adjlist[k].vertex);/*訪問出發(fā)點(diǎn)vk*/visited[k]=1;/*標(biāo)記vk已經(jīng)訪問過*/ENQUEUE(Q,k);/*頂點(diǎn)vk的序號(hào)k入隊(duì)*/while(!EMPTY(Q))/*隊(duì)列非空?qǐng)?zhí)行*/{i=DEQUEUE(Q);/*隊(duì)頭元素頂點(diǎn)序號(hào)出隊(duì)*/p=adjlist[i].link;while(p!=NULL){if(!visited[p->adjvex]){printf("序號(hào)%d的頂點(diǎn):%c\n",p->adjvex,adjlist[p-adjvex].vertex);visited[p->adjvex]=1;ENQUEUE(Q,p->adjvex);}p=p->next;}}}生成樹

連通圖G的一個(gè)子圖如果是一棵包含G的所有頂點(diǎn)的樹，則該子圖稱為G的生成樹。深度優(yōu)先生成樹(DFS生成樹)與廣度優(yōu)先生成樹(BFS生成樹)連通圖的生成樹是包含n個(gè)點(diǎn)、n-1條邊的無(wú)回路的連通圖。說(shuō)明：1、一個(gè)圖可以有許多棵不同的生成樹2、所有生成樹具有以下共同特點(diǎn)：●生成樹的頂點(diǎn)個(gè)數(shù)與圖的頂點(diǎn)個(gè)數(shù)相同●生成樹是圖的極小連通子圖●一個(gè)有n個(gè)頂點(diǎn)的連通圖的生成樹有n-1條邊

●生成樹中任意兩個(gè)頂點(diǎn)間的路徑是唯一的

●在生成樹中再加一條邊必然形成回路3、含n個(gè)頂點(diǎn)n-1條邊的圖不一定是生成樹。6.4最小生成樹問題提出要在n個(gè)城市間建立通信聯(lián)絡(luò)網(wǎng)，頂點(diǎn)——表示城市權(quán)——城市間建立通信線路所需花費(fèi)代價(jià)希望找到一棵生成樹，它的每條邊上的權(quán)值之和（即建立該通信網(wǎng)所需花費(fèi)的總代價(jià)）最小———最小代價(jià)生成樹問題分析1654327131791812752410n個(gè)城市間，最多可設(shè)置n(n-1)/2條線路n個(gè)城市間建立通信網(wǎng)，只需n-1條線路問題轉(zhuǎn)化為：如何在可能的線路中選擇n-1條，能把所有城市（頂點(diǎn)）均連起來(lái)，且總耗費(fèi)（各邊權(quán)值之和）最小定義：連通網(wǎng)絡(luò)的所有生成樹中邊上權(quán)值之和最小的生成樹稱為

最小生成樹。MST性質(zhì)：假設(shè)G=(V,E)是一個(gè)連通網(wǎng)絡(luò)，U為頂點(diǎn)集V的一個(gè)非空子集。若邊(u,v)是所有的一個(gè)端點(diǎn)在U中（即u∈U），另一個(gè)端點(diǎn)不在U中（即v∈V-U）的這些邊里面，權(quán)值最小的一條，則一定存在一棵G的最小生成樹包括此邊(u,v)。構(gòu)造最小生成樹方法：1、普里姆(Prim)算法算法思想：設(shè)G=(V,E)是連通網(wǎng)，T=（U，TE）是G的最小生成樹，其中U是T的頂點(diǎn)集，TE是T的邊集，U和TE的初值均為空集。

初始令U={u0},(u0V),TE=

在所有uU,vV-U的邊(u,v)E中，找一條代價(jià)最小的邊(u0,v0)

將(u0,v0)并入集合TE，同時(shí)v0并入U(xiǎn)

重復(fù)上述操作直至U=V為止，則T=(V,TE)為G的最小生成樹用Prim算法構(gòu)造最小生成樹的過程

生成樹T的邊集數(shù)組數(shù)組變化過程2、克魯斯卡爾(Kruskal)算法算法思想：設(shè)連通網(wǎng)G=(V,E)，令最小生成樹T=(U,TE)初始狀態(tài)U=V,TE=

將圖G中的邊按權(quán)值從小到大的順序依次選取，若選取的邊使生成樹T不形成回路，則把它并入TE中，保留作為T的一條邊；若選取的邊使生成樹T形成回路，則將其舍棄。

依此類推，直至TE中包含n-1條邊為止，此時(shí)的T即為最小生成樹。用Kruskal算法構(gòu)造最小生成樹的過程6．5最短路經(jīng)最短路徑問題通常是指如何從圖中某一頂點(diǎn)(稱為源點(diǎn))到達(dá)另一頂點(diǎn)(稱為終點(diǎn))的多條路徑中，找到一條路徑，使得此路徑上經(jīng)過的各邊上的權(quán)值總和達(dá)到最小。最短路徑問題通?？梢苑殖伤姆N不同情況:單源點(diǎn)、單目標(biāo)點(diǎn)最短路徑問題；單源點(diǎn)、多目標(biāo)點(diǎn)最短路徑問題；多源點(diǎn)、單目標(biāo)點(diǎn)最短路徑問題；多源點(diǎn)、多目標(biāo)點(diǎn)最短路徑問題。我們討論最常見的兩種情況：?jiǎn)卧袋c(diǎn)最短路徑和任意兩點(diǎn)間的最短路徑。單源最短路經(jīng)從源點(diǎn)1到其余各頂點(diǎn)的最短路徑

迪杰斯特拉（Dijkstra）算法：（1）初始化：集合S中只有一個(gè)源點(diǎn)，其余頂點(diǎn)都在集合V-S中。此時(shí)S中源點(diǎn)的距離值（最短路徑）為0；V-S中各個(gè)頂點(diǎn)的距離值為：只經(jīng)過源點(diǎn)到達(dá)該頂點(diǎn)的當(dāng)時(shí)最短路徑，即從源點(diǎn)到達(dá)該頂點(diǎn)的邊長(zhǎng)（無(wú)邊時(shí)，距離值為∞）。當(dāng)某點(diǎn)的距離值不等于∞時(shí)，可以得到該點(diǎn)的路徑（一條邊）。（2）從V-S中選擇一個(gè)距離值最小的頂點(diǎn)v，將其加入到S中，擴(kuò)充集合S。此時(shí)該點(diǎn)的距離值就是最短路徑長(zhǎng)度。（3）對(duì)集合V-S中剩余頂點(diǎn)的距離值進(jìn)行修正。方法是：假設(shè)u是V-S中的一個(gè)頂點(diǎn)，u點(diǎn)當(dāng)前的距離值為len_u，而新加入S的點(diǎn)m的最短路徑len_m加上邊<u，m>的長(zhǎng)度為L(zhǎng)，若L<len_u，則u點(diǎn)當(dāng)前的距離值修正為：len_u=L。同時(shí)修正路徑，即在m點(diǎn)的路徑后面加上u點(diǎn)即可。（4）重復(fù)（2）、（3）步，直到所有頂點(diǎn)全部進(jìn)入集合S，即V=S為止1.初始化：S={1}，V-S={2，3，4，5}。各點(diǎn)的距離值及路徑為：2.從V-S中選擇距離值最小的頂點(diǎn)2，加入到S中。此時(shí)S={1，2}，V-S={3，4，5}。然后對(duì)V-S中各點(diǎn)的距離值進(jìn)行修正，修正后各點(diǎn)的距離值及路徑為：3.再?gòu)腣-S中選擇距離值最小的頂點(diǎn)4，加入到S中。此時(shí)S={1，2，4}，V-S={3，5}。修正V-S中的點(diǎn)的距離值為：4.繼續(xù)從V-S中選擇距離值最小的頂點(diǎn)3，加入到S中。此時(shí)S={1，2，3，4}，V-S={5}。修正V-S中的點(diǎn)的距離值為：5.最后從V-S中選擇距離值最小的頂點(diǎn)5，加入到S中。此時(shí)S={1，2，3，4，5}，V-S={}，算法結(jié)束。存前點(diǎn)”方式存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)C語(yǔ)言描述：typedefstruct{intprenode;intpathlength;}shortestpath;intflag[n+1];shortestpathsp[n+1];任意兩點(diǎn)間最短路經(jīng)Floyd算法的實(shí)現(xiàn)是通過矩陣迭代來(lái)完成的。有向圖及其鄰接矩陣：6．6拓?fù)渑判?/p>

拓?fù)渑判蚴怯邢驘o(wú)環(huán)圖（directedacyclinegraph）上的重要運(yùn)算。拓?fù)渑判虻哪康氖菍⒂邢驘o(wú)環(huán)圖中所有的頂點(diǎn)排成一個(gè)線性序列，通常稱為拓?fù)湫蛄小?/p>

拓?fù)湫蛄斜仨殱M足如下條件：對(duì)一個(gè)有向無(wú)環(huán)圖G=（V，E），若頂點(diǎn)u，v∈V，且u到v有路徑，則在此線性序列中，頂點(diǎn)u必排列在頂點(diǎn)v之前。

AOV網(wǎng)：用頂點(diǎn)表示活動(dòng)，頂點(diǎn)之間的有向邊表示活動(dòng)之間的先后關(guān)系，從而將實(shí)際問題轉(zhuǎn)化為一個(gè)有向圖，稱其為頂點(diǎn)活動(dòng)網(wǎng)（ActivityOnVertexnetwork），簡(jiǎn)稱AOV網(wǎng)

可以得到拓?fù)湫蛄校海–1，C3，C3，C4，C5，C6，，C7，C8，C9，C10）和（C2，C6，C1，C5，C7，C10，C4，C3，C8，C9）拓?fù)渑判虻姆椒ㄔ谟邢驁D中選一個(gè)沒有前驅(qū)的頂點(diǎn)且輸出之從網(wǎng)中刪除該頂點(diǎn)及所有出邊重復(fù)上述兩步，直至全部頂點(diǎn)均已輸出；或者當(dāng)網(wǎng)中不存在入度為0的頂點(diǎn)為止。一個(gè)AOV網(wǎng)的拓?fù)湫蛄胁皇俏ㄒ坏腁OV網(wǎng)求拓?fù)渑判虻倪^程算法實(shí)現(xiàn)以鄰接表作存儲(chǔ)結(jié)構(gòu)每次都需要查找入度為0的頂點(diǎn)并刪除出邊，在鄰接表上刪除出邊很容易，而要查找入度為0的頂點(diǎn)需要遍歷所有的單鏈表，較麻煩。為此，增加一個(gè)存放頂點(diǎn)入度的域（id），先將每個(gè)頂點(diǎn)的入度求出后依次存放在該域中。重復(fù)上述操作直至棧空為止,拓?fù)渑判蛲戤叀?．7關(guān)鍵路徑

關(guān)鍵路徑