數(shù)據(jù)結(jié)構(gòu)演示稿

數(shù)據(jù)結(jié)構(gòu)演示稿第1頁，課件共52頁，創(chuàng)作于2023年2月

第7章圖

內(nèi)容7.1圖的概念7.2圖的存貯結(jié)構(gòu)7.3圖的遍歷7.4圖的最小生成樹7.5拓?fù)渑判?.6關(guān)鍵路徑7.7最短路徑第2頁，課件共52頁，創(chuàng)作于2023年2月7.1圖的概念7.1.1圖的定義每個結(jié)點(diǎn)有任意多個前驅(qū)和后繼結(jié)點(diǎn).圖也可以二元組表示:

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

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

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

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

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

1稱為此邊的起點(diǎn)或尾（弧尾）

2稱為此邊的終點(diǎn)或頭（弧頭）

邊的方向規(guī)定為弧尾——〉弧頭第3頁，課件共52頁，創(chuàng)作于2023年2月V(G1)={1,2,3,4}頂點(diǎn)集合;

E(G1)={<1,2>,<1,3>,<3,4>,<4,1>}邊的集合（頂點(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)}邊的集合

第4頁，課件共52頁，創(chuàng)作于2023年2月7.1.2圖的基本術(shù)語1、完全圖：在一個有N個頂點(diǎn)的圖中，若每個頂點(diǎn)到其它（N-1）頂點(diǎn)都有一條邊，則圖中有N個頂點(diǎn)且有（N*（N-1）/2）條邊的圖稱為完全圖。

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

3、相關(guān)邊：兩個相鄰接的點(diǎn)連成的邊叫做這兩個結(jié)點(diǎn)的相關(guān)邊。第5頁，課件共52頁，創(chuàng)作于2023年2月4、度：與每個頂點(diǎn)相連的邊的數(shù)叫該點(diǎn)的度。5、入度：對有向圖中某結(jié)點(diǎn)的弧頭數(shù)（邊的終點(diǎn)）稱為該結(jié)點(diǎn)的入度。6、出度：對有向圖中某結(jié)點(diǎn)的弧尾數(shù)（邊的終點(diǎn)）稱為該結(jié)點(diǎn)的出度。7、路徑：在一圖中若從某個頂點(diǎn)VP出發(fā)，沿著一些邊經(jīng)過頂點(diǎn)V1，V2，…,VM到達(dá)VG則稱頂點(diǎn)

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

第6頁，課件共52頁，創(chuàng)作于2023年2月9、子圖

若G和G'是兩個圖，且存在著V(G')≤V(G)和E（G’）≤E（G）的關(guān)系，則稱G’是G的子圖10、有關(guān)連通的概念連通：在無向圖中，若從頂點(diǎn)VI到頂點(diǎn)VJ之間有路徑則稱此二頂點(diǎn)是連通的。連通圖：如果圖中任意一對頂點(diǎn)之間都是連通的，則稱此圖為連通圖。強(qiáng)連通：對于有向圖，若從頂點(diǎn)VI到頂點(diǎn)VJ到頂點(diǎn)VI之間都有路徑，則稱這兩點(diǎn)是強(qiáng)連通的。強(qiáng)連通圖：圖中任何一對頂點(diǎn)都是強(qiáng)連通的，則此圖叫強(qiáng)連通圖。第7頁，課件共52頁，創(chuàng)作于2023年2月連通分量：非連通圖中的每一個連通部分叫連通分量。強(qiáng)連通分量：有向圖中極大強(qiáng)連通子圖稱為有向圖的強(qiáng)連通分量。11、生成樹一個連通的生成樹，它含有圖中全部頂點(diǎn)，但只有足以構(gòu)成樹的N-1條邊（N頂點(diǎn)個數(shù)）如圖P159第8頁，課件共52頁，創(chuàng)作于2023年2月12.權(quán)、網(wǎng)權(quán)：有些圖對應(yīng)每條邊有一相應(yīng)的數(shù)值。這個數(shù)值叫該邊的權(quán)。網(wǎng)：這種帶權(quán)的圖叫網(wǎng)。注：不同網(wǎng)絡(luò)的權(quán)有不同的意義：電網(wǎng)絡(luò)權(quán)可以是阻抗，運(yùn)輸網(wǎng)絡(luò)中的權(quán)可以是路程長度，運(yùn)費(fèi)等。

