第03基本數(shù)據(jù)結(jié)構(gòu)與運(yùn)算

1、第03基本數(shù)據(jù)結(jié)構(gòu)與運(yùn)算第1頁，共50頁，2022年，5月20日，13點(diǎn)25分，星期五3.6.1 圖的基本概念BACD63215數(shù)據(jù)結(jié)構(gòu) B=（D，R）圖： G=（V，E）頂點(diǎn):圖中的數(shù)據(jù)元素V：表示頂點(diǎn)的非空有限集合。E：表示兩個(gè)頂點(diǎn)之間關(guān)系的集合。圖的定義、術(shù)語第2頁，共50頁，2022年，5月20日，13點(diǎn)25分，星期五圖有向圖無向圖在有向圖中，表示從V1到V3的一條弧。 V1為弧尾或初始點(diǎn)，V3為弧頭或終端點(diǎn)。在無向圖中，(V1，V3)表示V1和V3之間的一條邊。V1V3V2V4V1V3V2V4圖的定義、術(shù)語第3頁，共50頁，2022年，5月20日，13點(diǎn)25分，星期五V1V3V2V4

2、V1V3V2V4頂點(diǎn)集合V=V1 ， V2 ， V3 ， V4 弧的集合G=, , , 頂點(diǎn)集合V=V1 ， V2 ， V3 ， V4 邊的集合E=(V1, V3), (V1, V2), (V1, V4),(V2, V4)G=( V, E )頂點(diǎn)(V1, V3)與 (V3, V1)表示同一條邊圖的定義、術(shù)語第4頁，共50頁，2022年，5月20日，13點(diǎn)25分，星期五BACD63215權(quán)：與圖的邊或弧相關(guān)的數(shù)。頂點(diǎn)的度：依附于該頂點(diǎn)的邊數(shù)或弧數(shù)。出度：（僅對(duì)有向圖）以該頂點(diǎn)為尾的弧數(shù)。入度：（僅對(duì)有向圖）以該頂點(diǎn)為頭的弧數(shù)。路徑：頂點(diǎn)A與頂點(diǎn)C之間存在一條路徑。路徑上邊或弧的數(shù)目 稱為該路徑的

3、路徑長度。連通圖：無向圖任意兩頂點(diǎn)都有路徑（沒有孤立頂點(diǎn)）強(qiáng)連通圖：有向圖任意兩頂點(diǎn)都有路徑網(wǎng)：帶權(quán)的圖稱為網(wǎng)圖的定義、術(shù)語第5頁，共50頁，2022年，5月20日，13點(diǎn)25分，星期五圖的存儲(chǔ) 鄰接矩陣3.6.2 圖的存儲(chǔ)1. 鄰接矩陣法（1）給頂點(diǎn)編號(hào)（2）建立鄰接（關(guān)系）矩陣21431 2 3 41 2 3 40 0 0 01 0 1 11 0 0 10 1 1 0a i j表示弧1：表示有??；0:表示無弧任意頂點(diǎn)的出度是該行元素之和任意頂點(diǎn)的入度是該列元素之和第6頁，共50頁，2022年，5月20日，13點(diǎn)25分，星期五圖的存儲(chǔ) 鄰接矩陣鄰接矩陣的優(yōu)點(diǎn)：增減邊的操作簡單鄰接矩陣的缺點(diǎn)：

4、增減頂點(diǎn)的操作需要搬移大量的元素，浪費(fèi)存儲(chǔ)空間21431 2 3 41 2 3 40 1 1 01 0 1 11 1 0 10 1 1 0無向圖的鄰接矩陣是對(duì)稱的第7頁，共50頁，2022年，5月20日，13點(diǎn)25分，星期五圖的存儲(chǔ) 鄰接矩陣的實(shí)現(xiàn)圖的鄰接矩陣實(shí)現(xiàn)typedef struct graph_melemtype nodeMAXNUM;int arcsMAXNUMMAXNUM;graph_m;頂點(diǎn)集合邊的鄰接矩陣二維數(shù)組第8頁，共50頁，2022年，5月20日，13點(diǎn)25分，星期五圖的存儲(chǔ) 鄰接表2. 鄰接表法一個(gè)鄰接表由兩種結(jié)構(gòu)組成存放各頂點(diǎn)元素的數(shù)組，頭結(jié)點(diǎn)各頂點(diǎn)各自的鄰接鏈表，

