圖的定義和術(shù)語

《圖的定義和術(shù)語》由會(huì)員分享，可在線閱讀，更多相關(guān)《圖的定義和術(shù)語（47頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、單擊此處編輯母版標(biāo)題樣式,*,*,單擊此處編輯母版文本樣式,第二級(jí),第三級(jí),第四級(jí),第五級(jí),第七章 圖,7.1,圖的定義和術(shù)語,7.2,圖的存儲(chǔ)結(jié)構(gòu),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)圖及其應(yīng)用,7.5.1,拓?fù)渑判?7.6,最短路徑,7.6.1,從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑,7.6.2,每一對(duì)頂點(diǎn)之間的最短路徑,7.1,圖的,定義和術(shù)語,圖的定義：,是一種多對(duì)多的結(jié)構(gòu)關(guān)系，每個(gè)元素可以有零個(gè)或多個(gè)直接前趨；零個(gè)或多個(gè)直接后繼。圖是由頂點(diǎn)集合,(,

2、vertex),及頂點(diǎn)間的關(guān)系集合組成的一種數(shù)據(jù)結(jié)構(gòu)：,Graph(V,R),其中,V=v|v,某個(gè)數(shù)據(jù)對(duì)象,是頂點(diǎn)的有窮非空集合；,R=VR=(v,w)|v,w,V,基本術(shù)語：,1.有向圖與無向圖,在有向圖中，頂點(diǎn)對(duì),是有序的。在無向圖中，頂點(diǎn)對(duì),(,x,y),是無序的。有向邊又可稱為,弧,中,vi,稱為,弧尾,或初始點(diǎn)，,vj,稱為,弧頭,或終端點(diǎn)。,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.鄰接點(diǎn)及關(guān)聯(lián),若無向圖中存在邊,(,v,u)，,則稱頂點(diǎn),v,和,u,互為鄰接點(diǎn)；邊,(,v,u),依附于頂點(diǎn),v,和,u；,或者說邊,(,v,u),和頂點(diǎn),v,和,u,相關(guān)聯(lián)。,3.,頂點(diǎn)的度、入度、出度,在無向圖中：頂點(diǎn),V,的度,=,與,V,相關(guān)聯(lián)的邊的數(shù)目,在有向圖中：,頂點(diǎn),V,的出度,=,以,V,為狐尾的有向邊數(shù),頂點(diǎn),V,的入度,=,以,V,為狐頭的有向邊數(shù),頂點(diǎn),V,的度,=,V,的出度,+,V,的入度,V0,V4,V3,V1,V2,V0,V1,V2,V3,4.路徑、回路,無向圖,G=（V，E）,中的頂點(diǎn)序列,v,1,v,2,v,k,若,(,v

4、,i,v,i+1,),E(i=1,2,k-1),v=v,1,u=,v,k,則稱該序列是從頂點(diǎn),v,到頂點(diǎn),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）,中的頂點(diǎn)序列,v,1,v,2,v,k,若,E (i=1,2,k-1),v=v,1,u=,v,k,則稱該序列是從頂點(diǎn),v,到頂點(diǎn),u,的

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

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

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

8、對(duì)非連通圖，則稱由各個(gè)連通分量的生成樹的集合為非連通圖的生成森林。,連通圖,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ù)組表示法,鄰接矩陣：,表示頂點(diǎn)間相聯(lián)關(guān)系的矩陣。,定義：,設(shè),G=(V,E),是有,n,1,個(gè)頂點(diǎn)的圖，,G,的鄰接矩陣,A,是具有以下性質(zhì)的,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,鄰接表,實(shí)現(xiàn)：為圖中每個(gè)頂點(diǎn)建立一個(gè)單鏈表，第,i,個(gè)單鏈表中的結(jié)點(diǎn)表示依附于頂點(diǎn),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,逆鄰接表：有向圖中對(duì)每個(gè)結(jié)點(diǎn)建立以,V

12、,i,為弧頭的弧的單鏈表。,7.3,圖的遍歷,7.3.1,深度優(yōu)先搜索,方法：從圖的某一頂點(diǎn),V0,出發(fā)，訪問此頂點(diǎn)；然后依次從,V0,的未被訪問的鄰接點(diǎn)出發(fā)，深度優(yōu)先遍歷圖，直至圖中所有和,V0,相通的頂點(diǎn)都被訪問到；若此時(shí)圖中尚有頂點(diǎn)未被訪問，則另選圖中一個(gè)未被訪問的頂點(diǎn)作起點(diǎn),重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問為止,。,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)先搜索,方法：從圖的某一頂點(diǎn),V0,出發(fā)，訪問此頂點(diǎn)后，依次訪問,V0,的各個(gè)未曾訪問過的鄰接點(diǎn)；然后分別從這些鄰接點(diǎn)出發(fā)，廣度優(yōu)先遍歷圖，直至圖中所有已被訪問的頂點(diǎn)的鄰接點(diǎn)都被訪問到；若此時(shí)圖中尚有頂點(diǎn)未被訪問，則另選圖中一個(gè)未被訪問的頂點(diǎn)作起點(diǎn),，,重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問為止。,廣度優(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,個(gè)城市間建立通信聯(lián)絡(luò)網(wǎng)，用頂點(diǎn)表示城市；權(quán)表示城市間建立通信線路所需花費(fèi)代價(jià)。希望找到一棵生成樹，它的每條邊上的權(quán)值之和（即建立該通信網(wǎng)所需花費(fèi)的總代價(jià)）最小,最小,(,代價(jià),),生成樹。,1,6,5,4,3,2,7,13,17,9,18,12,7,5,24,10,7.4.3,最小生成樹,算法思想：設(shè),N=(V,E),是連通網(wǎng)，,TE,是,N,上最小生成樹中邊的集合。,1.,初始令,U=u0,(u0,V),TE=。,2.,在所有,uU,vV-U,的邊(,u,v)E,中，找一條代價(jià)最,小的邊(,u0,v0)。,3.,將(,u0,v0),并入集合,TE，,同時(shí),v0,并入,U。,4.,重復(fù)上述操作直至,U=V,為止，則,T=(V,TE),為,N,的最,小生成樹。,方法一：普里姆,(,Prim),算法,構(gòu)造最小生成樹的方法,例：,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,