圖的定義和術語

《圖的定義和術語》由會員分享，可在線閱讀，更多相關《圖的定義和術語（47頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、單擊此處編輯母版標題樣式,*,*,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,第七章 圖,7.1,圖的定義和術語,7.2,圖的存儲結構,7.2.1,數(shù)組表示法,7.2.2,鄰接表,7.3,圖的遍歷,7.3.1,深度優(yōu)先搜索,7.3.2,廣度優(yōu)先搜索,7.4,圖的連通性問題,7.4.3,最小生成樹,7.5,有向無環(huán)圖及其應用,7.5.1,拓撲排序,7.6,最短路徑,7.6.1,從某個源點到其余各頂點的最短路徑,7.6.2,每一對頂點之間的最短路徑,7.1,圖的,定義和術語,圖的定義：,是一種多對多的結構關系，每個元素可以有零個或多個直接前趨；零個或多個直接后繼。圖是由頂點集合,(,

2、vertex),及頂點間的關系集合組成的一種數(shù)據(jù)結構：,Graph(V,R),其中,V=v|v,某個數(shù)據(jù)對象,是頂點的有窮非空集合；,R=VR=(v,w)|v,w,V,基本術語：,1.有向圖與無向圖,在有向圖中，頂點對,是有序的。在無向圖中，頂點對,(,x,y),是無序的。有向邊又可稱為,弧,中,vi,稱為,弧尾,或初始點，,vj,稱為,弧頭,或終端點。,5,3,6,7,2,1,4,有向圖,V=1,2,3,4,5,6,7,VR=,無向圖,5,3,6,7,2,1,4,V=1,2,3,4,5,6,7,VR=(1,3),(3,4),(4,5),(1,2),(2,6),(2,7),(6,7),(5,6

3、),(1,5),(,1,7),2.鄰接點及關聯(lián),若無向圖中存在邊,(,v,u)，,則稱頂點,v,和,u,互為鄰接點；邊,(,v,u),依附于頂點,v,和,u；,或者說邊,(,v,u),和頂點,v,和,u,相關聯(lián)。,3.,頂點的度、入度、出度,在無向圖中：頂點,V,的度,=,與,V,相關聯(lián)的邊的數(shù)目,在有向圖中：,頂點,V,的出度,=,以,V,為狐尾的有向邊數(shù),頂點,V,的入度,=,以,V,為狐頭的有向邊數(shù),頂點,V,的度,=,V,的出度,+,V,的入度,V0,V4,V3,V1,V2,V0,V1,V2,V3,4.路徑、回路,無向圖,G=（V，E）,中的頂點序列,v,1,v,2,v,k,若,(,v

4、,i,v,i+1,),E(i=1,2,k-1),v=v,1,u=,v,k,則稱該序列是從頂點,v,到頂點,u,的路徑。若,v=u，,則稱該序列為回路。,在圖,G1,中，,V0,V1,V2,V3,是,V0,到,V3,的路徑。,V0,V1,V2,V3,V0,是回路。,V0,V4,V3,V1,V2,例：,例：有向圖,G2,V0,V1,V2,V3,在圖,G2,中，,V0,V2,V3,是,V0,到,V3,的路徑。,V0,V2,V3,V0,是回路。,有向圖,G=（V，E）,中的頂點序列,v,1,v,2,v,k,若,E (i=1,2,k-1),v=v,1,u=,v,k,則稱該序列是從頂點,v,到頂點,u,的

5、路徑。若,v=u，,則稱該序列為回路。,在一條路徑中,若除起點和終點外,所有頂點各不相同,則稱該路徑為簡單路徑。,由簡單路徑組成的回路稱為簡單回路。,在圖,G1,中，,V0,V1,V2,V3,是,簡單路徑。,V0,V1,V2,V4,V1,不是簡單路徑。,在圖,G2,中，,V0,V2,V3,V0,是簡單回路。,無向圖,G1,有向圖,G2,V0,V4,V3,V1,V2,V0,V1,V2,V3,5.簡單路徑和簡單回路,非連通圖,連通圖,強連通圖,非強連通圖,V0,V1,V2,V3,V0,V4,V3,V1,V2,V0,V1,V2,V3,V0,V2,V3,V1,V5,V4,6.連通圖（強連通圖）,在無（

