數據結構 第6章 圖

1、數據結構 與 算法,第七講：圖,開場白,08/07/2020,2,內容提要,圖的定義 圖的存儲結構 圖的遍歷 最小生成樹 最短路徑 拓撲排序 關鍵路徑,08/07/2020,3,圖的定義,08/07/2020,4,圖(Graph)是由頂點的有窮集合和頂點之間的邊的集合組成，通常表示為：G(V,E)，其中 G 表示一個圖，V 是圖 G 中頂點的集合，E 是圖 G 中邊的集合。,1,2,3,5,7,6,9,8,4,圖的術語（一）,圖按有無方向分為無向圖和有向圖。無向圖由頂點和邊構成，有向圖由頂點和弧構成?；∮谢☆^和弧尾之分。 圖按照邊或弧的多少分稀疏圖和稠密圖。如果任意兩個頂點之間都存在邊叫完全圖

2、，有向的叫有向完全圖。若無重復的邊或頂點到自身的邊則叫簡單圖。 圖中頂點之間有鄰接點、依附的概念。無向圖頂點的邊數叫做度，有向圖頂點分為入度和出度。 圖上的邊或弧上帶權則稱為網。,08/07/2020,5,A,B,D,C,A,B,D,C,A,B,D,C,北京,香港,上海,臺北,1463,1680,1200,808,700,2160,圖a,圖b,圖c,圖d,圖的術語（二）,08/07/2020,6,圖中頂點存在路徑，兩頂點存在路徑則說明是連通的，如果路徑最終回到起始點則稱為回路或環(huán)，當中不重復叫簡單路徑。若任意兩頂點都是連通的，則圖就是連通圖，有向則稱強連通圖。圖中有子圖，若子圖極大連通則就是連

3、通分量，有向則稱強連通分量。,A,B,D,C,A,B,D,C,圖a,圖b,圖c,思考1：圖b是強連通圖嗎?圖c呢？,A,D,C,A,B,D,C,圖f,E,F,A,B,C,圖d,E,F,圖e,思考2：圖d是圖f的連通分量嗎？,圖的術語（三）,08/07/2020,7,無向圖中連通且n個頂點n-1條邊叫生成樹。有向圖中一頂點入度為0其余頂點入度為1的叫有向樹。一個有向圖由若干棵有向樹構成生成森林。,A,B,D,C,圖a,F,E,G,H,A,B,D,C,圖b,F,E,G,H,圖的抽象數據類型,08/07/2020,8,ADT 圖（Graph） Data 頂點的有窮集合和邊的集合。 Operation

