數(shù)據(jù)結構(長安大學)講課PPT6

1、數(shù)據(jù)結構教師教師：楊云 班級班級：24020803/04 學院學院：長安大學信息工程學院 地址地址：WM1506 Email：數(shù)據(jù)結構 -學習數(shù)據(jù)結構的方法邏輯結構運算定義存儲結構實現(xiàn)運算分析 第七章 圖7.1 圖的定義和基本概念7.2 圖的存儲結構 7.2.1 數(shù)組表示法 7.2.2 鄰接表 7.2.3 十字鏈表 7.2.4 鄰接多重表7.3 圖的遍歷 7.3.1 深度優(yōu)先搜索 7.3.2 廣度優(yōu)先搜索7.4 圖的連通性 7.4.1 無向圖的連通分量和生成樹 7.4.2 最小生成樹7.5 有向五環(huán)圖及其應用 7.5.1 拓撲排序 7.5.2 關鍵路徑7.6 最短路徑 7.6.1 從某個源點到

2、其余各頂點的最短路徑 7.6.2 每一對頂點之間的最短路徑 7 圖 圖是另一種非線性結構，它比樹更復雜、更一般化，因此可以把樹看成是簡單的圖。 圖的應用范圍極廣，近年來已經(jīng)滲入到各個領域，如語言學、邏輯學、數(shù)學、物理、化學、計算機科學和各種工程學領域。 比樹的結構更加復雜 沒有嚴格的層次 結點之間的關系是任意的 回憶：離散數(shù)學中關于圖的概念7.1 圖的定義和基本術語基本概念：什么是圖無向圖、邊、度有向圖、弧、出度和入度鄰接結點、鄰接邊路徑、連通性、連通分支生成樹特殊圖：完全圖、稀疏圖、帶權圖一、圖的定義一、圖的定義圖圖:由頂點集V和連接頂點的邊（?。┘疎所組成的結構，記作G=(V,E)； V是

3、頂點(元素)的有窮非空集， E是兩個頂點之間的關系的集合。12343124V=1,2,3,4E=,V=1,2,3,4E=(1,2),(1,3),(2,4),(1,4),(3,4) 圖的數(shù)據(jù)對象：圖的頂點集合 圖的數(shù)據(jù)關系：圖中各頂點之間的關系，就是邊（或稱作弧） 注意：上述關系是非線性的，多對多的關系，即前驅(qū)/后繼關系都不是唯一的！ 圖中的數(shù)據(jù)元素具有相同特性，稱為頂點； 若頂點a,c之間的關系為有序?qū)τ行驅(qū)?且E 則稱為從a到c的一條弧弧/有向邊有向邊； a是的弧尾弧尾， c是的弧頭弧頭； 此時的圖G稱為有向圖有向圖。 例 G1=V1,E1, V1=A,B,C,D,E E1=, 二、基本概念

4、二、基本概念ABCEDG1 圖中若頂點之間的關系有則必，即為無序?qū)Γ╝,c）； 則無序?qū)Γ╝,c）表示a和c之間的一條邊， 此時的圖G稱為無向圖。 例 G2=V2,E2, V2=A,B,C,D ABCDE2=（A,B）,（A,C）,（A,D）,（B,D）G2 若無向圖G中任意兩點間都有一條邊，則稱此圖G為無向完全圖無向完全圖。即n個頂點的無向完全圖有n(n-1)/2條邊；v1Av2Cv3G1 G2 G3 G4 G5 Bv1v1v2DACBDEe=1(1-1)/2 =0e=2(2-1)/2 =1e=3(3-1)/2 =3e=4(4-1)/2 =6e=5(5-1)/2 =10 若有向圖G中任意一個

5、頂點到其余各點間均有一條弧，則稱G為有向完全圖有向完全圖。即n個頂點的有向完全圖有n(n-1)條??；123G1 G2 G3112e=1(1-1) =0e=2(2-1) =2e=3(3-1) =6 圖的邊或弧具有與其相關的數(shù)值，這個數(shù)值稱為權(weight) 。 網(wǎng)(Network)-邊(弧)上加權的圖。123無向網(wǎng)G14ABC41559943有向網(wǎng)G2 有很少的邊或弧的圖稱為稀疏圖； 反之稱為稠密圖。若一個圖G1=(V1，E1)是從G中選取部分頂點和部分邊（或?。┙M成，即V1V，E1E，則稱G1是G的子圖子圖。123G412G1341G2341G4123G34G1,G2,G3是G的子圖 G4不