6、有）向圖,G=(V,E),中，若對任何兩個頂點,v、u,都存在從,v,到,u,的路徑，則稱,G,是連通圖（強連通圖）。,(a),(b),(c),V0,V4,V3,V1,V2,V0,V4,V3,V1,V2,V0,V4,V3,V1,V2,8.子圖,設有兩個圖,G=（V，E）、G1=（V1，E1），,若,V1,V，E1,E，,則稱,G1,是,G,的子圖。例,:(,b)、(c),是,(,a),的子圖,7.權,某些圖的邊具有與它相關的數(shù),稱之為權。這種帶權圖叫做網(wǎng)絡。,9.連通分量（強連通分量）,V0,V2,V3,V1,V5,V4,無向圖,G,的極大連通子圖稱為,G,的連通分量。極大連通子圖意思是：該子

7、圖是,G,連通子圖，將,G,的任何不在該子圖中的頂點加入，子圖不再連通。,V0,V2,V3,V1,V5,V4,連通分量,非連通圖,有向圖,G,的極大強連通子圖稱為,G,的強連通分量。極大強連通子圖意思是：該子圖是,G,的強連通子圖，將,D,的任何不在該子圖中的頂點加入，子圖不再是強連通的。,強連通分量,V0,V1,V2,V3,V0,V2,V3,V1,10.權與網(wǎng),圖中邊或弧所具有的相關數(shù)稱為權。表明從一個頂點到另一個頂點的距離或耗費。,帶權的圖稱為,網(wǎng),。,極小連通子圖：該子圖是,G,的連通子圖，在該子圖中刪除任何一條邊，子圖不再連通,包含無向圖,G,所有頂點的極小連通子圖稱為,G,的生成樹,

8、對非連通圖，則稱由各個連通分量的生成樹的集合為非連通圖的生成森林。,連通圖,G1,G1,的生成樹,V0,V4,V3,V1,V2,V0,V4,V3,V1,V2,V0,V4,V3,V1,V2,11.生成樹和生成森林,例：,G1,2,4,1,3,7.2.1,數(shù)組表示法,鄰接矩陣：,表示頂點間相聯(lián)關系的矩陣。,定義：,設,G=(V,E),是有,n,1,個頂點的圖，,G,的鄰接矩陣,A,是具有以下性質的,n,階方陣,：,例：,1,5,3,2,4,G2,網(wǎng)的鄰接矩陣可定義為：,例：,1,4,5,2,3,7,5,3,1,8,6,4,2,鄰接矩陣類型定義,:,#,define INFINITY INT_MAX

9、,#define MAX_VERTEX_NUM 20,typedef,enumDG,DN,AG,AN,GraphKind,;,typedef,struct,ArcCell,VRType,adj,;,InfoType,*info;,ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM,typedef,struct,VertexType,vexsMAX_VERTEX_NUM,;,AdjMatrix,arcs;,int,vexnum,arcnum,;,GraphKind,kind;,MGraph,;,鄰接表的類型定義,#,define MAX_VERTEX_NU

10、M 20,typedef struct ArcNode,int adjvex;,struct ArcNode*nextarc;,InfoType*info;,ArcNode;,7.2.2,鄰接表,實現(xiàn)：為圖中每個頂點建立一個單鏈表，第,i,個單鏈表中的結點表示依附于頂點,V,i,的邊（有向圖中指以,V,i,為尾的?。?。,typedef struct VNode,VertexType data;,ArcNode*firstarc;,VNode,AdjListMAX_VERTEX_NUM;,typedef struct,AdjList vertices;,int vexnum,arcnum;,in

11、t kind;,ALGraph;,adjvex,nextarc,vexdata,firstarc,例：,G1,b,d,a,c,1,2,3,4,a,c,d,b,vexdata,firstarc,3,2,4,1,adjvex,nextarc,例：,a,e,c,b,d,G2,1,2,3,4,a,c,d,b,vexdata,firstarc,4,2,1,2,adjvex,nextarc,5,e,4,3,5,1,5,3,2,3,例：,G1,b,d,a,c,1,2,3,4,a,c,d,b,vexdata,firstarc,4,1,1,3,adjvex,nextarc,逆鄰接表：有向圖中對每個結點建立以,V