4、 CreateGraph( typedef int EdgeType; #define MAXVEX 100 #define INFINITY 65535 typedef struct VertexType vexsMAXVEX; EdgeType arcMAXVEXMAXVEX; int numVertexes, numEdges; MGraph; void CreateMGraph(MGraph G) int i, j, k, w; printf(輸入頂點數和邊數：n); scanf(%d,%d, ,時間復雜度：O(n+n2+e),思考：鄰接矩陣的缺點？,圖的存儲結構：鄰接表（一）,鄰接表

5、：一維數組存頂點（包括數據和指向第一個鄰接點的指針），每個頂點vi的所有鄰接點構成一個單鏈表,08/07/2020,13,思考：如何知道某結點的度？ 如何判斷某條邊是否存在？ 如何求一個頂點的所有鄰接點？,圖的存儲結構：鄰接表（二）,08/07/2020,14,V0,V4,V1,V3,V2,9,有向網圖,typedef char VertexType; typedef int EdgeType; typedef struct EdgeNode int adjvex; EdgeType weight; struct EdgeNode *next; EdgeNode; typedef struct

6、 VertexNode VertexType data; EdgeNode *firstedge; VertexNode, AdjListMAXVEX; typedef struct AdjList adjList; int numVertexes, numEdges; GraphAdjList;,下標,0,1,2,3,4,0,V0,V1,V2,V3,data,firstedge,adjvex,next,0,3,4,4,V4,6,9,2,1,5,2,3,weight,圖的存儲結構：鄰接表（三）,08/07/2020,15,void CreateALGraph(GraphAdjList / 將當

7、前頂點的指針指向e ,時間復雜度：O(n+e),圖的存儲結構：十字鏈表,十字鏈表：有向圖的優(yōu)化，把鄰接表和逆鄰接表結合起來。,08/07/2020,16,V0,V3,V2,V1,有向圖,下標,0,1,2,3,3,0,V0,V1,V2,V3,data,firstedge,adjvex,next,2,0,1,創(chuàng)建算法的時間復雜度：O(n+e),注意：虛線箭頭其實就是逆鄰接表的表示,圖的存儲結構：鄰接多重表,鄰接多重表：無向圖的優(yōu)化，原來用兩個結點表示的一條邊，現在用一個結點表示,08/07/2020,17,V0,V3,V2,V1,無向圖,下標,0,1,2,3,1,2,0,V0,V1,V2,V3,d

8、ata,firstedge,adjvex,next,3,2,0,1,3,0,2,圖的存儲結構：邊集數組,邊集數組：兩個一維數組。一個存儲頂點的信息；另一個存儲邊的信息，邊數組每個數據元素由一條邊的起點下標（begin）、終點下標（end）和權（weight）組成。,08/07/2020,18,V0,V4,V1,V3,V2,9,V0,V1,V2,V3,頂點數組,V4,有向網圖,邊數組,typedef struct int begin; int end; int weight; Edge;,內容提要,圖的定義 圖的存儲結構 圖的遍歷 最小生成樹 最短路徑 拓撲排序 關鍵路徑,08/07/2020,

9、19,圖的遍歷,你經常找不到鑰匙嗎？ 圖的遍歷 從圖中某一頂點出發(fā) 訪遍圖中其余頂點， 且使每一個頂點僅被 訪問一次 兩種方法： 深度優(yōu)先遍歷 廣度優(yōu)先遍歷,08/07/2020,20,你玩游戲的時候討厭走迷宮嗎？,深度優(yōu)先遍歷(Depth First Search),08/07/2020,21,A,B,F,G,H,E,D,I,C,A,B,C,A,D,E,F,G,H,I,從圖中某個頂點v出發(fā)，訪問此頂點，然后從v的未訪問的鄰接點出發(fā)，深度優(yōu)先遍歷圖，直至圖中所有和v有路徑相同的頂點都被訪問到。對于非連通圖，則需要對它的連通分量分別進行深度優(yōu)先遍歷。,注意：是否與樹的某個次序遍歷相似？,鄰接矩陣

10、結構的深度優(yōu)先遍歷實現,08/07/2020,22,#define TRUE 1 #define FALSE 0 typedef int Boolean; /* Boolean是布爾類型，其值是TRUE或FALSE */ Boolean visitedMAX; /* 訪問標志的數組 */ /* 鄰接矩陣的深度優(yōu)先遞歸算法 */ void DFS(MGraph G, int i) int j; visitedi = TRUE; printf(%c , G.vexsi); /* 打印頂點，也可以為其他操作 */ for (j=0; jG.numVertexes; j+) if (G.arcij =

11、 1 ,時間復雜度：O(n2),鄰接表結構的深度優(yōu)先遍歷實現,08/07/2020,23,/* 鄰接表的深度優(yōu)先遞歸算法 */ void DFS(GraphAdjList GL, int i) EdgeNode *p; visitedi = TRUE; printf(%c , GL.adjListi.data); /* 打印頂點，也可以是其他操作 */ p = GL.adjListi.firstedge; while (p) if (!visitedp-adjvex) DFS(GL, p-adjvex); /* 對未訪問的鄰接頂點遞歸調用 */ p = p-next; /* 鄰接表的深度優(yōu)先遍

12、歷操作 */ void DFSTraverse(GraphAdjList GL) int i; for (i=0; iGL.numVertexes; i+) visitedi = FALSE; /* 初始化所有頂點狀態(tài)，都是未訪問過狀態(tài) */ for (i=0; iGL.numVertexes; i+) if(!visitedi) /* 對未訪問過的頂點調用DFS，若是連通圖，只會執(zhí)行一次 */ DFS(GL, i); ,時間復雜度：O(n+e),廣度優(yōu)先遍歷(Breath First Search),08/07/2020,24,A,B,F,G,H,E,D,I,C,A,B,F,G,H,E,D,

13、I,C,F,C,I,G,A,B,F,C,I,G,E,E,D,H,D,I,G,E,D,H,G,E,D,H,(1),(2),(3),(4),(5),(6),(7),(8),(9),出隊列,入隊列,鄰接矩陣結構的廣度優(yōu)先遍歷實現,08/07/2020,25,void BFSTraverse(MGraph G) /* 鄰接矩陣的廣度優(yōu)先遍歷算法 */ int i, j; Queue Q; for (i=0; iG.numVertexes; i+) visitedi = FALSE; InitQueue( ,時間復雜度：O(n2),鄰接表結構的廣度優(yōu)先遍歷實現,08/07/2020,26,void BF

14、STraverse(GraphAdjList GL) /* 鄰接表的廣度優(yōu)先遍歷算法 */ int i; EdgeNode *p; Queue Q; for (i=0; iadjvex) /* 若此頂點未被訪問 */ visitedp-adjvex = TRUE; printf(%c , GL.adjListp-adjvex.data); EnQueue( /* 指針指向下一個鄰接點 */ ,時間復雜度：O(n+e),深度優(yōu)先 vs 廣度優(yōu)先,如果存儲結構一樣，時間復雜度是一樣的 應用場景：深度優(yōu)先更適合找目標，廣度優(yōu)先更適合在不斷擴大遍歷范圍時找到相對最優(yōu)解。 方法論：深度優(yōu)先或廣度優(yōu)先是一

15、種生活態(tài)度 博覽群書不求甚解，還是專攻一門深入鉆研？ 走馬觀花蜻蜓點水，還是尋幽探奇深度體驗？ 四海之內皆兄弟，還是人生的一知己足矣？,08/07/2020,27,內容提要,圖的定義 圖的存儲結構 圖的遍歷 最小生成樹 最短路徑 拓撲排序 關鍵路徑,08/07/2020,28,最小生成樹(Minimum Cost Spanning Tree),假設你是電信工程師，需要為一個鎮(zhèn)子的九個村莊架設通信網絡 v0-v8是村莊 連線上的數字表示村與村之間的距離 沒有連線的表示不可直達，比如中間有高山或湖泊,08/07/2020,29,V0,V5,V4,V7,V6,V1,V2,V8,V3,11,10,18

16、,16,17,26,19,24,12,21,22,8,16,20,7,最小生成樹：普里姆(Prim)算法過程及演示,假設N=(V,E)是連通網，TE是N上最小生成樹中邊的集合。算法從U=u0(u0V),TE=開始。重復執(zhí)行下述操作：在所有uU,vV-U的邊(u,v)E中找一條代價最小的邊(u0,v0)并入集合TE，同時v0并入U，直至U=V為止。此時TE中必有n-1條邊，則T=(U,TE)為N的最小生成樹。 算法演示： U 包含所有藍灰色的結點； V-U 包含所有白色的結點； E 包含所有藍灰色的邊； TE 包含所有紅色的邊。,08/07/2020,30,V0,V5,V4,V7,V6,V1,V

17、2,V8,V3,11,10,18,16,17,26,19,24,12,21,22,8,16,20,7,最小生成樹：普里姆(Prim)算法代碼實現,08/07/2020,31,void MiniSpanTree_Prim(MGraph G) int min, i, j, k; / 保存已訪問的距離最近鄰接結點的下標 int adjvexMAXVEX; /* 保存已訪問的距離最近的鄰接結點之間的權值 */ int lowcostMAXVEX; /* lowcost為0表示該下標的頂點已加入生成樹,一開始生成樹中僅有v0 */ lowcost0 = 0; adjvex0 = 0; for (i=1;

18、 iG.numVertexes; i+) /* 將其他結點與v0之間的權值存入lowcost數組 */ lowcosti = G.arc0j; adjvexi = 0; for(i=1; iG.numVertexes; i+) /* 依次將其余結點加入最小生成樹，具體操作見右邊代碼 */ ,min = INFINITY; j = 1; k = 0; while (jG.numVertexes) if (lowcostj!=0 ,適用于稠密圖，時間復雜度：O(n2),最小生成樹：克魯斯卡爾(Kruscal)算法過程演示,假設N=(V,E)是連通網，令最小生成樹的初始狀態(tài)只有n個頂點而無邊的非連通

19、圖T=(V,)，圖中每個頂點自成一個連通分量。在E中選擇代價最小的邊，若該邊依附的頂點落在T中不同的連通分量上（即加上該邊不會形成回路），則將此邊加入到T中，否則舍去此邊而選擇下一條代價最小的邊。以此類推，直至T中所有頂點都在同一連通分量上為止。 算法演示： E 包含所有淺色的邊； T 包含所有紅色的邊； 黑色的邊為舍去的邊。,08/07/2020,32,V0,V5,V4,V7,V6,V1,V2,V8,V3,11,10,18,16,17,26,19,24,12,21,22,8,16,20,7,最小生成樹：克魯斯卡爾(Kruscal)算法代碼實現,08/07/2020,33,void MiniS

20、panTree_Kruskal(MGraph G) int i, n, m; Edge edgesMAXEDGE; int parentMAXVEX; /* 此處省略將鄰接矩陣G轉化為邊集數組edges并按權由小到大排序的代碼 */ for (i=0; i0) f = parentf; return f; ,適用于稀疏圖，時間復雜度：O(eloge),0,0,0,0,0,0,0,0,0,0,1,2,3,4,5,6,7,8,7,8,1,5,8,7,6,7,內容提要,圖的定義 圖的存儲結構 圖的遍歷 最小生成樹 最短路徑 拓撲排序 關鍵路徑,08/07/2020,34,最短路徑,08/07/202

21、0,35,網圖:指兩頂點之間經過的邊上權值之和最少的路徑。 非網圖：指兩頂點之間經過的邊數最少的路徑。 源點 終點,迪杰斯特拉(Dijkstra)算法,用途：求某個源點到其余各頂點的最短路徑 思路：按路徑長度遞增的次序產生最短路徑 算法演示：,08/07/2020,36,V1,V2,V3,V4,V5,V0,V6,V7,V8,1,5,7,5,3,1,7,3,2,3,6,9,5,2,7,4,下一個離v0最近的點是v1， 下一個離v0最近的點是v2， 下一個離v0最近的點是v4， 下一個離v0最近的點是v3， 下一個離v0最近的點是v5， 下一個離v0最近的點是v6， 下一個離v0最近的點是v7，

22、下一個離v0最近的點是v8，,v0v1v2v4v3v6v7v8,v0到v8的最短路徑是,迪杰斯特拉(Dijkstra)算法代碼實現,08/07/2020,37,#define MAXVEX 9 #define INFINITY 65535 typedef int PathMatrixMAXVEX; typedef int ShortPathTableMAXVEX; /* Pv的值為前驅頂點的下標 */ /* Dv表示v0到v的最短路徑長度和 */ void SP_Dijkstra(MGraph G, int v0, PathMatrix v+) /* 按長度遞增的次序，依次求得v0 到某個頂點

23、v的最短路徑，如右代碼 */ ,min = INFINITY; for (w=0; wG.numVertexes; w+) /* 尋找當前離v0最近的頂點 */ if (!finalw ,時間復雜度：O(n2),思考：如果求v0到特定頂點的最短路徑，算法會簡化嗎？如果求所有頂點之間的最短路徑呢？,弗洛伊德(Floyd)算法,用途：求任意兩個頂點之間的最短路徑 思路：鄰接矩陣迭代,08/07/2020,38,1,5,2,V0,V1,V2,V0,V1,V2,D-1,V0,V1,V2,V0,V1,V2,V0,V1,V2,V0,V1,V2,D0,因為D-112D-110+D-102,所以D-112=D

24、-110+D-102,V0,V1,V2,V0,V1,V2,P-1,V0,V1,V2,V0,V1,V2,P0,所以P-112=P-110,Dvw=L表示從頂點v到頂點w的最短路徑長度是L； Pvw=k表示從相應的從頂點v到頂點w的最短路徑從v出發(fā)要先經過頂點k。,弗洛伊德 (Floyd)算法代碼實現,08/07/2020,39,/* Floyd算法，各參數和D，P數組如前定義 */ void ShortestPath_Floyd(MGraph G, PathMatrix ,時間復雜度：O(n3),思考：剛才兩個算法舉例都是無向圖，那么對有向圖而言，兩個算法是否依然有效？,內容提要,圖的定義 圖的

25、存儲結構 圖的遍歷 最小生成樹 最短路徑 拓撲排序 關鍵路徑,08/07/2020,40,拓撲排序,在一個表示工程的有向圖中，用頂點表示活動，用弧表示活動之間的優(yōu)先關系，這樣的有向圖為頂點表示活動的網，我們稱為AOV網(Activity On Vertex Network)。 設G=(V,E)是一個具有n個頂點的有向圖，V中的頂點序列v1,v2,，vn，滿足若從頂點vi到vj有一條路徑，則在頂點序列中頂點vi必在頂點vj之前。則稱這樣的頂點序列為一個拓撲序列。拓撲排序就是對一個有向圖構造拓撲序列的過程。,08/07/2020,41,導演確定,劇本完善,電影制作啟動,投資確定,電影制作完成上映,

26、劇本初步完成,演職人員確定,V0,V2,V5,V6,人員到位進駐場地,V8,前期準備,場地確定,場景拍攝1,場景拍攝2,場景拍攝3,場景拍攝4,后期制作1,后期制作2,商業(yè)宣傳,V7,V3,V1,V4,V15,V13,V9,V10,V11,V12,V14,V16,拓撲排序算法,基本思路：(1)從AOV網中選擇一個入度為0的頂點輸出;(2)刪去此頂點，并刪除以此頂點為尾的弧。繼續(xù)重復這兩個步驟，直到輸出全部頂點或者AOV網中不存在入度為0的頂點為止。,08/07/2020,42,0,下標,0,V0,data,firstarc,indegree,11,0,V1,8,2,V2,9,0,V3,13,1

27、,2,3,2,4,V4,7,3,V5,12,1,V6,5,2,V7,5,6,7,2,8,V8,7,2,V9,11,1,V10,13,2,V11,9,10,11,1,V12,9,2,V13,12,13,adjvex,nextarc,5,4,4,2,6,5,2,8,10,V0,V1,V2,V3,V6,V5,V4,V7,V8,V9,V10,V13,V12,V11,1,4,3,2,1,0,V0,V1,V3,1,1,1,0,V2,2,0,1,V6,1,v3,v1,v2,v6,v0,0,0,1,V4,V5,vertices,拓撲排序算法代碼實現,08/07/2020,43,Status Topologic

28、alSort(ALGraph G) / 有向圖G采用鄰接表存儲結構，頂點表和邊表結構如前頁所示，G.vernum表示頂點數 / 若G無回路，則輸出G 的頂點的一個拓撲序列并返回OK，否則ERROR FindInDegree(G, indegree); / 對各頂點求入度indegree0.G.vernum-1 InitStack(S); / 建零入度頂點棧S for (i=0; inextarc) k = p-adjvex; if (!(-indegreek) Push(S, k); / 若入度減為0，則入棧 / for / while if (countG.vexnum) return ER

29、ROR; / 該有向圖有回路 else return OK; ,時間復雜度：O(n+e),內容提要,圖的定義 圖的存儲結構 圖的遍歷 最小生成樹 最短路徑 拓撲排序 關鍵路徑,08/07/2020,44,關鍵路徑,與AOV網對應的是AOE網(Activity On Edge)即邊表示活動的網。AOE網是一個帶權的有向無環(huán)圖，其中，頂點表示事件(Event)，弧表示活動，權表示活動持續(xù)的時間。通常，AOE網可用來估算工程的完成時間。 AOE網通常研究的問題是：（1）完成整個工程至少需要多少時間？（2）哪些活動是影響工程進度的關鍵？路徑長度最長的路經叫關鍵路徑（Critical Path）。,08/07/2020,45,造外殼,開始,集中,其他零部件,造發(fā)動機,造輪子,造底盤,組裝,完成,外殼完成,開始,其他零部件完成,發(fā)動機完成