869數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版第7章圖

1、數(shù)據(jù)結(jié)構(gòu)（c語(yǔ)言版）第7章圖第第7章圖章圖 內(nèi)容內(nèi)容7.1 圖的概念圖的概念7.2 圖的存貯結(jié)構(gòu)圖的存貯結(jié)構(gòu)7.3 圖的遍歷圖的遍歷7.4 圖的最小生成樹(shù)圖的最小生成樹(shù)7.5 拓?fù)渑判蛲負(fù)渑判?.6 關(guān)鍵路徑關(guān)鍵路徑7.7 最短路徑最短路徑7.1.1圖的定義 每個(gè)結(jié)點(diǎn)有任意多個(gè)前驅(qū)和后繼結(jié)點(diǎn).圖也可以二元組表示:定義graph=(v,e) v:表示元素集合 e:元素之間的關(guān)系現(xiàn)舉兩個(gè)例子，如下圖：例一例二無(wú)向圖中（1，2）和（2，1）代表同一邊有向圖中和表示兩個(gè)不同的方向邊以為例，在中：1稱為此邊的起點(diǎn)或尾（弧尾）2稱為此邊的終點(diǎn)或頭（弧頭）邊的方向規(guī)定為弧尾弧頭 v(g1)=1,2,3,4頂

2、點(diǎn)集合;e(g1)=,邊的集合（頂點(diǎn)關(guān)系） v(g2)=1,2,3,4,5頂點(diǎn)集合;e(g2)=(1,2),(1,4),(2,3),(2,5),(3,4),(3,5)邊的集合 7.1.2圖的基本術(shù)語(yǔ) 1、完全圖：在一個(gè)有n個(gè)頂點(diǎn)的圖中，若每個(gè)頂點(diǎn)到其它（n-1）頂點(diǎn)都有一條邊，則 圖中有n個(gè)頂點(diǎn)且有（n*（n-1）/2）條邊的圖稱為完全圖。 2、鄰接點(diǎn)：對(duì)無(wú)向圖g=（v，e），若有（v1，v2）屬于e則稱v1和v2互為鄰接點(diǎn)。 3、相關(guān)邊：兩個(gè)相鄰接的點(diǎn)連成的邊叫做這兩個(gè)結(jié)點(diǎn)的相關(guān)邊。4、度：與每個(gè)頂點(diǎn)相連的邊的數(shù)叫該點(diǎn)的度。5、入度：對(duì)有向圖中某結(jié)點(diǎn)的弧頭數(shù)（邊的終點(diǎn)）稱為該結(jié)點(diǎn)的入度。6、

3、出度：對(duì)有向圖中某結(jié)點(diǎn)的弧尾數(shù)（邊的終點(diǎn)）稱為該結(jié)點(diǎn)的出度。7、路徑：在一圖中若從某個(gè)頂點(diǎn)vp出發(fā)，沿著一些邊經(jīng)過(guò)頂點(diǎn)v1，v2，,vm到達(dá)vg則稱路徑8、回路：從一頂點(diǎn)出發(fā)又回到該頂點(diǎn)，則所經(jīng)過(guò)的路徑稱為回路。 9、子圖子圖 若g和g是兩個(gè)圖，且存在著v(g)v(g)和e（g）e（g）的關(guān)系，則稱g是g的子圖1010、有關(guān)連通的概念、有關(guān)連通的概念連通：連通：在無(wú)向圖中，若從頂點(diǎn)vi到頂點(diǎn)vj之間有路徑則稱此二頂點(diǎn)是連通的。連通圖：連通圖：如果圖中任意一對(duì)頂點(diǎn)之間都是連通的，則稱此圖為連通圖。強(qiáng)連通：強(qiáng)連通：對(duì)于有向圖，若從頂點(diǎn)vi到頂點(diǎn)vj到頂點(diǎn)vi之間都有路徑，則稱這兩點(diǎn)是強(qiáng)連通的。強(qiáng)連