5、鄰接結(jié)點(diǎn)2143231data2data3data4data134124233data頂點(diǎn)號(hào)元素域鄰接鏈表頭指針2鄰接頂點(diǎn)號(hào)下一鄰接結(jié)點(diǎn)第9頁，共50頁，2022年，5月20日，13點(diǎn)25分，星期五圖的存儲(chǔ)（課堂練習(xí)）請(qǐng)寫出下面這副圖的鄰接表1）給頂點(diǎn)編號(hào)2）建立頂點(diǎn)數(shù)組3）建立各頂點(diǎn)的鄰接鏈表注意，此圖為有向圖213451data2data3data4data5data2313514第10頁，共50頁，2022年，5月20日，13點(diǎn)25分，星期五圖的存儲(chǔ) 鄰接表的實(shí)現(xiàn)鄰接表的定義頭結(jié)點(diǎn)的定義鄰接結(jié)點(diǎn)的定義頂點(diǎn)號(hào)元素域與頭結(jié)點(diǎn)相鄰的頂點(diǎn)typedef struct headnodeint no

6、de_index;elemtype data;struct adj_node * next_adj; headnode;頂點(diǎn)號(hào)下一個(gè)與頭結(jié)點(diǎn)相鄰的頂點(diǎn)的鄰接結(jié)點(diǎn)typedef struct adj_nodeint node_index;struct adj_node *next_adj;adj_node;第11頁，共50頁，2022年，5月20日，13點(diǎn)25分，星期五圖的存儲(chǔ) 鄰接表圖鄰接表的定義typedef struct graph_lheadnode node_listMAXNUM;int node_num;graph_l;231data2data3data4data13412423第1

7、2頁，共50頁，2022年，5月20日，13點(diǎn)25分，星期五圖的存儲(chǔ) 鄰接表2143231data2data3data4data1341242321431data2data3data4data134134注意：有向圖與無向圖的區(qū)別第13頁，共50頁，2022年，5月20日，13點(diǎn)25分，星期五圖的存儲(chǔ)圖的鄰接表存儲(chǔ)法的特點(diǎn)優(yōu)點(diǎn)節(jié)省存儲(chǔ)空間邊的插入和刪除操作比較簡便缺點(diǎn)結(jié)構(gòu)復(fù)雜具有兩種不同的基本組成單元第14頁，共50頁，2022年，5月20日，13點(diǎn)25分，星期五圖的存儲(chǔ)3. 邊帶權(quán)值的圖的存儲(chǔ)1）在鄰接矩陣中的實(shí)現(xiàn)0 2 3 50 1 01 0 15 0 1 0a44 =a i j ：記錄邊

8、的權(quán)值；為0表示無邊124323511第15頁，共50頁，2022年，5月20日，13點(diǎn)25分，星期五圖的存儲(chǔ)3. 邊帶權(quán)值的圖的存儲(chǔ)2）在鄰接表中的實(shí)現(xiàn)在鄰接結(jié)點(diǎn)結(jié)構(gòu)中增加一個(gè)權(quán)值域1data2data3data4data233211354102331頂點(diǎn)號(hào)邊權(quán)值124332511103第16頁，共50頁，2022年，5月20日，13點(diǎn)25分，星期五圖的遍歷3.6.3 圖的遍歷問題：1）對(duì)于連通圖，從一個(gè)頂點(diǎn)出發(fā)沿著所有可能的路徑，是否可以將所有的頂點(diǎn)遍歷到。2）圖中有回路，遍歷算法可能產(chǎn)生死循環(huán)。有重復(fù)的路徑稱為回路2143第17頁，共50頁，2022年，5月20日，13點(diǎn)25分，星期五圖

