1、第7章 圖,7.1 圖的定義、術(shù)語(yǔ)和基本運(yùn)算,7.2 圖的存儲(chǔ)結(jié)構(gòu),7.3 圖的遍歷與拓?fù)渑判?7.4 最小生成樹(shù),7.5 最短路徑,7.6 本章小結(jié),7.1 圖的定義、術(shù)語(yǔ) 和基本運(yùn)算,7.1.1 圖的定義及術(shù)語(yǔ) 圖結(jié)構(gòu)的形式化定義： Graph=(V,R)，其中： V=x | xD,D是具有相同特性的數(shù)據(jù)元素的集合； R=Edge， Edge= | P(x,y)(x,yV),謂詞P(x,y)定義了弧上的意義或信息。,圓圈代表數(shù)據(jù)元素,圓圈之間的連線(xiàn)代表數(shù)據(jù)元素之間的關(guān)系,在圖結(jié)構(gòu)中，一個(gè)元素可以有多個(gè)直接后繼，也可以有多個(gè)直接前趨。,相關(guān)術(shù)語(yǔ),頂點(diǎn)（vertex） Edge是兩個(gè)頂點(diǎn)之間的

2、關(guān)系的集合： Edge，則為從x到y(tǒng)的一條?。?x為弧尾或始點(diǎn) ；y為弧頭或終點(diǎn)。 此時(shí)的圖稱(chēng)為有向圖。,若Edge是對(duì)稱(chēng)的 用無(wú)序?qū)?x,y) 表示x和y之間的一條邊。此時(shí)的圖稱(chēng)為無(wú)向圖。,不考慮頂點(diǎn)到自身的邊： 完全圖：N個(gè)頂點(diǎn)，有N(N-1)/2條邊的無(wú)向圖； 有向完全圖：N個(gè)頂點(diǎn)，有N(N-1)條弧的有向圖；,稀疏圖 /稠密圖,網(wǎng)（Network）：帶邊權(quán)的圖,子圖：,無(wú)向圖中 兩頂點(diǎn)互為鄰接點(diǎn)； 邊和頂點(diǎn)相關(guān)聯(lián)； 頂點(diǎn)的度,有向圖中 鄰接到/鄰接自 頂點(diǎn)的入度/出度,圖中的頂點(diǎn)與邊/弧之間有以下關(guān)系,路徑 路徑的長(zhǎng)度,回路/環(huán),簡(jiǎn)單路徑 簡(jiǎn)單回路/簡(jiǎn)單環(huán),連通 連通圖 連通分量,強(qiáng)連

3、通圖 (有向圖) 強(qiáng)連通分量,連通圖的生成樹(shù) 有向圖的生成森林,7.1.2 圖的基本運(yùn)算及其ADT,圖的基本運(yùn)算 查找，插入和刪除 頂點(diǎn)在圖中的位置： 人為隨意排列,圖的ADT聲明,ADT Graph 數(shù)據(jù)對(duì)象為D: D是具有相同特性的數(shù)據(jù)元素的集合,稱(chēng)為頂點(diǎn)集。 數(shù)據(jù)間的關(guān)系R: R=Edge, Edge= | P(x,y)(x,yV),謂詞P(x,y)定義了弧上的意義或信息,幾種基本操作: graphCreate(&graph) graphDestroy (&graph) graphClear(& graph),創(chuàng)建空的圖對(duì)象graph,銷(xiāo)毀一個(gè)已有的圖graph,將圖graph清空,gr