4、通圖：強(qiáng)連通圖：圖中任何一對(duì)頂點(diǎn)都是強(qiáng)連通的，則此圖叫強(qiáng)連通圖。連通分量連通分量：非連通圖中的每一個(gè)連通部分叫連通分量。強(qiáng)連通分量：強(qiáng)連通分量：有向圖中極大強(qiáng)連通子圖稱為有向圖的強(qiáng)連通分量。1111、生成樹(shù)、生成樹(shù)一個(gè)連通的生成樹(shù)，它含有圖中全部頂點(diǎn)，但只有足以構(gòu)成樹(shù)的n-1條邊（n頂點(diǎn)個(gè)數(shù)）如圖p15912. 12. 權(quán)、網(wǎng)權(quán)、網(wǎng)權(quán)：權(quán)： 有些圖對(duì)應(yīng)每條邊有一相應(yīng)的數(shù)值。這個(gè)數(shù)值叫該邊的權(quán)。網(wǎng)：網(wǎng)： 這種帶權(quán)的圖叫網(wǎng)。 注：不同網(wǎng)絡(luò)的權(quán)有不同的意義：電網(wǎng)絡(luò)權(quán)可以是阻抗，運(yùn)輸網(wǎng)絡(luò)中的權(quán)可以是路程長(zhǎng)度，運(yùn)費(fèi)等。 7.1.3 圖的幾種基本操作 (1) loc_vertex(g,v)(1) loc_

5、vertex(g,v)頂點(diǎn)定位函數(shù)頂點(diǎn)定位函數(shù) 頂點(diǎn)函數(shù): 確定頂點(diǎn)在圖g中的位置.若圖中無(wú)此頂點(diǎn)，則函數(shù)值為零.(2) get_vertex(g,i)(2) get_vertex(g,i)取頂點(diǎn)函數(shù)取頂點(diǎn)函數(shù) 取點(diǎn)函數(shù):求圖g中第i個(gè)頂點(diǎn).若i圖g中頂點(diǎn)數(shù)則函數(shù)值為零. (3) first_adj(g,v) (3) first_adj(g,v)求第一個(gè)鄰接點(diǎn)函數(shù)求第一個(gè)鄰接點(diǎn)函數(shù) 求第一個(gè)鄰接點(diǎn)函數(shù):求圖g中頂點(diǎn)v的第一個(gè)鄰接點(diǎn).若v沒(méi)有鄰接點(diǎn)或圖g中無(wú)頂點(diǎn)v,則函數(shù)值為零.p1567.2.1 鄰接矩陣表示法(數(shù)組表示法)鄰接矩陣表示法-表示各頂點(diǎn)之間的鄰接關(guān)系 可以借助二維數(shù)組作為存貯結(jié)構(gòu)

6、,故又稱為數(shù)組表示法. 7.2.2 7.2.2 鄰接表鄰接表 鄰接表是由鄰接矩陣改造而來(lái)的一種鏈接結(jié)構(gòu),它只考慮非零元素,因而節(jié)省了零元素所占的存貯空間. 逆鄰接表逆鄰接表 鏈表中每個(gè)結(jié)點(diǎn)表示鄰接矩陣中該頂點(diǎn)的列中每個(gè)非零元素 圖的存貯結(jié)構(gòu)說(shuō)明鄰接矩陣是一個(gè)n*n的方陣 ln為圖的頂點(diǎn)數(shù)l矩陣每一行分別對(duì)應(yīng)圖的各個(gè)頂點(diǎn)l矩陣的每一列分別對(duì)應(yīng)圖的各個(gè)頂點(diǎn) 1 規(guī)定矩陣元素aij= 0幾點(diǎn)說(shuō)明幾點(diǎn)說(shuō)明: :1.如果圖的各邊是帶權(quán)的,也可以用鄰接矩陣來(lái)表示,只需將矩陣中1元素?fù)Q成相應(yīng)邊的權(quán)值. 2.鄰接矩陣表示法對(duì)于以圖的頂點(diǎn)為主的運(yùn)算比較適用. 3.除完全圖外,其他圖的鄰接矩陣有許多零元素,特別是