6、是G的子圖2相鄰相鄰：若無向圖中（i，j）E i，j相鄰，若有向圖中 E i，j相鄰； i與j互為鄰接點，或者稱i與j相關聯(lián)。123456度度與頂點x相關聯(lián)的邊(x,y)的數(shù)目,稱為x的度度，記作TD(x) 或D(x)；25413G1 TD(1)=1 TD(2)=3 TD(3)=0出度出度以頂點x為弧尾的弧的數(shù)目,稱為x的出出度度，記作OD(x)。入度入度以頂點x為弧頭的弧的數(shù)目, 稱為x的入度入度，記作ID(x)。ABCG2OD(A)=1OD(B)=2OD(C)=0ID(A)=1 ID(B)=1ID(C)=1TD(A)=OD(A)+ID(A)=2 TD(B)=OD(B)+ID(B)=3TD(

7、C)=OD(C)+ID(C)=1注意： 無向圖：度 有向圖：入度，出度。 有向圖中某結點的度入度出度。路徑路徑：圖中從頂點x到達頂點y的頂點序列稱為路徑；有向圖中路徑也是有向的，路徑上的邊或弧的數(shù)目稱為路徑的長度； （1）序列中頂點無重復出現(xiàn)簡單路徑； （2）若首尾頂點相同回路； （3）若首尾相同且序列中間頂點無重復出現(xiàn)簡單回路 ；12341234 對無向圖G： 若從頂點vi到vj有路徑,則稱vi和vj是連通連通的。 若圖G中任意兩頂點是連通的,則稱G是連通圖連通圖。123456GAFECBGDAFECBG1DG2G3 連通分量連通分量- -是無向圖中的是無向圖中的極大連通子圖極大連通子圖。G

8、GG有三個連通分量有三個連通分量否則不連通不連通，就存在若干連通分量連通分量。如：G為連通圖，而G為非連通圖。 對有向圖G 若在圖G中,每對頂點vi和vj之間, 從vi到vj,且從vj 到vi都存在路徑,則稱G是強連通圖強連通圖。 若圖G是G的一個極大強連通子圖極大強連通子圖,則稱G是G的一個 強連通分量強連通分量。BCG1ADBC G11 是是G1的強連通分量強連通分量ADBC G12不是不是G1的強連通分量強連通分量ADBCG2ADBCG21ADG22G2有兩個強連通分量有兩個強連通分量 設G=(V,E),G=(V,E),V=V,若G是連通圖, G是G的一個極小連通子圖極小連通子圖, ,

9、則G是G的一棵生成樹生成樹。 注：生成樹包含圖中全部頂點，但只有足以構成一顆樹的n-1條邊。EDGBCAEDT1BCAEDT4BCAEDT3BCAEDT2BCAG的多棵生成樹 若有向圖G有且僅有一個頂點的入度為0，其余頂點的入度為1,則G是一棵有向樹有向樹。 注意：一個有向圖的有向森林由若干棵有向樹組成，含有圖中全部頂點，但只有足以構成若干棵不相交的有向樹的弧。EDT1BCAEDT2BCAEBT3ACEEDT4BCAEDT5BCAEDT6BCAT1,T2,T3,T4是有向樹有向樹T5,T6不是有向樹有向樹 有向圖的生成樹/生成森林。EDGBCAEBFADFFC三、圖的基本操作（1） Creat