9、的遍歷 深優(yōu)1. 深度優(yōu)先遍歷（1）從一個(gè)未訪問過的頂點(diǎn)開始，訪問它的一個(gè)未訪問過的相鄰頂點(diǎn)。（2）如果頂點(diǎn)的所有相鄰頂點(diǎn)都是已訪問過的，則需要回溯到之前的一個(gè)頂點(diǎn)，選取它的另一個(gè)未被訪問的相鄰頂點(diǎn)。（3）對(duì)于前兩個(gè)步驟是遞歸的第18頁，共50頁，2022年，5月20日，13點(diǎn)25分，星期五圖的遍歷 深優(yōu)1. 深度優(yōu)先遍歷（1）從一個(gè)未訪問過的頂點(diǎn)開始，訪問它的一個(gè)未訪問過的相鄰頂點(diǎn)。（2）如果頂點(diǎn)的所有相鄰頂點(diǎn)都是已訪問過的，則需要回溯到之前的一個(gè)頂點(diǎn)，選取它的另一個(gè)未被訪問的相鄰頂點(diǎn)。（3）對(duì)于前兩個(gè)步驟是遞歸的1258463717365284回到8173652841 3 6 8 4 2

10、5 7或者按以下順序遍歷：注意使用棧支持遞歸：第19頁，共50頁，2022年，5月20日，13點(diǎn)25分，星期五圖的遍歷 深優(yōu)深度優(yōu)先遍歷的特點(diǎn)“深度”：總是訪問頂點(diǎn)的一個(gè)相鄰頂點(diǎn)，好像是沿著圖中的一條路徑走到“底”，然后后退一點(diǎn)，再選一條路。如此“進(jìn)進(jìn)退退”，直到所有頂點(diǎn)都被訪問對(duì)于連通圖，如果第一個(gè)被訪問的頂點(diǎn)的所有相鄰頂點(diǎn)都被訪問了，意味著圖中所有頂點(diǎn)都被訪問了。即棧空時(shí)第20頁，共50頁，2022年，5月20日，13點(diǎn)25分，星期五圖的遍歷 深優(yōu)用遞歸調(diào)用實(shí)現(xiàn)深度優(yōu)先遍歷算法void dfs （g，v）1訪問頂點(diǎn)v；visit（v）；visited v = 1;p = gv-next_a

11、djwhile(p != NULL) w = p-node_index; if(visitedw = 0) p = p-next_adj;2取得頂點(diǎn)的一個(gè)未被訪問過的頂點(diǎn)w；3 dfs（g，w）；回到2；4重復(fù)2，3直到該頂點(diǎn)所有的相鄰頂點(diǎn)都被訪問過；dfs(g,w);第21頁，共50頁，2022年，5月20日，13點(diǎn)25分，星期五12345void dfs（g ，v） visited v = 1; p = g v -next_adj while(p != NULL) w = p-node_index; if(visited w = 0) dfs( g, w ); p = p-next_adj

12、; void dfs（g ，2） visited 2 = 1; p = g 2 -next_adj while(p != NULL) w = p-node_index; if(visited 3 = 0) dfs( g, 3 ); p = p-next_adj; void dfs（g ，3） visited 3 = 1; p = g 3 -next_adj while(p != NULL) w = p-node_index; if(visited 4 = 0) dfs( g , 4 ); p = p-next_adj; void dfs（g ，4） visited 4 = 1; p = g 4

13、 -next_adj while(p != NULL) w = p-node_index; if(visited w = 0) dfs( g , w ); p = p-next_adj; void dfs（g ，5） visited 5 = 1; p = g 5 -next_adj while(p != NULL) w = p-node_index; if(visited w = 0) dfs( g , w ); p = p-next_adj; void dfs（g ，1） visited 1 = 1; p = g 1 -next_adj while(p != NULL) w = p-node

