圖及有向圖的應(yīng)用課件

第4章圖及有向圖的應(yīng)用

基本定義與術(shù)語圖的存儲結(jié)構(gòu)圖的存儲結(jié)構(gòu)單源最短路徑問題頂點對之間最短路徑小結(jié)4.1基本定義與術(shù)語

基本定義：圖的二元組定義：圖G由兩個集合V和E組成，記為：G=(V,E)其中：V是頂點的有窮非空集合，E是V中頂點偶對（稱為邊）的有窮集有向圖還是無向圖，頂點數(shù)n、邊數(shù)e和度數(shù)之間有如下關(guān)系：其中：n為圖中的頂點數(shù)，e為圖中的邊數(shù)，D(Vi)為圖中的第i頂點的度數(shù)

基本術(shù)語：1.路徑（Path）在無向圖G中，如果存在一個頂點序列vp,vi1,vi2,…,vim,vq，使得(vp,vi1)，(vi1,vi2)，…，(vim,vq)都屬于E(G)，則稱頂點vp到vq存在一條路徑（Path）2.簡單路徑如果一條路徑上除vp和vq外，其余頂點均不相同，則稱此路徑為一條簡單路徑（這里vp和vq可以相同也可以不同）

簡單回路起點和終點都相同的簡單路徑稱為簡單回路（Cycle）。有根圖和圖的根在一個有向圖中，如果存在一個頂點v，從v可以到達圖中其他所有頂點，則稱此有向圖為有根圖，其中v稱作圖的根。連通圖和連通分量在無向圖中，如果從頂點V到頂點V′有路徑，則稱V和V′是連通的。如果對于圖中的任意兩個頂點Vi和Vj都是連通的，則稱G為連通圖強連通圖和強連通分量在有向圖G中，若對于V(G)中任意兩個不同的頂點vi和vj，都存在從vi到vj以及從vj到vi的路徑，則稱G是強連通圖。有向圖的極大強連通子圖稱為G的強連通分量。歐拉圖如果圖中存在一條通過圖中每條邊一次且僅一次的回路，則稱此回路為歐拉回路，具有歐拉回路的圖稱為歐拉圖

8.哈密頓圖若圖G中存在一條通過圖中所有頂點一次且僅一次的回路，則稱此回路為圖的哈密頓回路；具有哈密頓回路的圖稱為哈密頓圖4.2.2鄰接表表示法

圖的鄰接表表示法類似于樹的孩子鏈表表示法

鄰接表的類型定義如下：#defineMaxVerNum100 //最大頂點數(shù)為100typedefstructnode{ //邊表結(jié)點intadjvex; //鄰接點域structnode*next; //鏈域 //若要表示邊上的權(quán)，則應(yīng)增加一個數(shù)據(jù)域}EdgeNode;typedefstructvnode{ //頂點表結(jié)點VertexTypevertex; //頂點域EdgeNode*firstedge; //邊表頭指針}VertexNode;typedefVertexNodeAdjList[MaxVertexNum]; //AdjList是鄰接表類型typedefstruct{AdjListadjlist; //鄰接表intn,e;圖中當前頂點數(shù)和邊數(shù)}ALGraph; //對于簡單的應(yīng)用，無須定義此類型，可直接使用AdjList類型4.3圖的遍歷

圖的遍歷基本方法有兩種：深度優(yōu)先搜索和廣度優(yōu)先搜索，這兩種方法都適用于有向圖和無向圖的遍歷

4.3.1深度優(yōu)先搜索特點：盡可能先對縱深方向進行搜索。基本思想是：以圖中某個頂點v1為出發(fā)點，先訪問v1，然后選一個v1的鄰接點v2，以v2為新的出發(fā)點繼續(xù)進行深度優(yōu)先搜索，直至圖中所有頂點都被訪問過。搜索過程：4.3.2廣度優(yōu)先搜索

特點：盡可能優(yōu)先對橫向搜索基本思想是：從圖中某個頂點v1出發(fā)，訪問了v1之后依次訪問v1的所有鄰接點；然后分別從這些鄰接點出發(fā)按深度優(yōu)先搜索遍歷圖的其他頂點，直至所有頂點都被訪問到

廣度優(yōu)先搜索的過程：4.5頂點對之間最短路徑

為了求出每一對頂點之間的最短路徑，可以應(yīng)用dijkstra算法，分別以每個頂點為源點，求出從源點到各個頂點最短路徑，除此之外，還可以應(yīng)用另一種算法，稱為floyd算法

floyd算法的具體過程如下：

voidFloeyd(adjmatrixG,adjmatrixd,intn)//利用弗洛伊德算法求圖GA每對頂點間的最短長度，對應(yīng)存于二維數(shù)組A中{inti,j,k;//給二維數(shù)組d賦初值，等于鄰接矩陣Gfor(i=0;i<n;i++)for(j=0;j<n;j++)d[i][j]=G[i][j];//依次以每個頂點作為中間點，優(yōu)化數(shù)組dfor(k=0;k<n;k++)for(i=0;i<n;i++)for(j=0;j<n;j++){if(i==k||j==k||i==j)continue;if(d[i][k]+d[k][j]<d[i][j])d[i][j]=d[i][k]+d[k][j];}}4.6拓撲排序

性序列稱為滿足拓撲次序（TopoiSicalOrder）的序列，簡稱拓撲序列

有向圖拓撲排序算法的一般步驟如下：（1）從圖中選擇一個入度為0的頂點，輸出該頂點。（2）從圖中刪除該頂點及其相關(guān)聯(lián)的弧。（3）重復執(zhí)行（1）、（2）直到所有頂點均被輸出，或者圖中再也沒有入度為0的頂點（此種情況說明原有向圖含有環(huán)）

拓撲排序算法如下：StatusTopologicalSort(ALGraphG){//有向圖G采用鄰接表存儲結(jié)構(gòu)//若G無回路，則輸出G的頂點的一個拓撲序列并返回OK，否則ERRORFindInDegree(G,indegree);InitStack(S);for(i=0;i<G.vexnum;i++) //建零入度頂點棧Sif(!indegree[i])Push(S,i); //入度為0者進棧count=0; //對輸出頂點計數(shù)while(!StackEmpty(S)){Pop(S,i);printf(i,G.vertices[i].data);count++; //輸出i號頂點并計算for(p=G.vertices[i].fristarc;p;p=p->nextarc){k=p->adjvex; //對i號頂點的每個鄰接點的入度減1if(!(--indegree[k]))Push(S,k); //若入度減為0，則入棧}if（count<G.vexnum）returnERROR;elsereturnOK;}小結(jié)

圖結(jié)構(gòu)是一種比樹形結(jié)構(gòu)更復雜的非線性結(jié)構(gòu)。本章介紹了圖的概念，圖的存儲結(jié)構(gòu)，圖的深度優(yōu)先搜索和廣度優(yōu)先搜索算法，以及有向圖的若干應(yīng)用。