7、當(dāng)n值較大,而邊數(shù)又少是,則此矩陣稱為稀疏矩陣.浪費(fèi)存儲(chǔ)空間. 鄰接表與鄰接矩陣的關(guān)系鄰接表與鄰接矩陣的關(guān)系: : 1.與鄰接矩陣的每一行有一個(gè)線形鏈接表.2.鏈接表的表頭對(duì)應(yīng)著鄰接矩陣該行的頂點(diǎn).3.鏈接表中的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)著鄰接矩陣正中該行的一個(gè)非零元素?zé)o向圖:一個(gè)非零元素表示與該行頂點(diǎn)相鄰接的另一個(gè)頂點(diǎn)有向圖:非零元素則表示該行頂點(diǎn)為起點(diǎn)的一條邊的終點(diǎn)幾點(diǎn)說(shuō)明幾點(diǎn)說(shuō)明: : 1. 1.在鄰接表中的每個(gè)線性鏈接表中各結(jié)在鄰接表中的每個(gè)線性鏈接表中各結(jié)點(diǎn)的的順序是任意的點(diǎn)的的順序是任意的. .2.2.鄰接表中的各個(gè)線性鏈接表不說(shuō)明它鄰接表中的各個(gè)線性鏈接表不說(shuō)明它們頂點(diǎn)之間的鄰接關(guān)系們頂點(diǎn)之間

8、的鄰接關(guān)系. .3.3.對(duì)于對(duì)于無(wú)向圖無(wú)向圖: : 某頂點(diǎn)的度數(shù)某頂點(diǎn)的度數(shù)= =該頂點(diǎn)對(duì)應(yīng)的線性鏈該頂點(diǎn)對(duì)應(yīng)的線性鏈表的結(jié)點(diǎn)數(shù)表的結(jié)點(diǎn)數(shù) 對(duì)于對(duì)于有向圖有向圖: : 某頂點(diǎn)的某頂點(diǎn)的 出度出度 數(shù)數(shù)= =該頂點(diǎn)對(duì)應(yīng)的線該頂點(diǎn)對(duì)應(yīng)的線性鏈表的結(jié)點(diǎn)數(shù)性鏈表的結(jié)點(diǎn)數(shù) 逆鄰接表逆鄰接表 鏈表中每個(gè)結(jié)點(diǎn)表示鄰接矩陣中該鏈表中每個(gè)結(jié)點(diǎn)表示鄰接矩陣中該頂點(diǎn)的列中每個(gè)非零元素頂點(diǎn)的列中每個(gè)非零元素 7.3 圖的遍歷什么叫圖的遍歷什么叫圖的遍歷 從圖的任意點(diǎn)出發(fā)沿著一些邊訪問(wèn)圖中的所有頂點(diǎn),且使每個(gè)頂點(diǎn)僅被訪問(wèn)一次,這就叫圖的遍歷.l深度優(yōu)先搜索深度優(yōu)先搜索dfsdfs l廣度優(yōu)先搜索廣度優(yōu)先搜索bfsbfs

9、 方法方法: : 從圖中指定的起點(diǎn)v0出發(fā)(先訪問(wèn)v)訪問(wèn)它的任意相鄰接的頂點(diǎn)w1,再訪問(wèn)w1的任一個(gè)未訪問(wèn)的相鄰接頂點(diǎn)w2,如此下去,直到某頂點(diǎn)已無(wú)被訪問(wèn)過(guò)的頂點(diǎn),則返回一步找前一個(gè)頂點(diǎn)的其他沿未被訪問(wèn)的鄰接頂點(diǎn),重復(fù)以上過(guò)程直到所有的頂點(diǎn)都被訪問(wèn) 例：頂點(diǎn)的訪問(wèn)序列：v1v2v4v8v5v3v6v7方法方法: : 從圖指定的起點(diǎn)v0出發(fā),訪問(wèn)與它相鄰的所有頂點(diǎn)w1,w2,.然后再依次訪問(wèn)w1,w2.鄰接的尚未被訪問(wèn)的所有頂點(diǎn),再?gòu)倪@些頂點(diǎn)出發(fā)訪問(wèn)與它們相鄰接的尚未被訪問(wèn)的頂點(diǎn),直到所有頂點(diǎn)均被訪問(wèn)過(guò)為止. 例：頂點(diǎn)的訪問(wèn)序列：v1v2v3v4v5v6v7v87.4 圖的最小生成樹(shù)7.4.1