10、eGraph(&G, V, VR); DestroyGraph(&G); LocateVex(G, u); GetVex(G, v); PutVex(&G, v, value); FirstAdjVex(G, v); NextAdjVex(G, v, w);圖的基本操作（2） InsertVex(&G, v); DeleteVex(&G, v); InsertArc(&G, v, w); DeleteArc(&G, v, w); DFSTraverse(G, v, Visit(); BFSTraverse(G, v, Visit();圖的

11、存儲結構考慮 比樹更加復雜的非線性結構 無法直接用順序結構表示結點之間的關系（但是可以間接表示） 自然的鏈式結構：需要一個良好的鏈式結構7.2 圖的存儲結構一、 數(shù)組表示法/鄰接矩陣頂點數(shù)組頂點數(shù)組-用一維數(shù)組存儲頂點(元素)鄰接矩陣鄰接矩陣-用二維數(shù)組存儲頂點(元素)之間的關系(邊或弧) 143G2 1 2 3 41 0 0 1 12 0 0 0 03 1 0 0 14 1 0 1 0 M=例1鄰接矩陣鄰接矩陣 1 2 3 41 2 3 4頂點數(shù)組頂點數(shù)組V1.41.1 1.1 鄰接矩陣鄰接矩陣1、不帶權值設圖中有n個頂點：Ann aij 1 E 0或 否則對稱123411110110111

12、10000非0元素個數(shù)12341 2 3 444不對稱12341110000010100000第i非0元素個數(shù)=對應頂點的度第i非0元素個數(shù)=對應頂點的度12341 2 3 4442、帶權值 aij Vij E 0或 否則123453650230462400002536412341 2 3 4441.2 圖的數(shù)組表示法數(shù)據(jù)結構定義/圖的類型和弧的定義#define INFINITY INT_MAX /最大值#define MAX_VERTEX_NUM 20 /最大頂點數(shù)typedef enum DG, DN, AG, AN GraphKind;/有向圖，有向網(wǎng)，無向圖，無向網(wǎng)typedef s

13、truct ArcCellVRType adj; /頂點關系，無權圖0或1，帶權圖為權InfoType *info; /該弧相關信息的指針ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;/圖的數(shù)組定義typedef structVertexType vexsMAX_VERTEX_NUM; /頂點向量AdjMatrix arcs; /鄰接矩陣int vexnum, arcnum; /圖的當前頂點數(shù)和弧數(shù)GraphKind kind; /圖的種類標志MGraph;圖的數(shù)組表示的應用 鄰接矩陣中的含義 無向圖與對稱性 頂點的度 權 建立在鄰接矩陣上的算法舉

14、例： P162的算法7.1和算法7.2，用于構造圖和構造無向網(wǎng)二、鄰接表二、鄰接表12341234data firstadj逆鄰接表：1234data firstadj圖的鄰接表存儲數(shù)據(jù)結構定義#define MAX_VERTEX_NUM 20 typedef struct ArcNodeint adjvex; /該弧所指向的頂點的位置struct ArcNode *nextarc; /指向下一條弧的指針I(yè)nfoType *info; /該弧相關信息的指針ArcNode;typedef struct VNodeVertexType data; /頂點信息ArcNode *firstarc; /

15、指向第一條依附該頂點的弧的指針VNode, AdjListMAX_VERTEX_NUM;typedef structAdjList vertices;int vexnum, arcnum; /圖的當前頂點數(shù)和弧數(shù)int kind; /圖的種類標志ALGraph;有向圖的十字鏈表十字鏈表- 將鄰接表和逆鄰接表合并而成的鏈接表。 CBADABCD 1 2 3 41 GG的逆逆鄰接表鄰接表134 ABCD 1 2 3 44 3 G的鄰接表鄰接表2 2ABCD1234G的十字鏈表十字鏈表3 21 24 2 14 4 3 24 4 1 1 4 三、有向圖的十字鏈表三、有向圖的十字鏈表四、 無向圖的鄰接多

16、重表鄰接多重表-另一種鏈式存儲結構EDFBACGABCDEF012023013024034056序號序號 data firstedgedata firstedge(A,B)(A,C)(B,C)(B,D)(C,D)(E,F)隱含的鏈接表：隱含的鏈接表： A (1,2) (1,3) B (1,2) (2,3) (2,4) C (1,3) (2,3) (3,4) D (2,4) (3,4) E (5,6) F (5,6)ma vi vj vil vjlma vi vj vil vjl123456 圖的一條邊或弧用一個“頭結點頭結點”表示，其中： markmark-標志域，可用以標記該條邊是否被搜索過

17、； vivi和和vjvj-該條邊依附的兩個頂點在圖中的位置； vilvilinkink-指向下一條依附于頂點vi的邊； vjlvjlinkink-指向下一條依附于頂點vj的邊。 0 1 2mark vi vj vilink vjlinkmark vi vj vilink vjlinkdata firstedgedata firstedgeA表示頂點A的頭結點頭結點表示邊或弧(v1,v2)的表表結點結點 圖的一個頂點用一個“頭結點頭結點”表示，其中： datadata域域存儲和該頂點相關的信息， firstedgefirstedge域域存儲第一條依附于該頂點的邊。表表結點結點7.3 圖的遍歷一、

18、定義：從圖的某頂點出發(fā)，訪問圖中每個頂點一次且僅一次。 圖的遍歷算法：l深度優(yōu)先搜索（ Depth-First Search ）DFSl廣度優(yōu)先搜索（ Breadth-First Search ）BFS一、深度優(yōu)先搜索遍歷（一、深度優(yōu)先搜索遍歷（dfsdfs） DFS（Depth-First Search）算法是圖論中最重要的算法之一，它的思路可以用來表述。下圖是1690年獨裁者威廉王修筑的迷宮示意圖，現(xiàn)遺址在奧地利。xbdefclghijak迷宮法則 任務是從事先未知結構的迷宮入口出發(fā)，每個走廊都要搜索，再從入口退出。為了不兜圈子盡快退出，要記住哪些走廊已經(jīng)走過，沿著未走過的走廊盡可能地走下

19、去，走到已無未走過的走廊可走時，沿來路返回，到某一路口，發(fā)現(xiàn)可通往一條未走過的走廊時，沿此走廊搜索，依次類推，直至完成任務。迷宮法則一直往前走碰壁就回頭換條路走沿途要記錄走過的路線老鼠走迷宮dfs1、基本遍歷算法的描述： 1973年，用上述迷宮思想，Hopcroft和Tarjan設計了下面有效的DFS算法。 dfs(v0)從v0出發(fā)深度遍歷1、訪問v0visit(v0)；2、依次從v0未被訪問未被訪問的鄰接點出發(fā)深度遍歷。深度優(yōu)先搜索過程：v0v1v3v5v4v2v6v7搜索回溯dfs(v0)v0v1v3v5v4v2v7v6序列：序列：v0- v1 -v3- v5 -v4- v2 v6- v7

20、dfs(v1)dfs(v3)dfs(v5)dfs(v4)dfs(v6)dfs(v7)dfs(v2)DFS生成樹搜索過程形成DFS生成樹，如下圖：v0v1v3v5v4v2v7v62、DFS算法的實現(xiàn)： dfs(v0)從v0出發(fā)深度遍歷1、訪問v0visit(v0)；2、依次從v0未被訪問未被訪問的鄰接點出發(fā)深度遍歷。 未被訪問：visitedi=1（訪問）/0（未訪問）； 求鄰接點：firstadj，nextadj； nodes(G)返回圖G的結點數(shù)。 求鄰接點： firstadj(i)返回頂點i的第一個鄰接點，找不到返回0；如：w=firstadj(1);/w2; nextadj(i,j)返回

21、頂點i位于結點j后的鄰接點，找不到返回0；如：w=nextadj(1,2);/w=3;1234基于以上討論，得dfs算法如下：void dfs(Graph G,int v0) visit(v0); visitedv0=ture; w=firstadj(G, v0); while(w!=0) if(visitedw=false) dfs(G,w); w=nextadj(G,v0,w); 123458679遍歷整個圖的算法如下：void dfs-travel(Graph G) for (i=1;i=nodes(G);i+) visiedi=false; for (i=1;i=nodes(G);i+

22、) if(visitedi=false) dfs(G,i);1234586793、DFS算法的應用：1、設計算法判斷圖G是否連通。2、設計算法求圖G的連通分量數(shù)。思考題：設計算法求圖G的dfs生成樹；相鄰數(shù)相加質(zhì)數(shù)問題；求路徑問題； 可以看出，用dfs對迷宮進行搜索，可以找出穿過迷宮的路，但是不一定是最短的。如果要找出最短的，則對迷宮進行bfs搜索。二、廣度優(yōu)先搜索（BFS） BFS（Breadth-First Search）算法的描述bfs(v0)從v0出發(fā)廣度遍歷1、訪問v0visit(v0)；2、依次訪問v0的鄰接點；3、假設最近一層訪問的結點次序為vk1，vk2，vkm，依次訪問vk1

23、，vk2，vkm的鄰接點；廣度優(yōu)先搜索過程：v0v1v3v5v4v2v6v7bfs(v0)v0v1v3v5v4v2v7v6序列：序列：v0-v1-v2-v3-v4- v6- v7-v5搜索BFS生成樹搜索過程形成BFS生成樹，如下圖：v0v1v3v5v4v2v7v6BFS算法的一個顯著特點是：層次性。所以可以用來求兩點間最短路徑。01入口出口0117.4 圖的連通性 深度優(yōu)先遍歷（DFS)生成樹 廣度優(yōu)先遍歷（BFS）生成樹 DFS生成森林 BFS生成森林一、DFS生成樹：假定從A A出發(fā)DFSDFS遍歷圖G：FDBCAGHEI圖GABABABADCDFDBCAFDBCAIFDBCAIGDFS

24、生成樹T1FDBCAGHEI圖GFDBCAIGHFDBCAIGHEFDBCAIGHEDFS生成樹T2ECBDAIGFH二、 BFSBFS生成樹生成樹FDBCAGHEI圖G假定從A A出發(fā)BFSBFS遍歷圖G：AABABFABEFABEFCABEFCDABEFCDIFDBCAGHEI圖GABEFCDIHGABEFCDIHABEFCDIHGABEFCDIHGBFS生成樹T1BFS生成樹T2三、 DFSDFS生成森林生成森林CKIJADEBFGH從A A出發(fā)，得樹T1：T2CADEBF圖GT3T1從G G出發(fā),得樹T2：CADEBFT1GHT2CADEBFT1GHKIJ從I I出發(fā),得樹T3：四、

25、BFSBFS生成森林生成森林CKIJADEBFGH從A A出發(fā)，得樹T1：T2圖GT3T1從G G出發(fā),得樹T2：AT1GHT2T1GHKIJ從I I出發(fā),得樹T3：CDEBFACDEBFACDEBF7.5 有向無環(huán)圖及其應用 最小生成樹 拓撲排序 最短路徑 關鍵路徑一、 最小生成樹最小生成樹 假設在n個城市之間建立一個通信網(wǎng)絡，最少需要n-1條邊（最多為n(n-1)/2）。 邊上賦予相應的代價。 可以有多棵生成樹，那么選擇一棵代價最小的生成樹！ 要在 n 個小區(qū)間建立能源網(wǎng)，現(xiàn)在要考慮的問題如何在保證 n 個小區(qū)連通的前提下最節(jié)省經(jīng)費?上述問題即要使得生成樹各邊權值之和，即：)(),()(T

26、EvuuvwTW12354435323136 問題描述： 在有n個頂點的帶權連通圖G中，選取條邊以構成一棵樹，要求所選邊權值之和最小。這樣的樹稱為圖G的。最小生成樹的性質(zhì) 假設N=（V，E）是一個連通網(wǎng)，U是V的一個非空子集。若（u,v）是一條具有最小權值的邊，那么必存在一棵包含邊（u,v）的最小生成樹，其中u是U中的一個頂點，v是V-U中的一個頂點。( (一一)prim)prim算法算法( (普里姆普里姆) )1、基本思想： 在滿足如下條件選擇權值最小權值最小的邊一端已入選，另一端未入選。 N=（V，E），TE是N上最小生成樹的邊的集合。（1）初始化：U=u0, TE=；（2）在所有uU,

27、vV-U的邊（u,v）E中找一條代價最小的邊（u0,v0）并入集合TE，同時v0并入U；（3）重復（2），直至U=V。2、求解實例求下圖的最小生成樹：123541235443532313612354最小生成樹不唯一，但權值之和相同。 例：求例：求G G的最小生成樹的最小生成樹 CADEBF圖G3718745561.普里姆普里姆( (prim)prim)算法 以選頂點為主以選頂點為主DTCD5TCAD15CADB3156CADEB3156TTT圖G的最小生成樹 CADEBF圖G3718745561.普里姆普里姆( (prim)prim)算法 以選頂點為主以選頂點為主6CADEB3156TF4另一

28、最小生成樹CADEBF圖G3718745561.普里姆普里姆( (prim)prim)算法 以選頂點為主以選頂點為主DTDT6TTTB5ADB35ADB35C1ADB35C1E6另一最小生成樹 CADEBF圖G3718745561.普里姆普里姆( (prim)prim)算法 以選頂點為主以選頂點為主6CADEB316TF45Prim算法的關鍵 按照最小生成樹的性質(zhì)進行頂點擴張。 每擴展一個頂點，在兩個頂點集合中都要更新當前的最小邊。 以鄰接矩陣為存儲結構，時間復雜度為O（n2），與邊數(shù)無關！( (二二)Kruskal)Kruskal算法算法( (克魯斯卡爾克魯斯卡爾) )1、基本思想： 在滿足

29、如下條件選擇權值最小權值最小的邊和已選邊不構成回路。 N=（V，E），TE是N上最小生成樹的邊的集合。（1）初始化：T=（V，），即TE=；（2）在E中選擇代價最小的邊，若該邊依附的頂點落在T中不同的連通分量上，則將此邊加入到TE中，否則選擇下一條代價最小的邊；（3）重復（2），直至所有頂點都在同一連通分量上為止。2、求解實例求下圖的最小生成樹：1235443532313612354最小生成樹不唯一，但權值之和相同。克魯斯卡爾（克魯斯卡爾（KruskaiKruskai) )算法，以選邊為主以選邊為主CADEBF圖G371874556TT6TTTCACAB113CAB13EF4CAB13EF4D

