數(shù)據(jù)結構演示稿第一頁，共五十二頁，編輯于2023年，星期三

第7章圖

內容7.1圖的概念7.2圖的存貯結構7.3圖的遍歷7.4圖的最小生成樹7.5拓撲排序7.6關鍵路徑7.7最短路徑第二頁，共五十二頁，編輯于2023年，星期三7.1圖的概念7.1.1圖的定義每個結點有任意多個前驅和后繼結點.圖也可以二元組表示:

定義Graph=(v,E)v:表示元素集合E:元素之間的關系

現(xiàn)舉兩個例子，如下圖：[例一][例二]

無向圖中（1，2）和（2，1）代表同一邊

有向圖中<1,2>和<2,1>表示兩個不同的方向邊

以<1,2>為例，在<1,2>中：

1稱為此邊的起點或尾（弧尾）

2稱為此邊的終點或頭（弧頭）

邊的方向規(guī)定為弧尾——〉弧頭第三頁，共五十二頁，編輯于2023年，星期三V(G1)={1,2,3,4}頂點集合;

E(G1)={<1,2>,<1,3>,<3,4>,<4,1>}邊的集合（頂點關系）V(G2)={1,2,3,4,5}頂點集合;

E(G2)={(1,2),(1,4),(2,3),(2,5),(3,4),(3,5)}邊的集合

第四頁，共五十二頁，編輯于2023年，星期三7.1.2圖的基本術語1、完全圖：在一個有N個頂點的圖中，若每個頂點到其它（N-1）頂點都有一條邊，則圖中有N個頂點且有（N*（N-1）/2）條邊的圖稱為完全圖。

2、鄰接點：對無向圖G=（V，E），若有（V1，V2）屬于E則稱V1和V2互為鄰接點。

3、相關邊：兩個相鄰接的點連成的邊叫做這兩個結點的相關邊。第五頁，共五十二頁，編輯于2023年，星期三4、度：與每個頂點相連的邊的數(shù)叫該點的度。5、入度：對有向圖中某結點的弧頭數(shù)（邊的終點）稱為該結點的入度。6、出度：對有向圖中某結點的弧尾數(shù)（邊的終點）稱為該結點的出度。7、路徑：在一圖中若從某個頂點VP出發(fā)，沿著一些邊經過頂點V1，V2，…,VM到達VG則稱頂點

8、回路：從一頂點出發(fā)又回到該頂點，則所經過的路徑稱為回路。

第六頁，共五十二頁，編輯于2023年，星期三9、子圖

若G和G'是兩個圖，且存在著V(G')≤V(G)和E（G’）≤E（G）的關系，則稱G’是G的子圖10、有關連通的概念連通：在無向圖中，若從頂點VI到頂點VJ之間有路徑則稱此二頂點是連通的。連通圖：如果圖中任意一對頂點之間都是連通的，則稱此圖為連通圖。強連通：對于有向圖，若從頂點VI到頂點VJ到頂點VI之間都有路徑，則稱這兩點是強連通的。強連通圖：圖中任何一對頂點都是強連通的，則此圖叫強連通圖。第七頁，共五十二頁，編輯于2023年，星期三連通分量：非連通圖中的每一個連通部分叫連通分量。強連通分量：有向圖中極大強連通子圖稱為有向圖的強連通分量。11、生成樹一個連通的生成樹，它含有圖中全部頂點，但只有足以構成樹的N-1條邊（N頂點個數(shù)）如圖P159第八頁，共五十二頁，編輯于2023年，星期三12.權、網權：有些圖對應每條邊有一相應的數(shù)值。這個數(shù)值叫該邊的權。網：這種帶權的圖叫網。注：不同網絡的權有不同的意義：電網絡權可以是阻抗，運輸網絡中的權可以是路程長度，運費等。

第九頁，共五十二頁，編輯于2023年，星期三7.1.3圖的幾種基本操作(1)LOC_VERTEX(G,v)頂點定位函數(shù)

頂點函數(shù):確定頂點在圖G中的位置.若圖中無此頂點，則函數(shù)值為零.(2)GET_VERTEX(G,i)取頂點函數(shù)

取點函數(shù):求圖G中第i個頂點.若i>圖G中頂點數(shù)則函數(shù)值為零.(3)FIRST_ADJ(G,v)求第一個鄰接點函數(shù)

