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

《圖及有向圖的應(yīng)用》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、第4章圖及有向圖的應(yīng)用基本定義與術(shù)語圖的存儲結(jié)構(gòu)圖的存儲結(jié)構(gòu)單源最短路徑問題頂點對之間最短路徑拓撲排序關(guān)鍵路徑小結(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

2、)，…，(vim,vq)都屬于E(G)，則稱頂點vp到vq存在一條路徑（Path）2.簡單路徑如果一條路徑上除vp和vq外，其余頂點均不相同，則稱此路徑為一條簡單路徑（這里vp和vq可以相同也可以不同）簡單回路起點和終點都相同的簡單路徑稱為簡單回路（Cycle）。有根圖和圖的根在一個有向圖中，如果存在一個頂點v，從v可以到達圖中其他所有頂點，則稱此有向圖為有根圖，其中v稱作圖的根。連通圖和連通分量在無向圖中，如果從頂點V到頂點V′有路徑，則稱V和V′是連通的。如果對于圖中的任意兩個頂點Vi和Vj都是連通的，則稱G為連通圖強連通圖和強連

3、通分量在有向圖G中，若對于V(G)中任意兩個不同的頂點vi和vj，都存在從vi到vj以及從vj到vi的路徑，則稱G是強連通圖。有向圖的極大強連通子圖稱為G的強連通分量。歐拉圖如果圖中存在一條通過圖中每條邊一次且僅一次的回路，則稱此回路為歐拉回路，具有歐拉回路的圖稱為歐拉圖8.哈密頓圖若圖G中存在一條通過圖中所有頂點一次且僅一次的回路，則稱此回路為圖的哈密頓回路；具有哈密頓回路的圖稱為哈密頓圖4.2圖的存儲結(jié)構(gòu)4.2.1圖的鄰接矩陣表示法1.圖的鄰接矩陣表示法在圖的鄰接矩陣表示法中，用一個順序表來存儲頂點信息，用鄰接矩陣來表示頂點間的相

4、鄰關(guān)系。2.鄰接矩陣（AdacencyMatrix）設(shè)G=(V,E)是具有n個頂點的圖，則G的鄰接矩陣是一個n階方陣：4.2.2鄰接表表示法4.2.2鄰接表表示法圖的鄰接表表示法類似于樹的孩子鏈表表示法鄰接表的類型定義如下：#defineMaxVerNum100//最大頂點數(shù)為100typedefstructnode{//邊表結(jié)點intadjvex;//鄰接點域structnode*next;//鏈域//若要表示邊上的權(quán)，則應(yīng)增加一個數(shù)據(jù)域}EdgeNode;typedefstructvnode{//頂點表結(jié)點VertexTypeve

5、rtex;//頂點域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)先搜索特點：盡可能先對縱深方向進

6、行搜索?；舅枷胧牵阂詧D中某個頂點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.4單源最短路徑問題單源最短路徑問題是：給定帶權(quán)有向圖G=(V,E)和源點s∈V，找出從源點s到V中其他各頂點的最短路徑迪杰斯特拉（Dijkstra）

7、算法求單源最短路徑Dijkstra算法如下所示：Dijkstra(G,D,s){//用Dijkstra算法求有向網(wǎng)G的源點s到各頂點的最短路徑長度//以下是初始化操作S={s};D[s]=0;//設(shè)置初始的紅點集及最短距離for(alli∈V-S)do//對藍點集中每個頂點iD[i]=G[s][i];//設(shè)置i初始的估計距離為w//以下是擴充紅點集for(i=0;i

8、)return;//藍點集中所有藍點的估計距離均為∞時，表示這些頂點的最短路徑不存在S=S∪{k};//將藍點k涂紅后擴充到紅點集for(allj∈V-S)do//調(diào)整剩余藍點的估計距離if(D[j]>D[k]+G[k]