4、aphEmpty(graph) graphCount(graph) graphInsertVertex(&graph, dataIn),判圖graph是否為空,求圖graph中頂點(diǎn)個(gè)數(shù),在圖graph中插入新頂點(diǎn),新頂點(diǎn)數(shù)據(jù)域的值是dataIn,graphDeleteVertex(&graph, dltKey) graphInsertArc(&graph, fromKey, toKey),在圖graph中插入新弧,弧頭節(jié)點(diǎn)和弧尾節(jié)點(diǎn)關(guān)鍵字是fromKey和toKey,在圖graph中刪除頂點(diǎn),待刪頂點(diǎn)數(shù)據(jù)域的關(guān)鍵字是dltKey,graphDeleteArc(&graph, fromKey,

5、toKey) graphTraverse(graph, visit),遍歷圖graph各頂點(diǎn)，并用visit代表的操作去處理各個(gè)頂點(diǎn)中的數(shù)據(jù),在圖graph中刪除弧,弧頭節(jié)點(diǎn)和弧尾節(jié)點(diǎn)關(guān)鍵字是fromKey和toKey,graphRetrieveVertex(graph, key, & DataOut) ,在圖graph中尋找關(guān)鍵字為key的頂點(diǎn),并將其信息放入DataOut輸出參數(shù)中,7.2 圖的存儲(chǔ)結(jié)構(gòu),圖的常用存儲(chǔ)結(jié)構(gòu),數(shù)組表示法連續(xù)存儲(chǔ)方式 鄰接表 鄰接多重表 鏈?zhǔn)酱鎯?chǔ)方式 十字鏈表,7.2.1 數(shù)組表示法,設(shè)G =(V,E)是有N(N1)個(gè)頂點(diǎn)的圖，則G的鄰接矩陣是具有如下性質(zhì)的N階

6、方陣：,對(duì)于無(wú)向圖，頂點(diǎn)vi的度是鄰接矩陣中第i行（或第i列）的元素之和。 對(duì)于有向圖，第i行的元素之和為頂點(diǎn)vi的出度OD(vi)，第j列的元素之和為頂點(diǎn)vj的入度ID(vj)。,網(wǎng)的鄰接矩陣可定義為：,描述圖時(shí)，我們同時(shí)使用兩個(gè)數(shù)組： 一維數(shù)組中存儲(chǔ)的是各個(gè)頂點(diǎn)的信息； 二維數(shù)組（鄰接矩陣）中存儲(chǔ)的是邊或弧的信息。,7.2.2 鄰接表,在無(wú)向圖的鄰接表中，頂點(diǎn)vi的度恰為第i個(gè)鏈表中的節(jié)點(diǎn)數(shù)；而在有向圖中，第i個(gè)鏈表中的節(jié)點(diǎn)數(shù)只是頂點(diǎn)vi的出度；為求入度，必須對(duì)整個(gè)鄰接表掃描一遍。在所有鏈表中其鄰接點(diǎn)域的值為i的節(jié)點(diǎn)的個(gè)數(shù)是頂點(diǎn)vi的入度。 有時(shí)，為了便于求每個(gè)頂點(diǎn)的入度，尚需建立一個(gè)有向

7、圖的逆鄰接表，即對(duì)每個(gè)頂點(diǎn)vi建立以vi為弧頭的鏈表。,7.2.3 鄰接多重表,鄰接多重表 適宜作無(wú)向圖的存儲(chǔ)結(jié)構(gòu)。,在無(wú)向圖的鄰接表表示法中，每條邊(vi,vj)是用兩個(gè)表節(jié)點(diǎn)表示的。這給某些圖的操作帶來(lái)不便。,7.2.4 十字鏈表,十字鏈表： 將有向圖的鄰接表和逆鄰接表結(jié)合在一起得到的一種鏈表。 圖示參看 圖7.6,在十字鏈表中既容易找到以vi為尾的弧，也容易找到以vi為頭的弧，因而容易求得頂點(diǎn)的出度和入度（若需要，可在建立十字鏈表的同時(shí)求出）。在某些有向圖的應(yīng)用中，十字鏈表是很有用的工具。,7.3 圖的遍歷與拓?fù)渑判?7.3.1 圖的遍歷 遍歷圖的方法： 深度優(yōu)先搜索 （Depth Fi

8、rst Search） 廣度優(yōu)先搜索 （Breadth First Search）,深度優(yōu)先搜索體現(xiàn)了優(yōu)先向縱深發(fā)展的趨勢(shì)。算法思路可考慮回溯法。 時(shí)間復(fù)雜度為O(n+e)。,廣度優(yōu)先搜索需要借助隊(duì)列，其時(shí)間復(fù)雜度與深度優(yōu)先搜索相同。,7.3.2 拓?fù)渑判?有向無(wú)環(huán)圖： Direct Acycline Graph，簡(jiǎn)稱(chēng)DAG圖，無(wú)環(huán)的有向圖。 有向無(wú)環(huán)圖是描述一項(xiàng)工程或系統(tǒng)其進(jìn)行過(guò)程的有效工具。,拓?fù)渑判颍═opological Sort）,由某個(gè)集合上的一個(gè)偏序得到該集合上的一個(gè)全序的運(yùn)算。,當(dāng)圖中頂點(diǎn)數(shù)量與弧的數(shù)目分別為n和e時(shí)，時(shí)間復(fù)雜度為O(n+e)。 拓?fù)渑判虮举|(zhì)上是圖的遍歷，其時(shí)間