14、_index; if(visited 2 = 0) dfs( g, 2 ); p = p-next_adj; if(visited 5 = 0)dfs( g , 5 );第22頁，共50頁，2022年，5月20日，13點(diǎn)25分，星期五圖的遍歷 廣優(yōu)2. 廣度優(yōu)先遍歷訪問頂點(diǎn)v后，接著依次訪問v的所有鄰接頂點(diǎn)，再依次訪問這些鄰接頂點(diǎn)的鄰接頂點(diǎn)。直到所有的頂點(diǎn)都被訪問過。1258463712345678注意：8是作為哪個(gè)頂點(diǎn)的鄰接頂點(diǎn)被訪問的？12345678體會(huì)隊(duì)列操作方式：第23頁，共50頁，2022年，5月20日，13點(diǎn)25分，星期五圖的遍歷 廣優(yōu)廣度優(yōu)先遍歷的特點(diǎn)“廣度”：總是在訪問了一個(gè)

15、頂點(diǎn)后，依次訪問它的所有相鄰頂點(diǎn)。然后再從它的第一個(gè)相鄰頂點(diǎn)開始，訪問其所有的相鄰頂點(diǎn)。如此逐個(gè)頂點(diǎn)地逐步擴(kuò)散，直到所有的頂點(diǎn)都被訪問。廣度優(yōu)先遍歷操作具有隊(duì)列操作的特點(diǎn)，當(dāng)從隊(duì)列中取出最后一個(gè)頂點(diǎn)，發(fā)現(xiàn)該頂點(diǎn)的所有相鄰頂點(diǎn)都被訪問過時(shí)，意味著圖中所有的頂點(diǎn)都已被訪問過第24頁，共50頁，2022年，5月20日，13點(diǎn)25分，星期五生成樹與圖3.6.4 圖的應(yīng)用1. 生成樹定義假設(shè)存在這樣一顆樹：樹結(jié)點(diǎn)的集合與圖的頂點(diǎn)集合相等樹的分支全部由圖的邊組成。稱這顆樹是這幅圖的生成樹生成樹是圖的:子集/子圖是一個(gè)不包含回路的子圖圖的生成樹是2143214321432143不唯一的！唯一的！取決于遍歷方

16、法和遍歷的起始點(diǎn)第25頁，共50頁，2022年，5月20日，13點(diǎn)25分，星期五生成樹的示例生成樹與圖對(duì)于一個(gè)有n個(gè)頂點(diǎn)的連通圖G，其生成樹包含了 條邊。深度優(yōu)先搜索得到的生成樹廣度優(yōu)先搜索得到的生成樹n1第26頁，共50頁，2022年，5月20日，13點(diǎn)25分，星期五權(quán)值生成樹與圖2. 最小費(fèi)用生成樹（通信網(wǎng)絡(luò)、交通網(wǎng)絡(luò)）在圖所有生成樹中，邊的權(quán)值總和最小的生成樹1245636536642416124563邊131462253144364235126356566將邊按權(quán)值大小排列第27頁，共50頁，2022年，5月20日，13點(diǎn)25分，星期五生成樹與圖算法分析關(guān)鍵技術(shù)：為什么在（1,4）邊選

17、中后不能選（3,6）邊在選擇（3,6）邊和（2,3）邊時(shí)有什么不同，怎樣設(shè)置條件以區(qū)別？當(dāng)時(shí)3和6位于同一圖中，2、5和3位于不同的圖中1245636536642416124563144364235回路第28頁，共50頁，2022年，5月20日，13點(diǎn)25分，星期五生成樹與圖1245631）開始時(shí)所有的節(jié)點(diǎn)都位于不同的圖中2）選擇一條連接兩個(gè)不同子圖的最短邊3）連接以后兩個(gè)子圖的所有頂點(diǎn)都要改為 在一個(gè)子圖中4）當(dāng)所有的頂點(diǎn)都位于一個(gè)子圖中， 算法結(jié)束。權(quán)值邊131462253144364235126思考既然是顆樹，如果選擇邊數(shù)為n1個(gè)時(shí)可不可以結(jié)束算法呢？算法的優(yōu)化第29頁，共50頁，202

