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

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

1、第4章圖及有向圖的應(yīng)用基本定義與術(shù)語(yǔ)圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu)單源最短路徑問(wèn)題頂點(diǎn)對(duì)之間最短路徑拓?fù)渑判蜿P(guān)鍵路徑小結(jié)4.1基本定義與術(shù)語(yǔ)基本定義：圖的二元組定義：圖G由兩個(gè)集合V和E組成，記為：G=(V,E)其中：V是頂點(diǎn)的有窮非空集合，E是V中頂點(diǎn)偶對(duì)（稱(chēng)為邊）的有窮集有向圖還是無(wú)向圖，頂點(diǎn)數(shù)n、邊數(shù)e和度數(shù)之間有如下關(guān)系：其中：n為圖中的頂點(diǎn)數(shù)，e為圖中的邊數(shù)，D(Vi)為圖中的第i頂點(diǎn)的度數(shù)基本術(shù)語(yǔ)：1.路徑（Path）在無(wú)向圖G中，如果存在一個(gè)頂點(diǎn)序列vp,vi1,vi2,…,vim,vq，使得(vp,vi1)，(vi1,vi2

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

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

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

5、rtex;//頂點(diǎn)域EdgeNode*firstedge;//邊表頭指針}VertexNode;typedefVertexNodeAdjList[MaxVertexNum];//AdjList是鄰接表類(lèi)型typedefstruct{AdjListadjlist;//鄰接表intn,e;圖中當(dāng)前頂點(diǎn)數(shù)和邊數(shù)}ALGraph;//對(duì)于簡(jiǎn)單的應(yīng)用，無(wú)須定義此類(lèi)型，可直接使用AdjList類(lèi)型4.3圖的遍歷圖的遍歷基本方法有兩種：深度優(yōu)先搜索和廣度優(yōu)先搜索，這兩種方法都適用于有向圖和無(wú)向圖的遍歷4.3.1深度優(yōu)先搜索特點(diǎn)：盡可能先對(duì)縱深方向進(jìn)

6、行搜索?；舅枷胧牵阂詧D中某個(gè)頂點(diǎn)v1為出發(fā)點(diǎn)，先訪問(wèn)v1，然后選一個(gè)v1的鄰接點(diǎn)v2，以v2為新的出發(fā)點(diǎn)繼續(xù)進(jìn)行深度優(yōu)先搜索，直至圖中所有頂點(diǎn)都被訪問(wèn)過(guò)。搜索過(guò)程：4.3.2廣度優(yōu)先搜索特點(diǎn)：盡可能優(yōu)先對(duì)橫向搜索基本思想是：從圖中某個(gè)頂點(diǎn)v1出發(fā)，訪問(wèn)了v1之后依次訪問(wèn)v1的所有鄰接點(diǎn)；然后分別從這些鄰接點(diǎn)出發(fā)按深度優(yōu)先搜索遍歷圖的其他頂點(diǎn)，直至所有頂點(diǎn)都被訪問(wèn)到廣度優(yōu)先搜索的過(guò)程：4.4單源最短路徑問(wèn)題單源最短路徑問(wèn)題是：給定帶權(quán)有向圖G=(V,E)和源點(diǎn)s∈V，找出從源點(diǎn)s到V中其他各頂點(diǎn)的最短路徑迪杰斯特拉（Dijkstra）

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

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