10、 無(wú)向圖的連通分量和生成樹(shù)無(wú)向圖的連通分量和生成樹(shù) 1. 1. 連通分量連通分量 非連通圖的每一個(gè)連通部分叫連通分量. p159 g3 圖7.3(a) 鄰接表說(shuō)明：說(shuō)明： 該圖中包括三個(gè)連通分量，若按dfs分別從三個(gè)頂點(diǎn)（i，d，b）出發(fā)可得到三個(gè)連通分量的頂點(diǎn)序列：i，g，k，hd，eb，m，l，j，a，f，c 2. 圖的生成樹(shù)圖的生成樹(shù) 圖中全部頂點(diǎn)和搜索過(guò)程所經(jīng)過(guò)的邊,構(gòu)成該連通圖的生成樹(shù). 例如上圖搜索遍歷后得到的三棵樹(shù) 由此可以總結(jié)生成樹(shù)的特點(diǎn)由此可以總結(jié)生成樹(shù)的特點(diǎn): 任意兩個(gè)頂點(diǎn)之間有且僅有一條路徑如再增加一條邊,就會(huì)出現(xiàn)一條回路,如果去掉一條邊此子圖就會(huì)變成非連通圖. 7.4.

11、2 最小生成樹(shù)最小生成樹(shù) 1 什么叫最小生成樹(shù)什么叫最小生成樹(shù) 給定一個(gè)帶權(quán)的無(wú)向連通圖,如何選取一棵生成樹(shù),使樹(shù)上所有邊上權(quán)的總和為最小,這叫最小生成樹(shù). 2.求最小生成樹(shù)的算法求最小生成樹(shù)的算法 (1)克魯斯卡爾算法 (2)普里姆算法 例：克魯斯卡爾算法克魯斯卡爾算法 方法:將圖中邊按其權(quán)值由小到大的次序順序選取,若選邊后不形成回路,則保留作為一條邊,若形成回路則除去.依次選夠(n-1)條邊,即得最小生成樹(shù).(n為頂點(diǎn)數(shù)) 分析：該方法對(duì)于邊相對(duì)比較多的不是很實(shí)用,浪費(fèi)時(shí)間. 普里姆算法普里姆算法 方法:從指定頂點(diǎn)開(kāi)始將它加入集合中,然后將集合內(nèi)的頂點(diǎn)與集合外的頂點(diǎn)所構(gòu)成的所有邊中選取權(quán)值

12、最小的一條邊作為生成樹(shù)的邊,并將集合外的那個(gè)頂點(diǎn)加入到集合中,表示該頂點(diǎn)已連通.再用集合內(nèi)的頂點(diǎn)與集合外的頂點(diǎn)構(gòu)成的邊中找最小的邊,并將相應(yīng)的頂點(diǎn)加入集合中,如此下去直到全部頂點(diǎn)都加入到集合中,即得最小生成樹(shù). 有向無(wú)環(huán)圖有向無(wú)環(huán)圖: 是一個(gè)無(wú)環(huán)的有向圖.簡(jiǎn)稱dag圖. 有向無(wú)環(huán)圖的作用有向無(wú)環(huán)圖的作用: 常用來(lái)描述一個(gè)工程或一個(gè)系統(tǒng)的進(jìn)行的過(guò)程. 7.5.1 aov網(wǎng)網(wǎng) 有向無(wú)環(huán)圖可以描述一個(gè)過(guò)程或一個(gè)系統(tǒng).那么在一個(gè)過(guò)程或一個(gè)系統(tǒng)中又可以映射多個(gè)子過(guò)程或子系統(tǒng).比如我們熟悉的教學(xué)計(jì)劃,一個(gè)教學(xué)計(jì)劃中又可以包含許多課程(子計(jì)劃),當(dāng)這些子計(jì)劃都完成后,整個(gè)教學(xué)計(jì)劃方算完成.我們可以把每個(gè)子計(jì)