求第一個鄰接點函數(shù):求圖G中頂點V的第一個鄰接點.若v沒有鄰接點或圖G中無頂點v,則函數(shù)值為零.……P156第十頁，共五十二頁，編輯于2023年，星期三7.2圖的存貯結構7.2.1鄰接矩陣表示法(數(shù)組表示法)鄰接矩陣表示法--表示各頂點之間的鄰接關系可以借助二維數(shù)組作為存貯結構,故又稱為數(shù)組表示法.

第十一頁，共五十二頁，編輯于2023年，星期三7.2.2鄰接表鄰接表是由鄰接矩陣改造而來的一種鏈接結構,它只考慮非零元素,因而節(jié)省了零元素所占的存貯空間.

逆鄰接表

鏈表中每個結點表示鄰接矩陣中該頂點的列中每個非零元素

第十二頁，共五十二頁，編輯于2023年，星期三圖的存貯結構說明鄰接矩陣是一個n*n的方陣n為圖的頂點數(shù)

矩陣每一行分別對應圖的各個頂點

矩陣的每一列分別對應圖的各個頂點1規(guī)定矩陣元素aij=0第十三頁，共五十二頁，編輯于2023年，星期三幾點說明:

1.如果圖的各邊是帶權的,也可以用鄰接矩陣來表示,只需將矩陣中1元素換成相應邊的權值.

2.鄰接矩陣表示法對于以圖的頂點為主的運算比較適用.

3.除完全圖外,其他圖的鄰接矩陣有許多零元素,特別是當n值較大,而邊數(shù)又少是,則此矩陣稱為"稀疏矩陣".浪費存儲空間.

第十四頁，共五十二頁，編輯于2023年，星期三鄰接表與鄰接矩陣的關系:1.與鄰接矩陣的每一行有一個線形鏈接表.

2.鏈接表的表頭對應著鄰接矩陣該行的頂點.

3.鏈接表中的每個結點對應著鄰接矩陣正中該行的一個非零元素

無向圖:一個非零元素表示與該行頂點相鄰接的另一個頂點

有向圖:非零元素則表示該行頂點為起點的一條邊的終點第十五頁，共五十二頁，編輯于2023年，星期三幾點說明:1.在鄰接表中的每個線性鏈接表中各結點的的順序是任意的.

2.鄰接表中的各個線性鏈接表不說明它們頂點之間的鄰接關系.

3.對于無向圖:

某頂點的度數(shù)=該頂點對應的線性鏈表的結點數(shù)

對于有向圖:

某頂點的"出度"數(shù)=該頂點對應的線性鏈表的結點數(shù)

第十六頁，共五十二頁，編輯于2023年，星期三逆鄰接表鏈表中每個結點表示鄰接矩陣中該頂點的列中每個非零元素

第十七頁，共五十二頁，編輯于2023年，星期三7.3圖的遍歷什么叫圖的遍歷

從圖的任意點出發(fā)沿著一些邊訪問圖中的所有頂點,且使每個頂點僅被訪問一次,這就叫圖的遍歷.

第十八頁，共五十二頁，編輯于2023年，星期三圖的遍歷的兩種方法

深度優(yōu)先搜索dfs

廣度優(yōu)先搜索bfs

第十九頁，共五十二頁，編輯于2023年，星期三1.深度優(yōu)先搜索dfs

方法:

從圖中指定的起點v0出發(fā)(先訪問v)訪問它的任意相鄰接的頂點w1,再訪問w1的任一個未訪問的相鄰接頂點w2,如此下去,直到某頂點已無被訪問過的頂點,則返回一步找前一個頂點的其他沿未被訪問的鄰接頂點,重復以上過程直到所有的頂點都被訪問

第二十頁，共五十二頁，編輯于2023年，星期三例：頂點的訪問序列：V1V2V4V8V5V3V6V7第二十一頁，共五十二頁，編輯于2023年，星期三2.廣度優(yōu)先搜索bfs

方法:

從圖指定的起點v0出發(fā),訪問與它相鄰的所有頂點w1,w2,.....然后再依次訪問w1,w2......鄰接的尚未被訪問的所有頂點,再從這些頂點出發(fā)訪問與它們相鄰接的尚未被訪問的頂點,直到所有頂點均被訪問過為止.

第二十二頁，共五十二頁，編輯于2023年，星期三例：頂點的訪問序列：V1V2V3V4V5V6V7V8第二十三頁，共五十二頁，編輯于2023年，星期三7.4圖的最小生成樹

7.4.1無向圖的連通分量和生成樹

1.連通分量

非連通圖的每一個連通部分叫連通分量.

第二十四頁，共五十二頁，編輯于2023年，星期三P159G3圖7.3(a)鄰接表第二十五頁，共五十二頁，編輯于2023年，星期三說明：該圖中包括三個連通分量，若按dfs分別從三個頂點（I，D，B）出發(fā)可得到三個連通分量的頂點序列：

