數(shù)據(jù)結(jié)構(gòu)課件第七章

7.1抽象數(shù)據(jù)類型圖的定義,7.2圖的存儲表示,7.3圖的遍歷,7.4最小生成樹,7.5兩點之間的最短路徑問題,7.6拓?fù)渑判?7.7關(guān)鍵路徑,圖是由一個頂點集V和一個弧集R構(gòu)成的數(shù)據(jù)結(jié)構(gòu)。Graph=(V,R)其中，R|v,wV且P(v,w)表示從v到w的一條弧，并稱v為弧頭，w為弧尾。,圖的結(jié)構(gòu)定義:,V,W,由于“弧”是有方向的，因此稱由頂點集和弧集構(gòu)成的圖為有向圖。,ABECD,例如:,G1=(V1,VR1),其中V1=A,B,C,D,EVR1=,若VR必有VR,則稱(v,w)為頂點v和頂點w之間存在一條邊。,BCADFE,由頂點集和邊集構(gòu)成的圖稱作無向圖。,例如:G2=(V2,VR2)V2=A,B,C,D,E,FVR2=(A,B),(A,E),(B,E),(C,D),(D,F),(B,F),(C,F),名詞和術(shù)語,網(wǎng)、子圖,完全圖、稀疏圖、稠密圖,鄰接點、度、入度、出度,路徑、路徑長度、簡單路徑、簡單回路,連通圖、連通分量、強連通圖、強連通分量,生成樹、生成森林,A,B,E,C,F,A,E,A,B,B,C,設(shè)圖G=(V,VR)和圖G=(V,VR),且VV,VRVR,則稱G為G的子圖。,15,9,7,21,11,3,2,弧或邊帶權(quán)的圖分別稱作有向網(wǎng)或無向網(wǎng)。,假設(shè)圖中有n個頂點，e條邊，則,含有e=n(n-1)/2條邊的無向圖稱作完全圖；,含有e=n(n-1)條弧的有向圖稱作有向完全圖；,若邊或弧的個數(shù)enlogn，則稱作稀疏圖，否則稱作稠密圖。,假若頂點v和頂點w之間存在一條邊，則稱頂點v和w互為鄰接點，,A,C,D,F,E,例如:,ID(B)=3,ID(A)=2,邊(v,w)和頂點v和w相關(guān)聯(lián)。和頂點v關(guān)聯(lián)的邊的數(shù)目定義為頂點v的度。,B,頂點的出度:以頂點v為弧尾的弧的數(shù)目；,A,B,E,C,F,對有向圖來說，,頂點的入度:以頂點v為弧頭的弧的數(shù)目。,頂點的度(TD)=出度(OD)+入度(ID),例如:,ID(B)=2,OD(B)=1,TD(B)=3,設(shè)圖G=(V,VR)中的一個頂點序列u=vi,0,vi,1,vi,m=w中，(vi,j-1,vi,j)VR1jm,則稱從頂點u到頂點w之間存在一條路徑。路徑上邊的數(shù)目稱作路徑長度。,A,B,E,C,F,如:長度為3的路徑A,B,C,F,簡單路徑:序列中頂點不重復(fù)出現(xiàn)的路徑。,簡單回路:序列中第一個頂點和最后一個頂點相同的路徑。,若圖G中任意兩個頂點之間都有路徑相通，則稱此圖為連通圖；,若無向圖為非連通圖，則圖中各個極大連通子圖稱作此圖的連通分量。,B,A,C,D,F,E,B,A,C,D,F,E,若任意兩個頂點之間都存在一條有向路徑，則稱此有向圖為強連通圖。,A,B,E,C,F,A,B,E,C,F,對有向圖，,否則，其各個強連通子圖稱作它的強連通分量。,假設(shè)一個連通圖有n個頂點和e條邊，其中n-1條邊和n個頂點構(gòu)成一個極小連通子圖，稱該極小連通子圖為此連通圖的生成樹。,對非連通圖，則稱由各個連通分量的生成樹的集合為此非連通圖的生成森林。,B,A,C,D,F,E,結(jié)構(gòu)的建立和銷毀,插入或刪除頂點,對鄰接點的操作,對頂點的訪問操作,遍歷,插入和刪除弧,基本操作,CreatGraph(/若G中存在頂點u，則返回該頂點在/圖中“位置”；否則返回其它信息。,GetVex(G,v);/返回v的值。,PutVex(/對v賦值value。,對鄰接點的操作,FirstAdjVex(G,v);/返回v的“第一個鄰接點”。若該頂點/在G中沒有鄰接點，則返回“空”。,NextAdjVex(G,v,w);/返回v的（相對于w的）“下一個鄰接/點”。若w是v的最后一個鄰接點，則/返回“空”。,插入或刪除頂點,InsertVex(/在圖G中增添新頂點v。,DeleteVex(/刪除G中頂點v及其相關(guān)的弧。,插入和刪除弧,InsertArc(/在G中增添弧，若G是無向的，/則還增添對稱弧。,DeleteArc(/在G中刪除弧，若G是無向的，/則還刪除對稱弧。,遍歷,DFSTraverse(G,v,Visit();/從頂點v起深度優(yōu)先遍歷圖G，并對每/個頂點調(diào)用函數(shù)Visit一次且僅一次。,BFSTraverse(G,v,Visit();/從頂點v起廣度優(yōu)先遍歷圖G，并對每/個頂點調(diào)用函數(shù)Visit一次且僅一次。,7.2圖的存儲表示,一、圖的數(shù)組(鄰接矩陣)存儲表示,二、圖的鄰接表存儲表示,三、有向圖的十字鏈表存儲表示,四、無向圖的鄰接多重表存儲表示,Aij=,0(i,j)VR,1(i,j)VR,一、圖的數(shù)組(鄰接矩陣)存儲表示,B,A,C,D,F,E,定義:矩陣的元素為,無向圖的鄰接矩陣為對稱矩陣,ABCDEF,ABCDEF,有向圖的鄰接矩陣為非對稱矩陣,A,B,D,C,E,ABCDE,ABCDE,鄰接矩陣表示法特點：,1）無向圖鄰接矩陣是對稱矩陣，同一條邊表示了兩次；2）頂點v的度：在無向圖中等于二維數(shù)組對應(yīng)行（或列）中1的個數(shù)；在有向圖中,統(tǒng)計第i行1的個數(shù)可得頂點i的出度，統(tǒng)計第j列1的個數(shù)可得頂點j的入度。3）判斷兩頂點v、u是否為鄰接點：只需判二維數(shù)組對應(yīng)分量是否為1；4）頂點不變，在圖中增加、刪除邊：只需對二維數(shù)組對應(yīng)分量賦值1或清0；5）設(shè)存儲頂點的一維數(shù)組大小為n(圖的頂點數(shù)n),G占用存儲空間：n+n2；G占用存儲空間只與它的頂點數(shù)有關(guān)，與邊數(shù)無關(guān)；適用于邊稠密的圖；,typedefstructArcCell/弧的定義VRTypeadj;/VRType是頂點關(guān)系類型/對無權(quán)圖，用1或0表示相鄰否；/對帶權(quán)圖，則為權(quán)值類型。InfoType*info;/該弧相關(guān)信息的指針ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;,typedefstruct/圖的定義VertexType/頂點信息vexsMAX_VERTEX_NUM;AdjMatrixarcs;/弧的信息intvexnum,arcnum;/頂點數(shù)，弧數(shù)GraphKindkind;/圖的種類標(biāo)志MGraph;,網(wǎng)絡(luò)的鄰接矩陣,A,B,D,C,E,15,9,7,21,11,3,2,0A141B0452C353D254E015F123,B,A,C,D,F,E,二、圖的鄰接表存儲表示,同一個頂點發(fā)出的邊鏈接在同一個邊鏈表中，每一個鏈結(jié)點代表一條邊(邊結(jié)點),結(jié)點中有另一頂點的下標(biāo)adjvex和指針nextedge。,14,2,3,01,2,01234,ABCDE,有向圖的鄰接表,A,B,E,C,D,可見，在有向圖的鄰接表中不易找到指向該頂點的弧。,A,B,E,C,D,有向圖的逆鄰接表,ABCDE,3,0,3,4,2,0,01234,在有向圖的鄰接表中，對每個頂點，鏈接的是指向該頂點的弧。,鄰接表表示法特點：,1）無向圖鄰接表邊結(jié)點數(shù)是邊數(shù)的兩倍.2）頂點vi的度：在無向圖中等于第i個鏈表中的結(jié)點數(shù)；在有向圖鄰接表中,第i行的結(jié)點數(shù)等于頂點i的出度，在有向圖逆鄰接表中,第i行的結(jié)點數(shù)等于頂點i的入度。3）在鄰接表上容易找到任一頂點的第一個鄰接點和下一個鄰接點4）設(shè)存儲頂點的一維數(shù)組大小為n(圖的頂點數(shù)n),G占用存儲空間：n+e；G占用存儲空間與它的頂點數(shù)和邊數(shù)有關(guān)；適用于邊稀疏的圖；,typedefstructArcNodeintadjvex;/該弧所指向的頂點的位置structArcNode*nextarc;/指向下一條弧的指針I(yè)nfoType*info;/該弧相關(guān)信息的指針ArcNode;,adjvexnextarcinfo,弧的結(jié)點結(jié)構(gòu),typedefstructVNodeVertexTypedata;/頂點信息ArcNode*firstarc;/指向第一條依附該頂點的弧VNode,AdjListMAX_VERTEX_NUM;,datafirstarc,頂點的結(jié)點結(jié)構(gòu),typedefstructAdjListvertices;intvexnum,arcnum;intkind;/圖的種類標(biāo)志ALGraph;,圖的結(jié)構(gòu)定義,三、有向圖的十字鏈表存儲表示,弧的結(jié)點結(jié)構(gòu),弧尾頂點位置弧頭頂點位置弧的相關(guān)信息,指向下一個有相同弧尾的結(jié)點,指向下一個有相同弧頭的結(jié)點,typedefstructArcBox/弧的結(jié)構(gòu)表示inttailvex,headvex;InfoType*info;structArcBox*hlink,*tlink;VexNode;,頂點的結(jié)點結(jié)構(gòu),頂點信息數(shù)據(jù),指向該頂點的第一條入弧,指向該頂點的第一條出弧,typedefstructVexNode/頂點的結(jié)構(gòu)表示VertexTypedata;ArcBox*firstin,*firstout;VexNode;,typedefstructVexNodexlistMAX_VERTEX_NUM;/頂點結(jié)點(表頭向量)intvexnum,arcnum;/有向圖的當(dāng)前頂點數(shù)和弧數(shù)OLGraph;,有向圖的結(jié)構(gòu)表示(十字鏈表),A,B,C,D,0,1,2,3,四、無向圖的鄰接多重表存儲表示,typedefstructEboxVisitIfmark;/訪問標(biāo)記intivex,jvex;/該邊依附的兩個頂點的位置structEBox*ilink,*jlink;InfoType*info;/該邊信息指針EBox;,邊的結(jié)構(gòu)表示,typedefstruct/鄰接多重表VexBoxadjmulistMAX_VERTEX_NUM;intvexnum,edgenum;AMLGraph;,頂點的結(jié)構(gòu)表示,typedefstructVexBoxVertexTypedata;EBox*firstedge;/指向第一條依附該頂點的邊VexBox;,無向圖的結(jié)構(gòu)表示,01234,A,B,C,D,E,7.3圖的遍歷,從圖中某個頂點出發(fā)游歷圖，訪遍圖中其余頂點，并且使圖中的每個頂點僅被訪問一次的過程。,深度優(yōu)先搜索,廣度優(yōu)先搜索,遍歷應(yīng)用舉例,從圖中某個頂點V0出發(fā)，訪問此頂點，然后依次從V0的各個未被訪問的鄰接點出發(fā)深度優(yōu)先搜索遍歷圖，直至圖中所有和V0有路徑相通的頂點都被訪問到。,一、深度優(yōu)先搜索遍歷圖,連通圖的深度優(yōu)先搜索遍歷,V,w1,SG1,SG2,SG3,W1、W2和W3均為V的鄰接點，SG1、SG2和SG3分別為含頂點W1、W2和W3的子圖。,訪問頂點V：for(W1、W2、W3)若該鄰接點W未被訪問，則從它出發(fā)進行深度優(yōu)先搜索遍歷。,w2,w3,w2,從上頁的圖解可見:,1.從深度優(yōu)先搜索遍歷連通圖的過程類似于樹的先根遍歷；,解決的辦法是：為每個頂點設(shè)立一個“訪問標(biāo)志visitedw”。,2.如何判別V的鄰接點是否被訪問？,a,c,b,d,e,g,f,FFFFFFF,T,T,T,T,T,T,T,a,c,b,d,g,f,e,a,c,b,g,f,e,d,訪問標(biāo)志:,訪問次序:,例如:,0123456,0,2,3,4,5,1,6,voidDFS(GraphG,intv)/從頂點v出發(fā)，深度優(yōu)先搜索遍歷連通圖Gvisitedv=TRUE;VisitFunc(v);for(w=FirstAdjVex(G,v);w!=0;w=NextAdjVex(G,v,w)if(!visitedw)DFS(G,w);/對v的尚未訪問的鄰接頂點w/遞歸調(diào)用DFS/DFS,首先將圖中每個頂點的訪問標(biāo)志設(shè)為FALSE,之后搜索圖中每個頂點，如果未被訪問，則以該頂點為起始點，進行深度優(yōu)先搜索遍歷，否則繼續(xù)檢查下一頂點。,非連通圖的深度優(yōu)先搜索遍歷,a,b,c,h,d,e,k,f,g,FFFFFFFFF,T,T,T,T,T,T,T,T,T,a,c,h,d,k,f,e,b,g,a,c,h,k,f,e,d,b,g,訪問標(biāo)志:,訪問次序:,例如:,012345678,0,2,1,3,4,5,6,7,8,voidDFSTraverse(GraphG,Status(*Visit)(intv)/對圖G作深度優(yōu)先遍歷。VisitFunc=Visit;for(v=0;vw2,V-w8的路徑長度為1；,V-w7,V-w3,V-w5的路徑長度為2；,V-w6,V-w4的路徑長度為3。,w1,V,w2,w7,w6,w3,w8,w5,w4,從圖中的某個頂點V0出發(fā)，并在訪問此頂點之后依次訪問V0的所有未被訪問過的鄰接點，之后分別從這些鄰接點出發(fā)依次訪問它們的鄰接點，并使“先被訪問的頂點的鄰接點”先于“后被訪問的頂點的鄰接點”被訪問，直至圖中所有和V0有路徑相通的頂點都被訪問到。,若此時圖中尚有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作起始點，重復(fù)上述過程，直至圖中所有頂點都被訪問到為止。,V,w1,w8,w3,w7,w6,w2,w5,w4,w1,V,w2,w7,w6,w3,w8,w5,w4,FFFFFFFFF,T,T,T,T,T,T,T,T,T,012345678,Visited,Q,V,訪問次序:,w1,w2,w8,w4,w7,w3,w5,w6,voidBFSTraverse(GraphG,Status(*Visit)(intv)for(v=0;vG.vexnum;+v)visitedv=FALSE;/初始化訪問標(biāo)志InitQueue(Q);/置空的輔助隊列Qfor(v=0;vG.vexnum;+v)if(!visitedv)/v尚未訪問/BFSTraverse,visitedu=TRUE;Visit(u);/訪問uEnQueue(Q,v);/v入隊列while(!QueueEmpty(Q)DeQueue(Q,u);/隊頭元素出隊并置為ufor(w=FirstAdjVex(G,u);w!=0;w=NextAdjVex(G,u,w)if(!visitedw)visitedw=TRUE;Visit(w);EnQueue(Q,w);/訪問的頂點w入隊列/if/while,連通分量(Connectedcomponent)當(dāng)無向圖為非連通圖時,從圖中某一頂點出發(fā),利用深度優(yōu)先搜索算法或廣度優(yōu)先搜索算法不可能遍歷到圖中的所有頂點,只能訪問到該頂點所在的最大連通子圖(連通分量)的所有頂點。,圖的連通性問題,L,E,D,H,G,A,B,F,I,C,J,K,M,若從無向圖的每一個連通分量中的一個頂點出發(fā)進行遍歷,可求得無向圖的所有連通分量。求連通分量的算法需要對圖的每一個頂點進行檢測：若已被訪問過，則該頂點一定是落在圖中已求得的連通分量上；若還未被訪問，則從該頂點出發(fā)遍歷圖，可求得圖的另一個連通分量。對于非連通的無向圖，所有連通分量的生成樹組成了非連通圖的生成森林。,非連通無向圖,DFS訪問序列:ALMJBFCDEGKHI,H,G,I,K,L,A,B,F,C,J,M,E,D,7.4(連通網(wǎng)的)最小生成樹,假設(shè)要在n個城市之間建立通訊聯(lián)絡(luò)網(wǎng)，則連通n個城市只需要修建n-1條線路，如何在最節(jié)省經(jīng)費的前提下建立這個通訊網(wǎng)？,問題：,構(gòu)造網(wǎng)的一棵最小生成樹，即：在e條帶權(quán)的邊中選取n-1條邊（不構(gòu)成回路），使“權(quán)值之和”為最小。,算法二：（克魯斯卡爾算法）,該問題等價于：,算法一：（普里姆算法）,假設(shè)N=V,E)是連通網(wǎng)，TE是N上最小生成樹邊的集合。算法從Uu0(u0V)，TE=開始，重復(fù)執(zhí)行下述操作：在所有uV，vV-U的邊(u,v)E中找一條代價最小的邊（u0，v0）并入集合TE,同時v0并入U，直至U=V為止。此時TE中必有n-1條邊，則T=(V,TE)為N的最小生成樹。,普里姆算法的基本思想:,在生成樹的構(gòu)造過程中，圖中n個頂點分屬兩個集合：已落在生成樹上的頂點集U和尚未落在生成樹上的頂點集V-U，則應(yīng)在所有連通U中頂點和V-U中頂點的邊中選取權(quán)值最小的邊。,一般情況下所添加的頂點應(yīng)滿足下列條件:,a,b,c,d,e,g,f,例如:,19,5,14,18,27,16,8,21,3,a,e,12,d,c,b,g,f,7,14,8,5,3,16,21,所得生成樹權(quán)值和,=14+8+3+5+16+21=67,設(shè)置一個輔助數(shù)組，對每個頂點，記錄從頂點集U到VU具有代價最小的邊：,structVertexTypeadjvex;/U集中的頂點VRTypelowcost;/邊的權(quán)值closedgeMAX_VERTEX_NUM;,adjvexlowcost,a,b,c,d,e,g,f,19,5,14,18,27,16,8,21,3,a,e,12,d,c,b,7,a,a,a,19,14,18,14,e,12,e,e,8,16,8,d,3,d,d,7,21,3,c,5,5,0,1,2,3,4,5,6,U:,V-U:,a,b,c,d,e,f,g,f,g,16,21,abcdefg,abcdefg,voidMiniSpanTree_P(MGraphG,VertexTypeu)/用普里姆算法從頂點u出發(fā)構(gòu)造網(wǎng)G的最小生成樹k=LocateVex(G,u);for(j=0;jG.vexnum;+j)/輔助數(shù)組初始化if(j!=k)closedgej=u,G.arcskj.adj;closedgek.lowcost=0;/初始，Uufor(i=0;iG.vexnum;+i),繼續(xù)向生成樹上添加頂點;,k=minimum(closedge);/求出加入生成樹的下一個頂點(k)printf(closedgek.adjvex,G.vexsk);/輸出生成樹上一條邊closedgek.lowcost=0;/第k頂點并入U集for(j=0;jG.vexnum;+j)/修改其它頂點的最小邊if(G.arcskj.adjclosedgej.lowcost)closedgej=G.vexsk,G.arcskj.adj;,具體做法:先構(gòu)造一個只含n個頂點的子圖SG，然后從權(quán)值最小的邊開始，若它的添加不使SG中產(chǎn)生回路，則在SG上加上這條邊，如此重復(fù)，直至加上n-1條邊為止。,考慮問題的出發(fā)點:為使生成樹上邊的權(quán)值之和達到最小，則應(yīng)使生成樹中每一條邊的權(quán)值盡可能地小。,克魯斯卡爾算法的基本思想：,a,b,c,d,e,g,f,19,5,14,18,27,16,8,21,3,a,e,12,d,c,b,g,f,7,14,8,5,3,16,21,例如:,7,12,18,19,算法描述:,構(gòu)造非連通圖ST=(V,);k=i=0;/k計選中的邊數(shù)while(kadjvex;if(!(-indegreek)push(s,k);,if(countvextarc)k=p-adjvex;dut=*(p-info);if(vlk-dutnextarc)k=p-adjvex;dut=*(p-info);ee=vej;el=vlk-dut;tag=(ee=el)?*:printf(j,k,dut,ee,el,tag);,7.6兩點之間的最短路徑問題,求從某個源點到其余各點的最短路徑,每一對頂點之間的最短路徑,求從源點到其余各點的最短路徑的算法的基本思想:,依最短路徑的長度遞增的次序求得各條路徑,源點,v1,其中，從源點到頂點v的最短路徑是所有最短路徑中長度最短者。,v2,這條路徑必定是直接從源點到該點v1只含一條弧，并且這條弧的權(quán)