1、,第7章 圖 7.1 圖的定義和術(shù)語(yǔ) 圖(Graph)是一種數(shù)據(jù)結(jié)構(gòu)，形式定義 Graph = ( V , R ) 其中：V = x | xdataobject R = VR VR = | p( x,y ) ( x,y V ) p( x,y )表示從x到y(tǒng)的一條通路,圖的抽象數(shù)據(jù)類型定義： ADT Graph 數(shù)據(jù)對(duì)象V:V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂 點(diǎn)集。 數(shù)據(jù)關(guān)系R： R=VR VR=|v,wV且P(v,w),表示從v到w的弧， 謂詞P(v,w)定義了弧的意義或信息 基本操作P： GreateGraph ( ADT Graph,例如： G1 = ( v1 , A1 ) 其中：

2、v1= v1,v2,v3,v4, A1= , , , ,例如： G2 = ( v2 , E2 ) 其中： v2= v1,v2,v3,v4, v5 E2= (v1,v2), (v1,v4), (v2,v3) (v2,v5), (v3,v4), (v3,v5) ,設(shè)圖中頂點(diǎn)數(shù)為n，邊或弧數(shù)為e，則：,對(duì)于無向圖，e的取值范圍為0n(n-1)/2,具有n(n-1)/2條邊的無向圖稱為完全圖,對(duì)于有向圖，e的取值范圍為0n(n-1),具有n(n-1)條邊的有向圖稱為有向完全圖,和圖中邊相關(guān)的數(shù)叫作權(quán)（weigth）,帶權(quán)的圖稱為網(wǎng),頂點(diǎn)的度是和該頂點(diǎn)相關(guān)聯(lián)的邊的數(shù)目。記作TD(v),以頂點(diǎn)v為頭的弧的

3、數(shù)目稱為v的入度。記作ID(v),以頂點(diǎn)v為尾的弧的數(shù)目稱為v的出度。記作OD(v),頂點(diǎn)v的度 TD(v) =ID(v) + OD(v),鄰接點(diǎn)：對(duì)于無向圖G= ( V,E )，如果邊(v,v)E,則稱頂 點(diǎn)v和v互為鄰接點(diǎn),路徑：路徑是頂點(diǎn)的序列V=Vi0,Vi1, Vin， 滿足(Vij-1,Vij)E 或 E,(1jn) 路徑長(zhǎng)度：沿路徑邊的數(shù)目或沿路徑各邊權(quán)值之和 回路：第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑 簡(jiǎn)單路徑：序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑 簡(jiǎn)單回路：除了第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)外，其余頂點(diǎn)不 重復(fù)出現(xiàn)的回路 連通：從頂點(diǎn)V到頂點(diǎn)W有一條路徑，則說V和W是連通的 連通圖：無向圖中任

4、意兩個(gè)頂點(diǎn)都是連通的 連通分量：無向圖中的極大連通子圖 強(qiáng)連通圖：有向圖中，如果對(duì)每一對(duì)Vi,VjV, ViVj,從Vi到 Vj 和從Vj到 Vi都存在路徑，則稱G是強(qiáng)連通圖 強(qiáng)連通分量：有向圖中的極大強(qiáng)連通子圖,有向完全圖：具有n(n-1) 條邊的有向圖 無向完備圖：具有n(n-1)/2 條邊的無向圖 權(quán)：與圖的邊或弧相關(guān)的數(shù) 網(wǎng)：帶權(quán)的圖,7.2 圖的存儲(chǔ)結(jié)構(gòu) 多重鏈表,實(shí)際中不適用,數(shù)組表示法（鄰接矩陣） 設(shè)G=(V,E)是有n1個(gè)頂點(diǎn)的圖，G的鄰接矩陣A是具有以下性質(zhì)的n階方陣,圖的數(shù)組（鄰接矩陣）存儲(chǔ)表示 #define INFINITY INT_MAX #define MAX_VE

5、RTEX_NUM 20 typedef enum DG , DN , UDG , UDN GraphKind ; typedef struct ArcCell VRType adj ; InfoType * info ; ArcCell,djMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; typedef struct VertexType vexs MAX_VERTEX_NUM ; AdjMatrix arcs ; int vexnum , arcnum ; GraphKind kind ; MGraph ;,特點(diǎn)： 無向圖的鄰接矩陣對(duì)稱，可壓縮存儲(chǔ)；有n個(gè)頂點(diǎn)的無向圖