30、5CADEBF31456克魯斯卡爾（克魯斯卡爾（KruskaiKruskai) )算法，以選邊為主以選邊為主CADEBF圖G371874556TT6TTTCACAB113CAB13EF4CAB13EF4DCADEBF314655刪除權最大的邊，保留刪除權最大的邊，保留n-1n-1條條CADEBF圖G3718745566CADEBF371745566CADEBF37145566圖G圖GCADEBF圖G3718745566刪除權最大的邊，保留刪除權最大的邊，保留n-1n-1條條CADEBF圖G3718745566CADEBF314556TCADEBF31456圖GCADEBF3145566圖GKr

31、uskal算法的特征 按照最小生成樹的性質(zhì)進行邊的擴展 每擴展一條邊，都需要判斷有無形成回路 以鄰接矩陣為存儲結構時，時間復雜度可以達到O（eloge)，與頂點數(shù)無關！二、 拓撲排序拓撲排序拓撲排序 偏序關系的一個序列 拓撲排序的應用：選課次序 工程施工流程圖：AOV網(wǎng)（一）問題描述：（一）問題描述：由多項子工程（活動）組成，子工程（活動）之間存在制約關系。用圖表示工程，頂點表示子工程（活動），弧表示活動間的制約關系。(1)工程是否能順利完成？ 圖中是否存在回路？(2)工程需要多少時間完成？(3)哪些是關鍵性工程？（二）拓撲排序方法及實現(xiàn)（二）拓撲排序方法及實現(xiàn)(AOV(AOV網(wǎng)網(wǎng)) )1、如

32、何判斷AOV網(wǎng)中是否存在有向回路？解決方法：(1)用深度遍歷要做許多試探性工作；(2)用產(chǎn)生頂點序列的方法拓撲排序；如果能產(chǎn)生包含的拓撲序列則說明AOV網(wǎng)中無回路，否則有回路。2、拓撲排序步驟： (1)選擇一個沒有前驅(qū)的頂點(入度為0)的頂點v；(2)此頂點排序后即刪除之，并刪除所有以它為尾的弧（將此弧的頭的頂點的入度減1）；(3)重復(1)、(2)，直到重復上述過程，直至所有頂點都被排序(找不到入度為0的頂點)為止。123456求下圖的拓撲序列：3、求解實例12345653124563465123456312345612354624565123456465312345612345664512345646245653123456123456三、 最短路徑問題引入：問題引入： 兩類問題：(1)從單點到其余頂點的最短路徑；(2)各點間的最短路徑。123456