I，G，K，H

D，E

B，M，L，J，A，F(xiàn)，C

第二十六頁，共五十二頁，編輯于2023年，星期三2.圖的生成樹

圖中全部頂點和搜索過程所經過的邊,構成該連通圖的生成樹.

例如上圖搜索遍歷后得到的三棵樹

第二十七頁，共五十二頁，編輯于2023年，星期三

由此可以總結生成樹的特點:

任意兩個頂點之間有且僅有一條路徑如再增加一條邊,就會出現(xiàn)一條回路,如果去掉一條邊此子圖就會變成非連通圖.

第二十八頁，共五十二頁，編輯于2023年，星期三7.4.2最小生成樹

1什么叫最小生成樹

給定一個帶權的無向連通圖,如何選取一棵生成樹,使樹上所有邊上權的總和為最小,這叫最小生成樹.

2.求最小生成樹的算法

克魯斯卡爾算法普里姆算法第二十九頁，共五十二頁，編輯于2023年，星期三例：第三十頁，共五十二頁，編輯于2023年，星期三克魯斯卡爾算法方法:將圖中邊按其權值由小到大的次序順序選取,若選邊后不形成回路,則保留作為一條邊,若形成回路則除去.依次選夠(n-1)條邊,即得最小生成樹.(n為頂點數(shù))

分析：該方法對于邊相對比較多的不是很實用,浪費時間.

第三十一頁，共五十二頁，編輯于2023年，星期三普里姆算法

方法:從指定頂點開始將它加入集合中,然后將集合內的頂點與集合外的頂點所構成的所有邊中選取權值最小的一條邊作為生成樹的邊,并將集合外的那個頂點加入到集合中,表示該頂點已連通.再用集合內的頂點與集合外的頂點構成的邊中找最小的邊,并將相應的頂點加入集合中,如此下去直到全部頂點都加入到集合中,即得最小生成樹.第三十二頁，共五十二頁，編輯于2023年，星期三7.5有向無環(huán)圖及其應用

有向無環(huán)圖:是一個無環(huán)的有向圖.簡稱DAG圖.

有向無環(huán)圖的作用:常用來描述一個工程或一個系統(tǒng)的進行的過程.第三十三頁，共五十二頁，編輯于2023年，星期三7.5.1AOV網

有向無環(huán)圖可以描述一個過程或一個系統(tǒng).那么在一個過程或一個系統(tǒng)中又可以映射多個子過程或子系統(tǒng).比如我們熟悉的教學計劃,一個教學計劃中又可以包含許多課程(子計劃),當這些子計劃都完成后,整個教學計劃方算完成.我們可以把每個子計劃稱為活動.

第三十四頁，共五十二頁，編輯于2023年，星期三說明：在各個活動之間,有些必須按規(guī)定的先后次序進行,有些則沒有次序要求.

把這種活動之間的次序要求,可用一個有向圖來表示.

圖中每個頂點代表一個活動.如果從頂點vi到頂點vj之間存在有向邊<vi,vj>則表示活動i必須先于活動j進行.這種圖中用頂點表示活動的網絡稱為AOV網.

AOV網的特點:在網中一定不能有有向回路.

檢測網中是否存在環(huán),可用拓撲排序的方法.第三十五頁，共五十二頁，編輯于2023年，星期三7.5.2拓撲排序

1.什么叫拓撲排序

將AOV網中各個頂點排列成一個有序序列,使得所有前驅和后繼關系都能得到滿足,而那些沒有次序的頂點,在拓撲排序的序列中可以插到任意位置.也可說拓撲排序是對非線形結構的有向圖進行線形化的重要手段.第三十六頁，共五十二頁，編輯于2023年，星期三2.拓撲排序的方法

由AOV網選取某個沒有前驅的頂點,排到序列中,凡取出某頂點,即將它與它相關聯(lián)的邊從圖中刪掉,隨著邊的刪除,又會有無前驅的頂點,重復如此進行,直到全部頂點都排到序列中去.例：如圖P181圖7.27第三十七頁，共五十二頁，編輯于2023年，星期三7.6關鍵路徑

AOE網(ActivityOnEdgenetwork)，即邊表示活動的網絡，與AOV網相對應的是。它通常表示一個工程的計劃或進度。AOE網是一個有向帶權圖，圖中的：

邊：表示活動(子工程)，

邊上的權：表示該活動的持續(xù)時間，即完成該活動所需要的時間；