9、復(fù)雜度為O(n)，故整個(gè)算法時(shí)間復(fù)雜度為O(n+e)。,學(xué)生的選課問(wèn)題（拓?fù)渑判騿?wèn)題）：,拓?fù)渑判蚝蟮男蛄锌捎卸喾N。下面就是其中的兩種拓?fù)湫蛄小?第一種是：1，2，3，6，4，10，5，7，9，8，11； 第二種是：3，2，6，4，5，7，8，1，10，9，11。,7.4 最小生成樹(shù),在連通網(wǎng)的生成樹(shù)中選擇這樣一棵生成樹(shù)，使它在所有生成樹(shù)中總的耗費(fèi)最小，即為此連通網(wǎng)的最小生成樹(shù)。,最小生成樹(shù)的MST性質(zhì)：假設(shè)N =(V,E)是一個(gè)連通網(wǎng)，U是頂點(diǎn)集V的一個(gè)非空子集，若(u,v)是一條具有最小權(quán)值（代價(jià)）的邊，其中uU，vV-U，則必存在一棵包含邊(u,v)的最小生成樹(shù)。,最小生成樹(shù)的兩種算法：

10、,Kruskal算法 Prim算法,基于MST性質(zhì)，使用了貪心算法的思想,Kruskal算法,按邊權(quán)值的遞增順序，依次找出權(quán)值最低的邊來(lái)構(gòu)建最小生成樹(shù)，而且規(guī)定每次新增的邊，不能使已生成的部分出現(xiàn)回路。對(duì)于N個(gè)頂點(diǎn)的連通圖來(lái)說(shuō)，當(dāng)已找出N-1條邊時(shí)，過(guò)程結(jié)束。,Prim算法,與Kruskal算法思路類(lèi)似，區(qū)別在于：每次加入的新邊都會(huì)與已生成部分相鄰接，將頂點(diǎn)逐個(gè)連通而成最小生成樹(shù)。,7.5 最短路徑,帶權(quán)圖中求最短路徑的問(wèn)題，即求兩個(gè)頂點(diǎn)間長(zhǎng)度最短的路徑。 注意：這里路徑長(zhǎng)度指的是路徑上的邊所帶權(quán)的總和，而不是路徑上邊數(shù)的總和。,7.5.1 單源最短路徑問(wèn)題與分支限界法,單源最短路徑問(wèn)題: D

11、ijkstra算法,Dijkstra算法解決單源最短路徑的基本策略是： 先求出長(zhǎng)度最小的一條最短路，然后求出長(zhǎng)度第二小的最短路徑，最后求出長(zhǎng)度最大的最短路徑。,應(yīng)用Dijkstra算法的求解過(guò)程示例,從解空間樹(shù)中我們得到源點(diǎn)A到網(wǎng)中其他頂點(diǎn)的最短路徑的分析過(guò)程中，使用了分支限界法(Branch and Bound)的思想。,分支限界法與回溯法的對(duì)比：,同：同為在問(wèn)題的解空間樹(shù)上搜索問(wèn)題解的方法。,異： 1. 求解目標(biāo)不同：回溯法的求解目標(biāo)是找出解空間樹(shù)中滿(mǎn)足約束條件的所有解，而分支限界法的求解目標(biāo)則是找出滿(mǎn)足約束條件的一個(gè)解，或是在滿(mǎn)足約束條件的解中找出使某一目標(biāo)函數(shù)值達(dá)到極大或極小的解，即在