12、,i,為弧頭的弧的單鏈表。,7.3,圖的遍歷,7.3.1,深度優(yōu)先搜索,方法：從圖的某一頂點,V0,出發(fā)，訪問此頂點；然后依次從,V0,的未被訪問的鄰接點出發(fā)，深度優(yōu)先遍歷圖，直至圖中所有和,V0,相通的頂點都被訪問到；若此時圖中尚有頂點未被訪問，則另選圖中一個未被訪問的頂點作起點,重復上述過程，直至圖中所有頂點都被訪問為止,。,V1,V2,V4,V5,V3,V7,V6,V8,例：,深度遍歷：,V1,V2 V4 V8 V5 V3 V6 V7,深度優(yōu)先遍歷算法（遞歸算法）參見,P169。,V1,V2,V4,V5,V3,V7,V6,V8,深度優(yōu)先生成樹,V1,V2,V4,V5,V3,V7,V6,V

13、8,深度優(yōu)先遍歷算法（遞歸算法）,Boolean visitedMAX;,Status(*VisitFunc)(int v);,void DFSTraverse(Gragh G,Status(*Visit)(int v),VisitFunc=Visit;,for(v=0;vG.vexnum;+v)visitedv=FALSE;,for(v=0;v=0;w=NextAdjVex(G,v,w),if(!visitedw)DFS(G,W);,V1,V2,V4,V5,V3,V7,V6,V8,例：,1,2,3,4,1,3,4,2,vexdata,firstarc,2,7,8,3,adjvex,nexta

14、rc,5,5,6,4,1,5,1,2,8,2,6,7,8,6,7,8,7,3,6,3,5,4,深度遍歷：,V1,V3,V7,V6,V2,V5,V8,V4,7.3.2,廣度優(yōu)先搜索,方法：從圖的某一頂點,V0,出發(fā)，訪問此頂點后，依次訪問,V0,的各個未曾訪問過的鄰接點；然后分別從這些鄰接點出發(fā)，廣度優(yōu)先遍歷圖，直至圖中所有已被訪問的頂點的鄰接點都被訪問到；若此時圖中尚有頂點未被訪問，則另選圖中一個未被訪問的頂點作起點,，,重復上述過程，直至圖中所有頂點都被訪問為止。,廣度優(yōu)先遍歷算法,void BFSTraverse(Graph G,Status(*Visit)(int v),for(v=0;

15、vG.vexnum;+v)visitedv=FALSE;,InitQueue(Q);,for(v=0;v=0;w=NextAdjVex(G,u,w),Visitedw=TRUE;visit(w);,EnQueue(Q,w);,V1,V2,V4,V5,V3,V7,V6,V8,例,:,廣度遍歷：,V1,V2 V3 V4 V5 V6 V7 V8,V1,V2,V4,V5,V3,V7,V6,V8,廣度優(yōu)先生成樹,V1,V2,V4,V5,V3,V7,V6,V8,例,:,1,4,2,3,5,1,2,3,4,1,3,4,2,vexdata,firstarc,5,5,4,3,adjvex,nextarc,5,5

16、,1,5,1,1,4,3,2,2,廣度遍歷序列：,1 4 3 2 5,7.4,圖的連通性問題,問題提出：要在,n,個城市間建立通信聯(lián)絡網(wǎng)，用頂點表示城市；權表示城市間建立通信線路所需花費代價。希望找到一棵生成樹，它的每條邊上的權值之和（即建立該通信網(wǎng)所需花費的總代價）最小,最小,(,代價,),生成樹。,1,6,5,4,3,2,7,13,17,9,18,12,7,5,24,10,7.4.3,最小生成樹,算法思想：設,N=(V,E),是連通網(wǎng)，,TE,是,N,上最小生成樹中邊的集合。,1.,初始令,U=u0,(u0,V),TE=。,2.,在所有,uU,vV-U,的邊(,u,v)E,中，找一條代價最,小的邊(,u0,v0)。,3.,將(,u0,v0),并入集合,TE，,同時,v0,并入,U。,4.,重復上述操作直至,U=V,為止，則,T=(V,TE),為,N,的最,小生成樹。,方法一：普里姆,(,Prim),算法,構造最小生成樹的方法,例：,1,6,5,4,3,2,6,5,1,3,5,6,6,4,2,5,1,3,1,1,6,3,1,4,1,6,4,3,1,4,2,1,1,6,4,3,2,1,