頂點：表示事件，每個事件是活動之間的轉接點，即表示它的所有入邊活動到此完成，所有出邊活動從此開始。第三十八頁，共五十二頁，編輯于2023年，星期三

其中有兩個特殊的頂點(事件)，一個稱做源點，它表示整個工程的開始，亦即最早活動的起點，顯然它只有出邊，沒有入邊；另一個稱做匯點，它表示整個工程的結束，亦即最后活動的終點，顯然它只有入邊，沒有出邊。除這兩個頂點外，其余頂點都既有入邊，也有出邊，是入邊活動和出邊活動的轉接點。第三十九頁，共五十二頁，編輯于2023年，星期三

在一個AOE網中，若包含有n個事件，通常令源點為第0個事件，匯點為第n-1個事件，其余事件的編號(即頂點序號)分別為1~n-2。

一個AOE網如圖，該網中包含有活動和事件。如圖P183圖7.29一個AOV網11項9個第四十頁，共五十二頁，編輯于2023年，星期三

對于一個AOE網，待研究的問題是：

(1)整個工程至少需要多長時間完成?

(2)哪些活動是影響工程進度的關鍵?

第四十一頁，共五十二頁，編輯于2023年，星期三1．事件的最早發(fā)生時間與活動的最早開始時間的關系

在AOE網中，一個頂點事件的發(fā)生或出現(xiàn)必須在它的所有入邊活動(或稱前驅活動)都完成之后，即只要有一個入邊活動沒有完成，該事件就不可能發(fā)生。所以：

一個事件的最早發(fā)生時間是它的所有入邊活動，或者說最后一個入邊活動剛完成的時間。

一個活動的開始必須在它的起點事件發(fā)生之后，也就是說，一個頂點事件沒有發(fā)生時，它的所有出邊活動(或稱后繼活動)都不可能開始，所以：

一個活動的最早開始時間是它的起點事件的最早發(fā)生時間。若用ve[j]表示頂點vj事件的最早發(fā)生時間，用e[i]表示vj一條出邊活動ai的最早開始時間，則有e[i]=ve[j]。

第四十二頁，共五十二頁，編輯于2023年，星期三2．求事件的最早發(fā)生時間

對于源點事件來說，因為它沒有入邊，所以隨時都可以發(fā)生，整個工程的開始時間就是它的發(fā)生時間，亦即最早發(fā)生時間，通常把此時間定義為0，從此開始推出其他事件的最早發(fā)生時間。

例：分析圖7.29

第四十三頁，共五十二頁，編輯于2023年，星期三3．事件的最遲發(fā)生時間與活動的最遲開始時間的關系

事件的最遲發(fā)生時間：在不影響整個工程按時完成的前提下，一些事件可以不在最早發(fā)生時間發(fā)生，而允許向后推遲一些時間發(fā)生，我們把最晚必須發(fā)生的時間叫做該事件的最遲發(fā)生時間。

同樣，在不影響整個工程按時完成的前提下，一些活動可以不在最早開始時間開始，而允許向后推遲一些時間開始，我們把最晚必須開始的時間叫做該活動的最遲開始時間。AOE網中的任一個事件若在最遲發(fā)生時間仍沒有發(fā)生或任一項活動在最遲開始時間仍沒有開始，則必將影響整個工程的按時完成，使工期拖延。

第四十四頁，共五十二頁，編輯于2023年，星期三4．求事件的最遲發(fā)生時間

dut(<j，k>)表示邊<j，k>上的權

5．根據(jù)AOE網中每個事件的最早發(fā)生時間和最遲發(fā)生時間計算出每個活動的最早開始時間和最遲開始時間。

第四十五頁，共五十二頁，編輯于2023年，星期三關鍵路徑有些活動的開始時間余量不為0，表明這些活動不在最早開始時間開始，至多向后拖延相應的開始時間余量所規(guī)定的時間開始也不會延誤整個工程的進展。如對于活動a5，它最早可以從整個工程開工后的第4天開始，至多向后拖延兩天，即從第6天開始。

有些活動的開始時間余量為0，表明這些活動只能在最早開始時間開始，并且必須在持續(xù)時間內按時完成，否則將拖延整個工期。我們把開始時間余量為0的活動稱為關鍵活動，由關鍵活動所形成的從源點到匯點的每一條路徑稱為關鍵路徑。

第四十六頁，共五十二頁，編輯于2023年，星期三

關鍵路徑實際上就是從源點到匯點具有最長路徑長度的那些路徑，即最長路徑。這很容易理解，因為整個工程的工期就是按照最長路徑長度計算出來的，即等于該路徑