13、劃稱為活動(dòng). 說(shuō)明：說(shuō)明： 在各個(gè)活動(dòng)之間,有些必須按規(guī)定的先后次序進(jìn)行,有些則沒(méi)有次序要求. 把這種活動(dòng)之間的次序要求,可用一個(gè)有向圖來(lái)表示. 圖中每個(gè)頂點(diǎn)代表一個(gè)活動(dòng).如果從頂點(diǎn)vi到頂點(diǎn)vj之間存在有向邊則表示活動(dòng)i必須先于活動(dòng)j進(jìn)行.這種圖中用頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)稱為稱為aov網(wǎng)網(wǎng). aov網(wǎng)的特點(diǎn)網(wǎng)的特點(diǎn):在網(wǎng)中一定不能有有向回路. 檢測(cè)網(wǎng)中是否存在環(huán),可用拓?fù)渑判蛲負(fù)渑判虻姆椒? 1.什么叫拓?fù)渑判蚴裁唇型負(fù)渑判?將aov網(wǎng)中各個(gè)頂點(diǎn)排列成一個(gè)有序序列,使得所有前驅(qū)和后繼關(guān)系都能得到滿足,而那些沒(méi)有次序的頂點(diǎn),在拓?fù)渑判虻男蛄兄锌梢圆宓饺我馕恢?也可說(shuō)拓?fù)渑判蚴菍?duì)非線形結(jié)構(gòu)的有向圖進(jìn)

14、行線形化的重要手段. 2.拓?fù)渑判虻姆椒ㄍ負(fù)渑判虻姆椒?由aov網(wǎng)選取某個(gè)沒(méi)有前驅(qū)的頂點(diǎn),排到序列中,凡取出某頂點(diǎn),即將它與它相關(guān)聯(lián)的邊從圖中刪掉,隨著邊的刪除,又會(huì)有無(wú)前驅(qū)的頂點(diǎn),重復(fù)如此進(jìn)行,直到全部頂點(diǎn)都排到序列中去. 例：如圖p181圖7.27 aoe網(wǎng)(activity on edge network)，即邊表示活動(dòng)的網(wǎng)絡(luò)，與aov網(wǎng)相對(duì)應(yīng)的是。它通常表示一個(gè)工程的計(jì)劃或進(jìn)度。 aoe網(wǎng)是一個(gè)有向帶權(quán)圖有向帶權(quán)圖，圖中的： 邊：表示活動(dòng)(子工程)， 邊上的權(quán)：表示該活動(dòng)的持續(xù)時(shí)間，即完成該活動(dòng)所需要的時(shí)間； 頂點(diǎn)：表示事件事件，每個(gè)事件是活動(dòng)之間的轉(zhuǎn)接點(diǎn)，即表示它的所有入邊活動(dòng)到此完

15、成，所有出邊活動(dòng)從此開(kāi)始。 其中有兩個(gè)特殊的頂點(diǎn)兩個(gè)特殊的頂點(diǎn)(事件事件)，一個(gè)稱做源點(diǎn)源點(diǎn)，它表示整個(gè)工程的開(kāi)始，亦即最早活動(dòng)的起點(diǎn)，顯然它只有出邊，沒(méi)有入邊；另一個(gè)稱做匯點(diǎn)匯點(diǎn)，它表示整個(gè)工程的結(jié)束，亦即最后活動(dòng)的終點(diǎn)，顯然它只有入邊，沒(méi)有出邊。除這兩個(gè)頂點(diǎn)外，其余頂點(diǎn)都既有入邊，也有出邊，是入邊活動(dòng)和出邊活動(dòng)的轉(zhuǎn)接點(diǎn)。 在一個(gè)aoe網(wǎng)中，若包含有n個(gè)事件，通常令源點(diǎn)為第0個(gè)事件，匯點(diǎn)為第n-1個(gè)事件，其余事件的編號(hào)(即頂點(diǎn)序號(hào))分別為1n-2。 一個(gè)aoe網(wǎng)如圖，該網(wǎng)中包含有 活動(dòng)和 事件。 如圖p183圖7.29一個(gè)aov網(wǎng)11項(xiàng)9個(gè) (1)(1)整個(gè)工程至少需要多長(zhǎng)時(shí)間完成整個(gè)工程至