6、需存儲(chǔ)空間為n(n+1)/2 有向圖鄰接矩陣不一定對(duì)稱；有n個(gè)頂點(diǎn)的有向圖需存儲(chǔ)空間為n 無向圖中頂點(diǎn)Vi的度TD(Vi)是鄰接矩陣中第i行元素之和 有向圖中， 頂點(diǎn)Vi的出度是鄰接矩陣中第i行元素之和 頂點(diǎn)Vi的入度是鄰接矩陣中第i列元素之和 易于實(shí)現(xiàn)基本操作,采用數(shù)組（鄰接矩陣）表示法，構(gòu)造圖G Status CreateGraph ( MGraph ,采用數(shù)組（鄰接矩陣）表示法，構(gòu)造無向網(wǎng)G Status CreateUDN ( MGraph return OK ,鄰接表表示,圖的鄰接表存儲(chǔ)表示 #define MAX_VERTEX_NUM 20 typedef struct ArcNo

7、de int adjvex ; struct ArcNode * nextarc ; InfoType * info ; ArcNode ; typedef struct Vnode VertexType data ; ArcNode * firstarc ; Vnode , AdjList MAX_VERTEX_NUM ; typedef struct AdjList Vertices; int vexnum , arcnum ; int kind ; ALGraph ;,特點(diǎn) 若無向圖中有n個(gè)頂點(diǎn)、e條邊，則需n個(gè)頭結(jié)點(diǎn)和2e個(gè)表結(jié)點(diǎn) 無向圖中頂點(diǎn)Vi的度為第i個(gè)單鏈表中的結(jié)點(diǎn)數(shù) 有向圖中

8、 頂點(diǎn)Vi的出度為第i個(gè)單鏈表中的結(jié)點(diǎn)個(gè)數(shù) 頂點(diǎn)Vi的入度為整個(gè)單鏈表中鄰接點(diǎn)域值是i的結(jié)點(diǎn)個(gè)數(shù) 逆鄰接表：有向圖中對(duì)每個(gè)結(jié)點(diǎn)建立以Vi為頭的弧的單鏈表,十字鏈表-有向圖的另一種存儲(chǔ)結(jié)構(gòu),有向圖的十字鏈表存儲(chǔ)表示 #define MAX_VERTEX_NUM 20 typedef struct ArcBox int tailvex , headvex ; struct ArcBox *hlink , *tlink ; InfoType *info ; ArcBox ; typedef struct VexNode VertexType data ; ArcBox *firstin, *firs

9、tout ; VexNode ; typedef struct VexNode xlist MAX_VERTEX_NUM ; int vexnum , arcnum ; OLGraph ;,采用十字鏈表存儲(chǔ)結(jié)構(gòu)，構(gòu)造有向圖 Status CreateDG ( OLGraph ,無向圖的鄰接多重表存儲(chǔ)表示 #define MAX_VERTEX_NUM 20 typedef emnu unvisited , visited VisitIf ; typedef struct EBox VisitIfmark ; int ivex , jvex ; struct EBox * ilink , *jli

10、nk ; InfoType * info ; Ebox ; typedef struct VexBox VertexType data ; EBox * firstedge ; VexBox ; typedef struct VexBox adjmulist MAX_VERTEX_NUM ; int vexnum , edgenum ; AMLGraph ;,鄰接多重表-無向圖的另一種存儲(chǔ)結(jié)構(gòu),7.3 圖的遍歷,圖的遍歷：從圖中某一頂點(diǎn)出發(fā)，對(duì)圖中所有頂點(diǎn)訪問一次且僅訪問一次。,在線性結(jié)構(gòu)中，元素之間的關(guān)系為前驅(qū)和后繼； 在樹結(jié)構(gòu)中，結(jié)點(diǎn)之間的關(guān)系為雙親和孩子； 在圖結(jié)構(gòu)中，頂點(diǎn)之間的關(guān)系為鄰

11、接。,7.3 圖的遍歷 不同結(jié)構(gòu)中邏輯關(guān)系的對(duì)比,一、深度優(yōu)先搜索(Depth First Search) 方法：從圖的某一頂點(diǎn)V出發(fā)，訪問此頂點(diǎn)；然后依次從V的未被訪問的鄰接點(diǎn)出發(fā)，深度優(yōu)先搜索圖，直至圖中所有和V有路徑相通的頂點(diǎn)都被訪問到；若此時(shí)圖中尚有頂點(diǎn)未被訪問，則另選圖中一個(gè)未被訪問的頂點(diǎn)作起點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問為止。,深度優(yōu)先搜索序列：,V1,V2,V3,V1,V4,V5,V6,V7,V2,V8,V7,V3,V4,V5,V3,V6,V2,V8,v1,v2,v4,v8,v5,v3,v6,v7,遍歷操作中要解決的關(guān)鍵問題：, “從圖的某一頂點(diǎn)V出發(fā)” ，如何選取出

12、發(fā)頂點(diǎn)。,解決方案：按存儲(chǔ)結(jié)構(gòu)排列順序的第一個(gè)。,“依次從V的未被訪問的鄰接點(diǎn)出發(fā)”中“依次”,解決方案：按基本操作，先找第一鄰接點(diǎn)，再找下一個(gè),循環(huán)查找各鄰接點(diǎn)。,“未被訪問的”鄰接點(diǎn),解決方案：設(shè)訪問標(biāo)志數(shù)組visited , 非連通圖,解決方案：從任意一個(gè)未被訪問的結(jié)點(diǎn)出發(fā)調(diào)用算法,算法7.4 7.5 深度優(yōu)先算法 Boolean visited MAX ; Status( *VisitFunc )( int v ) ; void DFSTraverse ( Graph G , Status ( *Visit )( int v ) ) VisitFunc = Visit ; for (

13、v = 0 ; v G .vexnum ; +v ) visited v = FALSE ; for ( v = 0 ; v G .vexnum ; +v ) if ( !visited v ) DFS ( G , v ) ; void DFS ( Graph G , int v ) visited v = TRUE ; VisitFunc( v ) ; for(w=FirstAdjVex(G ,v) ; w ; w=NextAdjVex(G ,v ,w ) ) if ( !visited w ) DFS ( G , w ) ; ,問題：判斷給定圖是否是連通圖？多少個(gè)連通分量,深度遍歷：V1,

14、V2 ,V4 ,V8 ,V5 ,V3 ,V6 ,V7,void DFS ( Graph G , int v ) visited v = TRUE ; VisitFunc( v ) ; for(w=FirstAdjVex(G ,v) ; w ; w=NextAdjVex(G ,v ,w ) ) if ( !visited w ) DFS ( G , w ) ; ,鄰接矩陣存儲(chǔ)結(jié)構(gòu) void DFS ( MGraph G , int v ) visited v = TRUE ; VisitFunc( v ) ; for(j=0 ; jG.vexnum ; j+ ) if ( G.arcsvj.ad

15、j=1 ,鄰接表存儲(chǔ)結(jié)構(gòu) void DFS ( ALGraph G , int v ) visited v = TRUE ; VisitFunc( v ) ; p=G.verticesv.firstarc ; while ( p ) if (!visitedp-adjvex ) DFS(G,p-adjvex); p = p-nextarc; ,時(shí)間復(fù)雜度：O ( n2 ),時(shí)間復(fù)雜度：O ( n + e ),二、廣度優(yōu)先搜索(Breadth First Search) 方法：從圖的某一頂點(diǎn)V出發(fā)，訪問了V之后，依次訪問V的各個(gè)未曾訪問過的鄰接點(diǎn)；然后分別從這些鄰接點(diǎn)出發(fā)，廣度優(yōu)先搜索圖，直至圖

16、中所有已被訪問的頂點(diǎn)的鄰接點(diǎn)都被訪問到；若此時(shí)圖中尚有頂點(diǎn)未被訪問，則另選圖中一個(gè)未被訪問的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問為止。,廣度遍歷：V1 V2 V3 V4 V5 V6 V7 V8,void BFSTraverse(Graph G,Status(*visit)(int v) for ( v = 0 ; v G .vexnum ; +v ) visited v = FALSE ; InitQueue( Q ) ; for ( v = 0 ; v G .vexnum ; +v ) if ( !visited v ) visited v = TRUE ; visit( v

17、 ) ; EnQueue ( Q , v ) ; while ( !QueueEmpty( Q ) ) DeQueue( Q , u ) ; for(w=FirstAdjVex(G,u);w;w=NextAdjVex(G,u,w) if ( !visited w ) visited w = TRUE ; visit( w ) ; EnQueue(Q,w) /if /while /if ,時(shí)間復(fù)雜度： 鄰接矩陣存儲(chǔ)：O ( n2 ) 鄰接表存儲(chǔ)：O ( n+e ),問題：二叉樹按層次遍歷,問題：迷宮問題,7.4 圖的連通性問題 一、無向圖的連通分量和生成樹,對(duì)無向非連同圖進(jìn)行深度優(yōu)先遍歷,三次調(diào)

18、用得到的訪問序列為：,ALMJBFC,DE,GKHI,A,B,C,D,E,F,G,H,I,J,K,L,M,生成樹：所有頂點(diǎn)均由邊連接在一起，但不存在回路的圖。 深度優(yōu)先生成樹與廣度優(yōu)先生成樹 生成森林：非連通圖每個(gè)連通分量的生成樹一起組成非連通圖的生成森林。 說明 一個(gè)圖可以有許多棵不同的生成樹 所有生成樹具有以下共同特點(diǎn)： 生成樹的頂點(diǎn)個(gè)數(shù)與圖的頂點(diǎn)個(gè)數(shù)相同 生成樹是圖的極小連通子圖 一個(gè)有n個(gè)頂點(diǎn)的連通圖的生成樹有n-1條邊 生成樹中任意兩個(gè)頂點(diǎn)間的路徑是唯一的 在生成樹中再加一條邊必然形成回路 含n個(gè)頂點(diǎn)n-1條邊的圖不一定是生成樹,建立非連通圖G的深度優(yōu)先生成森林 void DFSForest ( Graph G