12、某種意義下的最優(yōu)解。,2. 對(duì)解空間樹(shù)的搜索方式不同： 回溯法以深度優(yōu)先的方式搜索解空間樹(shù)，而分支限界法則以廣度優(yōu)先或以最小耗費(fèi)（最大效益）優(yōu)先的方式搜索解空間樹(shù)。,由于有雙重循環(huán)，故對(duì)于含有N個(gè)頂點(diǎn)的有向網(wǎng)來(lái)說(shuō)，Dijkstra算法總的時(shí)間復(fù)雜度是O(N2)。,7.5.2 多源最短路徑問(wèn)題與動(dòng)態(tài)規(guī)劃法,多源最短路徑問(wèn)題： 方法一：每次以一個(gè)頂點(diǎn)為源點(diǎn)，重復(fù)執(zhí)行Dijkstra 算法N次。,效率與方法一同階，但形式相對(duì)簡(jiǎn)單,方法二：Floyed算法,Floyed 算法從圖的帶權(quán)鄰接矩陣cost出發(fā)，其基本思想是： 假設(shè)求從頂點(diǎn)vi到vj 的最短路徑。如果從vi到vj有弧，則從vi到vj存在一條

13、長(zhǎng)度為costi,j的路徑。 該路徑不一定是最短路徑，尚需進(jìn)行N次試探。 首先考慮路徑 (vi,v1,vj)是否存在（即判斷弧(vi,v1)和(v1,vj)是否存在）。如果存在，則比較其路徑長(zhǎng)度。取長(zhǎng)度較短者為從vi到vj的中間頂點(diǎn)的序號(hào)不大于1的最短路徑。,假如在路徑上再增加一個(gè)頂點(diǎn)v2，即如果(vi,v2)和(v2,vj)分別是當(dāng)前找到的中間頂點(diǎn)的序號(hào)不大于1的最短路徑，那么，(vi,v2,vj)就有可能是從vi到vj中間頂點(diǎn)的序號(hào)不大于2的最短路徑。將它和已經(jīng)得到的從vi到vj中間頂點(diǎn)序號(hào)不大于1的最短路徑相比較，從中選出較小者做為中間頂點(diǎn)的序號(hào)不大于2的最短路徑。 之后，再增加一個(gè)頂點(diǎn)

14、v3，繼續(xù)進(jìn)行試探。依此類(lèi)推， ，直至經(jīng)過(guò)N次比較，最后求得的就是從vi到vj中間頂點(diǎn)的序號(hào)不大于N的最短路徑。因?yàn)橛邢蚓W(wǎng)中只有N個(gè)頂點(diǎn)，故該路徑就是從vi到vj的最短路徑。按此方法，可以同時(shí)求得各對(duì)頂點(diǎn)間的最短路徑。,Floyed 算法中，新一步的結(jié)果總是基于上一步的結(jié)果，所以每次運(yùn)算都無(wú)需從頭做起，這正是動(dòng)態(tài)規(guī)劃(Dynamic Programming)算法的典型設(shè)計(jì)思想。,動(dòng)態(tài)規(guī)劃法與分治法的對(duì)比：,同：在解決問(wèn)題時(shí)基于問(wèn)題的劃分：將問(wèn)題實(shí)例歸納為更小的、相似的子問(wèn)題，并通過(guò)求解子問(wèn)題產(chǎn)生一個(gè)全局最優(yōu)解。,異： 分治法中，各個(gè)子問(wèn)題是獨(dú)立的 (即不包含公共的子問(wèn)題)，因此一旦遞歸地求出各子問(wèn)題的解后，便可自下而上地將子問(wèn)題的解合并成問(wèn)題的解。要做許多不必要的重復(fù)工作。 動(dòng)態(tài)規(guī)劃法中，整個(gè)問(wèn)題的最優(yōu)解是由各個(gè)子問(wèn)題的最優(yōu)解構(gòu)成的。在求解過(guò)程中，每個(gè)子解都是在前面的結(jié)果上得出的新的子解，子解隨著步驟的進(jìn)行而逐步擴(kuò)大，最后一步得到完整的解。,7.6 本章小結(jié),基本內(nèi)容： 1. 圖的定義，有關(guān)術(shù)語(yǔ)； 2. 圖的四種存儲(chǔ)結(jié)構(gòu)； 3. 圖的兩種遍歷方法：深度優(yōu)先遍歷和廣度優(yōu)先遍歷；拓?fù)渑判騿?wèn)題； 4