第9頁，課件共52頁，創(chuàng)作于2023年2月7.1.3圖的幾種基本操作(1)LOC_VERTEX(G,v)頂點(diǎn)定位函數(shù)

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

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

求第一個鄰接點(diǎn)函數(shù):求圖G中頂點(diǎn)V的第一個鄰接點(diǎn).若v沒有鄰接點(diǎn)或圖G中無頂點(diǎn)v,則函數(shù)值為零.……P156第10頁，課件共52頁，創(chuàng)作于2023年2月7.2圖的存貯結(jié)構(gòu)7.2.1鄰接矩陣表示法(數(shù)組表示法)鄰接矩陣表示法--表示各頂點(diǎn)之間的鄰接關(guān)系可以借助二維數(shù)組作為存貯結(jié)構(gòu),故又稱為數(shù)組表示法.

第11頁，課件共52頁，創(chuàng)作于2023年2月7.2.2鄰接表鄰接表是由鄰接矩陣改造而來的一種鏈接結(jié)構(gòu),它只考慮非零元素,因而節(jié)省了零元素所占的存貯空間.

逆鄰接表

鏈表中每個結(jié)點(diǎn)表示鄰接矩陣中該頂點(diǎn)的列中每個非零元素

第12頁，課件共52頁，創(chuàng)作于2023年2月圖的存貯結(jié)構(gòu)說明鄰接矩陣是一個n*n的方陣n為圖的頂點(diǎn)數(shù)

矩陣每一行分別對應(yīng)圖的各個頂點(diǎn)

矩陣的每一列分別對應(yīng)圖的各個頂點(diǎn)1規(guī)定矩陣元素aij=0第13頁，課件共52頁，創(chuàng)作于2023年2月幾點(diǎn)說明:

1.如果圖的各邊是帶權(quán)的,也可以用鄰接矩陣來表示,只需將矩陣中1元素?fù)Q成相應(yīng)邊的權(quán)值.

2.鄰接矩陣表示法對于以圖的頂點(diǎn)為主的運(yùn)算比較適用.

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

第14頁，課件共52頁，創(chuàng)作于2023年2月鄰接表與鄰接矩陣的關(guān)系:1.與鄰接矩陣的每一行有一個線形鏈接表.

2.鏈接表的表頭對應(yīng)著鄰接矩陣該行的頂點(diǎn).

3.鏈接表中的每個結(jié)點(diǎn)對應(yīng)著鄰接矩陣正中該行的一個非零元素

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

有向圖:非零元素則表示該行頂點(diǎn)為起點(diǎn)的一條邊的終點(diǎn)第15頁，課件共52頁，創(chuàng)作于2023年2月幾點(diǎn)說明:1.在鄰接表中的每個線性鏈接表中各結(jié)點(diǎn)的的順序是任意的.

2.鄰接表中的各個線性鏈接表不說明它們頂點(diǎn)之間的鄰接關(guān)系.

3.對于無向圖:

某頂點(diǎn)的度數(shù)=該頂點(diǎn)對應(yīng)的線性鏈表的結(jié)點(diǎn)數(shù)

對于有向圖:

某頂點(diǎn)的"出度"數(shù)=該頂點(diǎn)對應(yīng)的線性鏈表的結(jié)點(diǎn)數(shù)

第16頁，課件共52頁，創(chuàng)作于2023年2月逆鄰接表鏈表中每個結(jié)點(diǎn)表示鄰接矩陣中該頂點(diǎn)的列中每個非零元素

第17頁，課件共52頁，創(chuàng)作于2023年2月7.3圖的遍歷什么叫圖的遍歷

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