18、2年，5月20日，13點(diǎn)25分，星期五圖的最短路徑3 .最短路徑圖中兩個(gè)頂點(diǎn)之間有 條路徑最短路徑：是路徑中邊（?。┑臋?quán)值總和最小的路徑計(jì)算機(jī)網(wǎng)絡(luò)中常使用最短路徑算法計(jì)算最佳路徑交通網(wǎng)絡(luò)中使用最短路徑算法計(jì)算最短旅途多Dijkstra AlgorithmFloyd Algorithm第30頁，共50頁，2022年，5月20日，13點(diǎn)25分，星期五A1A2A4A3A526512151）初始化時(shí)，設(shè)A1到其它不直連頂點(diǎn)距離為尋找A1到所有節(jié)點(diǎn)的最短路徑A2A3A4A5頂點(diǎn)距離路徑2）選擇距離最短的路徑3）觀察通過新選擇的路徑是否能更短地到達(dá)其它頂點(diǎn)4）選擇出的最短路徑將不參加下一輪比較5）反復(fù)2

19、- 4步，直到不剩有頂點(diǎn)265A2A3A4A1 A2 A33更新A1 A2 A33A1 A2 A4 A1 A2 A5 4A1 A2 A3 A44更新A1 A2 A3 A44A1 A2 A3 A58A1 A2 A54A1 A2 A3 A4 A5更新Dijkstra Algorithm第31頁，共50頁，2022年，5月20日，13點(diǎn)25分，星期五拓 撲 排 序按一定順序進(jìn)行的活動(dòng)，可以使用頂點(diǎn)表示活動(dòng)、頂點(diǎn)之間的有向邊表示活動(dòng)間的先后關(guān)系的有向圖來表示，這種有向圖稱為頂點(diǎn)表示活動(dòng)網(wǎng)絡(luò)(Activity On Vertex network，簡稱AOV網(wǎng))。AOV網(wǎng)中的有向邊表示了活動(dòng)之間的制約關(guān)系

20、。4. 拓 撲 排 序第32頁，共50頁，2022年，5月20日，13點(diǎn)25分，星期五將AOV網(wǎng)中的所有頂點(diǎn)排列成一個(gè)線性序列vi1, vi2, , vin，并且這個(gè)序列同時(shí)滿足關(guān)系：若在AOV網(wǎng)中從頂點(diǎn)vi到頂點(diǎn)vj存在一條路徑，則在線性序列中vi必在vj之前，我們就稱這個(gè)線性序列為拓?fù)湫蛄小０褜?duì)AOV網(wǎng)構(gòu)造拓?fù)湫蛄械牟僮鞣Q為拓?fù)渑判?。在?shí)際的意義上，AOV網(wǎng)中存在的有向環(huán)就意味著某些活動(dòng)是以自己為先決條件，這顯然是荒謬的。例如對(duì)于程序的數(shù)據(jù)流圖而言，AOV網(wǎng)中存在環(huán)就意味著程序存在一個(gè)死循環(huán)。第33頁，共50頁，2022年，5月20日，13點(diǎn)25分，星期五任何一個(gè)無環(huán)的AOV網(wǎng)中的所有頂點(diǎn)

21、都可排列在一個(gè)拓?fù)湫蛄欣?，拓?fù)渑判虻幕静僮魅缦拢?(1) 從網(wǎng)中選擇一個(gè)入度為0的頂點(diǎn)并且輸出它。 (2) 從網(wǎng)中刪除此頂點(diǎn)及所有由它發(fā)出的邊。 (3) 重復(fù)上述兩步，直到網(wǎng)中再?zèng)]有入度為0的頂點(diǎn)為止。 第34頁，共50頁，2022年，5月20日，13點(diǎn)25分，星期五第35頁，共50頁，2022年，5月20日，13點(diǎn)25分，星期五 以上的操作會(huì)產(chǎn)生兩種結(jié)果：一種是網(wǎng)中的全部頂點(diǎn)都被輸出，整個(gè)拓?fù)渑判蛲瓿?；另一種是網(wǎng)中頂點(diǎn)未被全部輸出，剩余的頂點(diǎn)的入度均不為0，則說明網(wǎng)中存在有向環(huán)。用以上操得到了一種拓?fù)湫蛄校篊1, C2 , C3, C4, C5, C7, C9, C10, C12, C11

