圖及有向圖的應用

圖及有向圖的應用第一頁，共十三頁，編輯于2023年，星期二4.1基本定義與術語

基本定義：圖的二元組定義：圖G由兩個集合V和E組成，記為：

G=(V,E)其中：V是頂點的有窮非空集合，E是V中頂點偶對（稱為邊）的有窮集有向圖還是無向圖，頂點數(shù)n、邊數(shù)e和度數(shù)之間有如下關系：其中：n為圖中的頂點數(shù)，e為圖中的邊數(shù)，D(Vi)為圖中的第i頂點的度數(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可以相同也可以不同）

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

8.哈密頓圖若圖G中存在一條通過圖中所有頂點一次且僅一次的回路，則稱此回路為圖的哈密頓回路；具有哈密頓回路的圖稱為哈密頓圖第三頁，共十三頁，編輯于2023年，星期二4.2圖的存儲結構

4.2.1圖的鄰接矩陣表示法1.圖的鄰接矩陣表示法在圖的鄰接矩陣表示法中，用一個順序表來存儲頂點信息，用鄰接矩陣來表示頂點間的相鄰關系。2.鄰接矩陣（AdacencyMatrix）設G=(V,E)是具有n個頂點的圖，則G的鄰接矩陣是一個n階方陣：4.2.2鄰接表表示法第四頁，共十三頁，編輯于2023年，星期二4.2.2鄰接表表示法

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

鄰接表的類型定義如下：#defineMaxVerNum100 //最大頂點數(shù)為100typedefstructnode

{ //邊表結點

intadjvex; //鄰接點域

structnode*next; //鏈域

//若要表示邊上的權，則應增加一個數(shù)據(jù)域

}EdgeNode;typedefstructvnode

{ //頂點表結點

VertexTypevertex; //頂點域

EdgeNode*firstedge; //邊表頭指針

}VertexNode;typedefVertexNodeAdjList[MaxVertexNum]; //AdjList是鄰接表類型

typedefstruct

{

AdjListadjlist; //鄰接表

intn,e;圖中當前頂點數(shù)和邊數(shù)

}ALGraph; //對于簡單的應用，無須定義此類型，可直接使用AdjList類型第五頁，共十三頁，編輯于2023年，星期二4.3圖的遍歷

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

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

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

廣度優(yōu)先搜索的過程：第七頁，共十三頁，編輯于2023年，星期二4.4單源最短路徑問題

單源最短路徑問題是：給定帶權有向圖G=(V,E)和源點s∈V，找出從源點s到V中其他各頂點的最短路徑迪杰斯特拉（Dijkstra）算法求單源最短路徑Dijkstra算法如下所示：Dijkstra(G,D,s){ //用Dijkstra算法求有向網G的源點s到各頂點的最短路徑長度

//以下是初始化操作

S={s};D[s]=0; //設置初始的紅點集及最短距離

for(alli∈V-S)do //對藍點集中每個頂點iD[i]=G[s][i]; //設置i初始的估計距離為w<s，i>//以下是擴充紅點集

for(i=0;i<n-1;i++)do{ //最多擴充n-1個藍點到紅點集

D[k]=min{D[i];alliV-S};//在當前藍點集中選估計距離最小的頂點kif(D[k]==∞)return; //藍點集中所有藍點的估計距離均為∞時，表示這些頂點的最短路徑不存在

S=S∪{k}; //將藍點k涂紅后擴充到紅點集

for(allj∈V-S)do //調整剩余藍點的估計距離

if(D[j]>D[k]+G[k][j])//新紅點k使原D[j]值變小時，用新路徑的長度修改D[j]，使j離s更近

D[j]=D[k]+G[k][j];}}第八頁，共十三頁，編輯于2023年，星期二4.5頂點對之間最短路徑

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

floyd算法的具體過程如下：

voidFloeyd(adjmatrixG,adjmatrixd,intn)//利用弗洛伊德算法求圖GA每對頂點間的最短長度，對應存于二維數(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];}}第九頁，共十三頁，編輯于2023年，星期二4.6拓撲排序

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

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

第十頁，共十三頁，編輯于2023年，星期二拓撲排序算法如下：StatusTopologicalSort(ALGraphG){//有向圖G采用鄰接表存儲結構

//若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;}第十一頁，共十三頁，編輯于2023年，星期二4.7關鍵路徑

在帶權的有向圖中，用頂點表示事件（event），弧表示活動（activity），權表示活動持續(xù)的時間。于是，把這樣的有向圖稱為關于邊的活動網（ActivityOnEdge），簡稱AOE網，與此相對應，用頂點表示活動的先后順序關系，這樣的有向圖稱為關于頂點的活動網（ActivityOnVertexNetwork），簡稱AOV網

在AOE網中，由于有些活動可以并列進行，所以，完成工程最少時間是從起始點到結束點最長路徑的長度（路徑的長度指的是這條路徑的所有活動持續(xù)的時間之和）。把從起點到結束點具有最大長度的路稱為關鍵路徑（criticalpath）分析關鍵路徑的目的是識別哪些活動是關鍵活動，以便提高關鍵活動的工效，縮短整個工程的完成時間

第十二頁，共十三頁，編輯于2023年，星期二小結

圖