第18頁，課件共52頁，創(chuàng)作于2023年2月圖的遍歷的兩種方法

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

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

第19頁，課件共52頁，創(chuàng)作于2023年2月1.深度優(yōu)先搜索dfs

方法:

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

第20頁，課件共52頁，創(chuàng)作于2023年2月例：頂點(diǎn)的訪問序列：V1V2V4V8V5V3V6V7第21頁，課件共52頁，創(chuàng)作于2023年2月2.廣度優(yōu)先搜索bfs

方法:

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

第22頁，課件共52頁，創(chuàng)作于2023年2月例：頂點(diǎn)的訪問序列：V1V2V3V4V5V6V7V8第23頁，課件共52頁，創(chuàng)作于2023年2月7.4圖的最小生成樹

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

1.連通分量

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

第24頁，課件共52頁，創(chuàng)作于2023年2月P159G3圖7.3(a)鄰接表第25頁，課件共52頁，創(chuàng)作于2023年2月說明：該圖中包括三個連通分量，若按dfs分別從三個頂點(diǎn)（I，D，B）出發(fā)可得到三個連通分量的頂點(diǎn)序列：

I，G，K，H

D，E

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

第26頁，課件共52頁，創(chuàng)作于2023年2月2.圖的生成樹

圖中全部頂點(diǎn)和搜索過程所經(jīng)過的邊,構(gòu)成該連通圖的生成樹.

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

第27頁，課件共52頁，創(chuàng)作于2023年2月

由此可以總結(jié)生成樹的特點(diǎn):

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

第28頁，課件共52頁，創(chuàng)作于2023年2月7.4.2最小生成樹

1什么叫最小生成樹

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

2.求最小生成樹的算法

克魯斯卡爾算法普里姆算法第29頁，課件共52頁，創(chuàng)作于2023年2月例：第30頁，課件共52頁，創(chuàng)作于2023年2月克魯斯卡爾算法方法:將圖中邊按其權(quán)值由小到大的次序順序選取,若選邊后不形成回路,則保留作為一條邊,若形成回路則除去.依次選夠(n-1)條邊,即得最小生成樹.(n為頂點(diǎn)數(shù))

分析：該方法對于邊相對比較多的不是很實(shí)用,浪費(fèi)時間.

第31頁，課件共52頁，創(chuàng)作于2023年2月普里姆算法

方法:從指定頂點(diǎn)開始將它加入集合中,然后將集合內(nèi)的頂點(diǎn)與集合外的頂點(diǎn)所構(gòu)成的所有邊中選取權(quán)值最小的一條邊作為生成樹的邊,并將集合外的那個頂點(diǎn)加入到集合中,表示該頂點(diǎn)已連通.再用集合內(nèi)的頂點(diǎn)與集合外的頂點(diǎn)構(gòu)成的邊中找最小的邊,并將相應(yīng)的頂點(diǎn)加入集合中,如此下去直到全部頂點(diǎn)都加入到集合中,即得最小生成樹.第32頁，課件共52頁，創(chuàng)作于2023年2月7.5有向無環(huán)圖及其應(yīng)用

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

有向無環(huán)圖的作用:常用來描述一個工程或一個系統(tǒng)的進(jìn)行的過程.第33頁，課件共52頁，創(chuàng)作于2023年2月7.5.1AOV網(wǎng)

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

第34頁，課件共52頁，創(chuàng)作于2023年2月說明：在各個活動之間,有些必須按規(guī)定的先后次序進(jìn)行,有些則沒有次序要求.

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

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

AOV網(wǎng)的特點(diǎn):在網(wǎng)中一定不能有有向回路.

檢測網(wǎng)中是否存在環(huán),可用拓?fù)渑判虻姆椒?第35頁，課件共52頁，創(chuàng)作于2023年2月7.5.2拓?fù)渑判?/p>

1.什么叫拓?fù)渑判?/p>