22、, C6, C8。拓?fù)湫蛄锌梢允?種多第36頁，共50頁，2022年，5月20日，13點(diǎn)25分，星期五AOV網(wǎng)拓?fù)渑判蜻^程第37頁，共50頁，2022年，5月20日，13點(diǎn)25分，星期五在鄰接表存儲(chǔ)結(jié)構(gòu)中實(shí)現(xiàn)拓?fù)渑判蛩惴ǖ牟襟E為： (1) 掃描頂點(diǎn)表，將入度為0的頂點(diǎn)入棧。 (2) 當(dāng)棧非空時(shí)執(zhí)行以下操作： 將棧頂頂點(diǎn)vi的序號(hào)彈出，并輸出之； 檢查vi的出邊表，將每條出邊表鄰接點(diǎn)域所對(duì)應(yīng)的頂點(diǎn)的入度域值減1，若該頂點(diǎn)入度為0，則將其入棧； (3) 若輸出的頂點(diǎn)數(shù)小于n，則輸出“有回路”，否則拓?fù)渑判蛘＝Y(jié)束。第38頁，共50頁，2022年，5月20日，13點(diǎn)25分，星期五關(guān) 鍵 路 徑5.

23、關(guān)鍵路徑AOE網(wǎng)絡(luò)(Activity On Edge network)：有向邊：表示一個(gè)子工程（活動(dòng)）邊上的權(quán)值：表示一個(gè)活動(dòng)持續(xù)的時(shí)間頂點(diǎn)：表示事件，它表示了一種狀態(tài)，即它的入邊所表示的活動(dòng)均已完成，它的出邊所表示的活動(dòng)可以開始。這種帶權(quán)的有向網(wǎng)絡(luò)稱為 AOE網(wǎng)絡(luò)(Activity On Edge network)，即邊表示活動(dòng)網(wǎng)絡(luò)。第39頁，共50頁，2022年，5月20日，13點(diǎn)25分，星期五一個(gè)AOE網(wǎng)絡(luò)的示例第40頁，共50頁，2022年，5月20日，13點(diǎn)25分，星期五關(guān)鍵路徑：從源點(diǎn)到匯點(diǎn)的具有最大路徑長度的路徑。關(guān)鍵活動(dòng)：關(guān)鍵路徑上的各個(gè)活動(dòng)。明確了哪些活動(dòng)是關(guān)鍵活動(dòng)就可以設(shè)法

24、提高關(guān)鍵活動(dòng)的功效，以便縮短整個(gè)工期。 第41頁，共50頁，2022年，5月20日，13點(diǎn)25分，星期五 其中E1是網(wǎng)絡(luò)中以vj為終點(diǎn)的入邊集合，dur()是有向邊 上的權(quán)值。 vl(j)的計(jì)算可從匯點(diǎn)開始，向源點(diǎn)逆推計(jì)算： (13.2) 其中E2是網(wǎng)絡(luò)中以vj為起點(diǎn)的出邊集合。 (1)(2)ve(j)的計(jì)算可從源點(diǎn)開始利用以下的遞推公式求得第42頁，共50頁，2022年，5月20日，13點(diǎn)25分，星期五ve(1)=0ve(2)=maxve(1)+dur()=max0+3=3ve(3)=maxve(1)+dur()=max0+2=2ve(4)=mawve(2)+dur(), ve(3)+dur()=max3+4, 2+3=7ve(5)=maxve(4)+dur(), ve(2)+dur()=max7+4, 3+8=11ve(6)=maxve(3)+dur(), ve(4)+dur()=max2+7, 7+2=9ve(7)=maxve(5)+dur(), ve(6)+dur()=max11+9, 9+6=20vl(7)=ve(7)=20按(1)式和