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

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

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

3、路徑長度。連通圖：無向圖任意兩頂點都有路徑（沒有孤立頂點）強連通圖：有向圖任意兩頂點都有路徑網(wǎng)：帶權(quán)的圖稱為網(wǎng)圖的定義、術(shù)語第5頁，共50頁，2022年，5月20日，13點25分，星期五圖的存儲 鄰接矩陣3.6.2 圖的存儲1. 鄰接矩陣法（1）給頂點編號（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:表示無弧任意頂點的出度是該行元素之和任意頂點的入度是該列元素之和第6頁，共50頁，2022年，5月20日，13點25分，星期五圖的存儲 鄰接矩陣鄰接矩陣的優(yōu)點：增減邊的操作簡單鄰接矩陣的缺點：

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

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

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

7、2頁，共50頁，2022年，5月20日，13點25分，星期五圖的存儲 鄰接表2143231data2data3data4data1341242321431data2data3data4data134134注意：有向圖與無向圖的區(qū)別第13頁，共50頁，2022年，5月20日，13點25分，星期五圖的存儲圖的鄰接表存儲法的特點優(yōu)點節(jié)省存儲空間邊的插入和刪除操作比較簡便缺點結(jié)構(gòu)復(fù)雜具有兩種不同的基本組成單元第14頁，共50頁，2022年，5月20日，13點25分，星期五圖的存儲3. 邊帶權(quán)值的圖的存儲1）在鄰接矩陣中的實現(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點25分，星期五圖的存儲3. 邊帶權(quán)值的圖的存儲2）在鄰接表中的實現(xiàn)在鄰接結(jié)點結(jié)構(gòu)中增加一個權(quán)值域1data2data3data4data233211354102331頂點號邊權(quán)值124332511103第16頁，共50頁，2022年，5月20日，13點25分，星期五圖的遍歷3.6.3 圖的遍歷問題：1）對于連通圖，從一個頂點出發(fā)沿著所有可能的路徑，是否可以將所有的頂點遍歷到。2）圖中有回路，遍歷算法可能產(chǎn)生死循環(huán)。有重復(fù)的路徑稱為回路2143第17頁，共50頁，2022年，5月20日，13點25分，星期五圖

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

10、5 7或者按以下順序遍歷：注意使用棧支持遞歸：第19頁，共50頁，2022年，5月20日，13點25分，星期五圖的遍歷 深優(yōu)深度優(yōu)先遍歷的特點“深度”：總是訪問頂點的一個相鄰頂點，好像是沿著圖中的一條路徑走到“底”，然后后退一點，再選一條路。如此“進進退退”，直到所有頂點都被訪問對于連通圖，如果第一個被訪問的頂點的所有相鄰頂點都被訪問了，意味著圖中所有頂點都被訪問了。即?？諘r第20頁，共50頁，2022年，5月20日，13點25分，星期五圖的遍歷 深優(yōu)用遞歸調(diào)用實現(xiàn)深度優(yōu)先遍歷算法void dfs （g，v）1訪問頂點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取得頂點的一個未被訪問過的頂點w；3 dfs（g，w）；回到2；4重復(fù)2，3直到該頂點所有的相鄰頂點都被訪問過；dfs(g,w);第21頁，共50頁，2022年，5月20日，13點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點25分，星期五圖的遍歷 廣優(yōu)2. 廣度優(yōu)先遍歷訪問頂點v后，接著依次訪問v的所有鄰接頂點，再依次訪問這些鄰接頂點的鄰接頂點。直到所有的頂點都被訪問過。1258463712345678注意：8是作為哪個頂點的鄰接頂點被訪問的？12345678體會隊列操作方式：第23頁，共50頁，2022年，5月20日，13點25分，星期五圖的遍歷 廣優(yōu)廣度優(yōu)先遍歷的特點“廣度”：總是在訪問了一個

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

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

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

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

19、- 4步，直到不剩有頂點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點25分，星期五拓 撲 排 序按一定順序進行的活動，可以使用頂點表示活動、頂點之間的有向邊表示活動間的先后關(guān)系的有向圖來表示，這種有向圖稱為頂點表示活動網(wǎng)絡(luò)(Activity On Vertex network，簡稱AOV網(wǎng))。AOV網(wǎng)中的有向邊表示了活動之間的制約關(guān)系

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

21、都可排列在一個拓撲序列里，拓撲排序的基本操作如下： (1) 從網(wǎng)中選擇一個入度為0的頂點并且輸出它。 (2) 從網(wǎng)中刪除此頂點及所有由它發(fā)出的邊。 (3) 重復(fù)上述兩步，直到網(wǎng)中再沒有入度為0的頂點為止。 第34頁，共50頁，2022年，5月20日，13點25分，星期五第35頁，共50頁，2022年，5月20日，13點25分，星期五 以上的操作會產(chǎn)生兩種結(jié)果：一種是網(wǎng)中的全部頂點都被輸出，整個拓撲排序完成；另一種是網(wǎng)中頂點未被全部輸出，剩余的頂點的入度均不為0，則說明網(wǎng)中存在有向環(huán)。用以上操得到了一種拓撲序列：C1, C2 , C3, C4, C5, C7, C9, C10, C12, C11

22、, C6, C8。拓撲序列可以是 種多第36頁，共50頁，2022年，5月20日，13點25分，星期五AOV網(wǎng)拓撲排序過程第37頁，共50頁，2022年，5月20日，13點25分，星期五在鄰接表存儲結(jié)構(gòu)中實現(xiàn)拓撲排序算法的步驟為： (1) 掃描頂點表，將入度為0的頂點入棧。 (2) 當棧非空時執(zhí)行以下操作： 將棧頂頂點vi的序號彈出，并輸出之； 檢查vi的出邊表，將每條出邊表鄰接點域所對應(yīng)的頂點的入度域值減1，若該頂點入度為0，則將其入棧； (3) 若輸出的頂點數(shù)小于n，則輸出“有回路”，否則拓撲排序正常結(jié)束。第38頁，共50頁，2022年，5月20日，13點25分，星期五關(guān) 鍵 路 徑5.

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

24、提高關(guān)鍵活動的功效，以便縮短整個工期。 第41頁，共50頁，2022年，5月20日，13點25分，星期五 其中E1是網(wǎng)絡(luò)中以vj為終點的入邊集合，dur()是有向邊 上的權(quán)值。 vl(j)的計算可從匯點開始，向源點逆推計算： (13.2) 其中E2是網(wǎng)絡(luò)中以vj為起點的出邊集合。 (1)(2)ve(j)的計算可從源點開始利用以下的遞推公式求得第42頁，共50頁，2022年，5月20日，13點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)式和