將AOV網(wǎng)中各個頂點(diǎn)排列成一個有序序列,使得所有前驅(qū)和后繼關(guān)系都能得到滿足,而那些沒有次序的頂點(diǎn),在拓?fù)渑判虻男蛄兄锌梢圆宓饺我馕恢?也可說拓?fù)渑判蚴菍Ψ蔷€形結(jié)構(gòu)的有向圖進(jìn)行線形化的重要手段.第36頁，課件共52頁，創(chuàng)作于2023年2月2.拓?fù)渑判虻姆椒?/p>

由AOV網(wǎng)選取某個沒有前驅(qū)的頂點(diǎn),排到序列中,凡取出某頂點(diǎn),即將它與它相關(guān)聯(lián)的邊從圖中刪掉,隨著邊的刪除,又會有無前驅(qū)的頂點(diǎn),重復(fù)如此進(jìn)行,直到全部頂點(diǎn)都排到序列中去.例：如圖P181圖7.27第37頁，課件共52頁，創(chuàng)作于2023年2月7.6關(guān)鍵路徑

AOE網(wǎng)(ActivityOnEdgenetwork)，即邊表示活動的網(wǎng)絡(luò)，與AOV網(wǎng)相對應(yīng)的是。它通常表示一個工程的計(jì)劃或進(jìn)度。AOE網(wǎng)是一個有向帶權(quán)圖，圖中的：

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

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

頂點(diǎn)：表示事件，每個事件是活動之間的轉(zhuǎn)接點(diǎn)，即表示它的所有入邊活動到此完成，所有出邊活動從此開始。第38頁，課件共52頁，創(chuàng)作于2023年2月

其中有兩個特殊的頂點(diǎn)(事件)，一個稱做源點(diǎn)，它表示整個工程的開始，亦即最早活動的起點(diǎn)，顯然它只有出邊，沒有入邊；另一個稱做匯點(diǎn)，它表示整個工程的結(jié)束，亦即最后活動的終點(diǎn)，顯然它只有入邊，沒有出邊。除這兩個頂點(diǎn)外，其余頂點(diǎn)都既有入邊，也有出邊，是入邊活動和出邊活動的轉(zhuǎn)接點(diǎn)。第39頁，課件共52頁，創(chuàng)作于2023年2月

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

一個AOE網(wǎng)如圖，該網(wǎng)中包含有活動和事件。如圖P183圖7.29一個AOV網(wǎng)11項(xiàng)9個第40頁，課件共52頁，創(chuàng)作于2023年2月

對于一個AOE網(wǎng)，待研究的問題是：

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

(2)哪些活動是影響工程進(jìn)度的關(guān)鍵?

第41頁，課件共52頁，創(chuàng)作于2023年2月1．事件的最早發(fā)生時間與活動的最早開始時間的關(guān)系

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

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

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

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

第42頁，課件共52頁，創(chuàng)作于2023年2月2．求事件的最早發(fā)生時間

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

例：分析圖7.29

第43頁，課件共52頁，創(chuàng)作于2023年2月3．事件的最遲發(fā)生時間與活動的最遲開始時間的關(guān)系

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

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

第44頁，課件共52頁，創(chuàng)作于2023年2月4．求事件的最遲發(fā)生時間

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

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

第45頁，課件共52頁，創(chuàng)作于2023年2月關(guān)鍵路徑有些活動的開始時間余量不為0，表明這些活動不在最早開始時間開始，至多向后拖延相應(yīng)的開始時間余量所規(guī)定的時間開始也不會延誤整個工程的進(jìn)展。如對于活動a5，它最早可以從整個工程開工后的第4天開始，至多向后拖延兩天，即從第6天開始。

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

第46頁，課件共52頁，創(chuàng)作于2023年2月

關(guān)鍵路徑實(shí)際上就是從源點(diǎn)到匯點(diǎn)具有最長路徑長度的那些路徑，即最長路徑。這很容易理解，因?yàn)檎麄€工程的工期就是按照最長路徑長度計(jì)算出來的，即等于