16、少需要多長(zhǎng)時(shí)間完成? ?(2)(2)哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵? ? 在aoe網(wǎng)中，一個(gè)頂點(diǎn)事件的發(fā)生或出現(xiàn)必須在它的所有入邊活動(dòng)(或稱前驅(qū)活動(dòng))都完成之后，即只要有一個(gè)入邊活動(dòng)沒(méi)有完成，該事件就不可能發(fā)生。所以： 一個(gè)事件的最早發(fā)生時(shí)間一個(gè)事件的最早發(fā)生時(shí)間是它的所有入邊活動(dòng)，或者說(shuō)最后一個(gè)入邊活動(dòng)剛完成的時(shí)間。 一個(gè)活動(dòng)的開(kāi)始必須在它的起點(diǎn)事件發(fā)生之后，也就是說(shuō)，一個(gè)頂點(diǎn)事件沒(méi)有發(fā)生時(shí)，它的所有出邊活動(dòng)(或稱后繼活動(dòng))都不可能開(kāi)始，所以： 一個(gè)活動(dòng)的最早開(kāi)始時(shí)間一個(gè)活動(dòng)的最早開(kāi)始時(shí)間是它的起點(diǎn)事件的最早發(fā)生時(shí)間。若用vej表示頂點(diǎn)vj事件的最早發(fā)生時(shí)間，用ei

17、表示vj一條出邊活動(dòng)ai的最早開(kāi)始時(shí)間，則有ei=vej。 對(duì)于源點(diǎn)事件來(lái)說(shuō)，因?yàn)樗鼪](méi)有入邊，所以隨時(shí)都可以發(fā)生，整個(gè)工程的開(kāi)始時(shí)間就是它的發(fā)生時(shí)間，亦即最早發(fā)生時(shí)間，通常把此時(shí)間定義為0，從此開(kāi)始推出其他事件的最早發(fā)生時(shí)間。例：分析圖7.29 事件的最遲發(fā)生時(shí)間事件的最遲發(fā)生時(shí)間：在不影響整個(gè)工程按時(shí)完成的前提下，一些事件可以不在最早發(fā)生時(shí)間發(fā)生，而允許向后推遲一些時(shí)間發(fā)生，我們把最晚必須發(fā)生的時(shí)間叫做該事件的最遲發(fā)生時(shí)間事件的最遲發(fā)生時(shí)間。 同樣，在不影響整個(gè)工程按時(shí)完成的前提下，一些活動(dòng)可以不在最早開(kāi)始時(shí)間開(kāi)始，而允許向后推遲一些時(shí)間開(kāi)始，我們把最晚必須開(kāi)始的時(shí)間叫做該活動(dòng)的最遲開(kāi)始時(shí)間

18、最遲開(kāi)始時(shí)間。aoe網(wǎng)中的任一個(gè)事件若在最遲發(fā)生時(shí)間仍沒(méi)有發(fā)生或任一項(xiàng)活動(dòng)在最遲開(kāi)始時(shí)間仍沒(méi)有開(kāi)始，則必將影響整個(gè)工程的按時(shí)完成，使工期拖延。5根據(jù)根據(jù)aoe網(wǎng)中每個(gè)事件的最早發(fā)生時(shí)網(wǎng)中每個(gè)事件的最早發(fā)生時(shí)間和最遲發(fā)生時(shí)間計(jì)算出每個(gè)活動(dòng)的最間和最遲發(fā)生時(shí)間計(jì)算出每個(gè)活動(dòng)的最早開(kāi)始時(shí)間和最遲開(kāi)始時(shí)間。早開(kāi)始時(shí)間和最遲開(kāi)始時(shí)間。 有些活動(dòng)的開(kāi)始時(shí)間余量不為0，表明這些活動(dòng)不在最早開(kāi)始時(shí)間開(kāi)始，至多向后拖延相應(yīng)的開(kāi)始時(shí)間余量所規(guī)定的時(shí)間開(kāi)始也不會(huì)延誤整個(gè)工程的進(jìn)展。如對(duì)于活動(dòng)a5，它最早可以從整個(gè)工程開(kāi)工后的第4天開(kāi)始，至多向后拖延兩天，即從第6天開(kāi)始。 有些活動(dòng)的開(kāi)始時(shí)間余量為0，表明這些活動(dòng)只能在最早開(kāi)始時(shí)間開(kāi)始，并且必須在持續(xù)時(shí)間內(nèi)按時(shí)完成，否則將拖延整個(gè)工期。我們把開(kāi)始時(shí)間余量為0的活動(dòng)稱為關(guān)鍵