第七章圖（Graphs)課件

第七章圖（Graphs),圖的基本概念圖的存儲表示圖的遍歷最小生成樹活動網(wǎng)絡(luò)最短路徑,圖例,結(jié)點,邊:(v2,v5),圖的構(gòu)成：結(jié)點集：V=v1,v2,v3,v4,v5,邊集：E=(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5),圖例,有向邊V3：始點，v4:終點,圖的構(gòu)成：結(jié)點集：V=v1,v2,v3,v4,有向邊集：E=,圖的概念,圖是由頂點(vertex)集合及頂點間的關(guān)系集合組成的一種數(shù)據(jù)結(jié)構(gòu)：Graph(V,E)其中V=x|x某個數(shù)據(jù)對象是頂點的有窮非空集合；E=|x,yV是頂點之間關(guān)系的有窮集合，也叫做邊(edge)的集合。,有向圖G1V1=v1,v2,v3,v4,E1=,無向圖G2V2=v1,v2,v3,v4,v5,E2=,或者E2=(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5),(a)G1=(V1,E1),(b)G2=(V2,E2),圖的術(shù)語,v3鄰接到v4,v4的入度ID(v4)=1,v1的出度OD(v4)=1,性質(zhì):入度之和=出度之和=邊數(shù),結(jié)點的度數(shù):TD(v)=ID(v)+OD(v),v1和v4互為鄰接點,v4的度數(shù)為2TD(v4)=2,度數(shù)之和=邊數(shù)的二倍（因為每個邊“貢獻(xiàn)”了兩個度數(shù)）,子圖設(shè)有兩個圖G(V,E)和G(V,E)。若VV且EE,則稱圖G是圖G的子圖。權(quán)某些圖的邊具有與它相關(guān)的數(shù),稱之為權(quán)。這種帶權(quán)圖叫做網(wǎng)絡(luò)。完全圖若有n個頂點的無向圖有n(n-1)/2條邊,則此圖為完全無向圖。有n個頂點的有向圖有n(n-1)條邊,則此圖為完全有向圖。,路徑:(1),(簡單路徑)(2),(環(huán))(3),路徑:在圖G(V,E)中,若存在邊的序列(vi,vp1)、(vp1,vp2)、.、(vpm,vj)則稱頂點序列(vivp1vp2.vpmvj)為從頂點vi到頂點vj的路徑。,路徑長度非帶權(quán)圖的路徑長度是指此路徑上邊的條數(shù)。帶權(quán)圖的路徑長度是指路徑上各邊的權(quán)之和,簡單路徑若路徑上各頂點v1,v2,.,vm均不互相重復(fù),則稱這樣的路徑為簡單路徑。回路若路徑上第一個頂點v1與最后一個頂點vm重合,則稱這樣的路徑為回路或環(huán)。,連通圖與連通分量在無向圖中,若從頂點v1到頂點v2有路徑,則稱頂點v1與v2是連通的。如果圖中任意一對頂點都是連通的,則稱此圖是連通圖。非連通圖的極大連通子圖叫做連通分量。,強(qiáng)連通圖在有向圖中,若對于每一對頂點vi和vj,都存在一條從vi到vj和從vj到vi的路徑,則稱此圖是強(qiáng)連通圖。,生成樹一個連通圖的生成樹是它的極小連通子圖，在n個頂點的情形下，有n-1條邊。,圖的存儲結(jié)構(gòu),鄰接矩陣,存儲原則:存儲結(jié)點集和邊集的信息.,（1）存儲結(jié)點集；（2）存儲邊集：存儲每兩個結(jié)點是否有關(guān)系。,圖的存儲結(jié)構(gòu),有向圖的鄰接矩陣,帶權(quán)圖的鄰接矩陣,鄰接矩陣表示法,在圖的鄰接矩陣表示中:有一個記錄各個頂點信息的頂點表，還有一個表示各個頂點之間關(guān)系的鄰接矩陣。,#defineMAX_VERTEX_NUM20/最大頂點個數(shù)typedefstructVertexTypevexsMAX_VERTEX_NUM；/頂點向量intarcsMAX_VERTEX_NUMMAX_VERTEX_NUM；/鄰接矩陣intvexnum，arcnum；/圖的當(dāng)前頂點數(shù)和弧數(shù)MGraph;,容易計算結(jié)點的度數(shù);容易判定兩個結(jié)點間是否有邊相連;容易判定結(jié)點之間是否有路徑相連(計算Am);對于有向圖，需要n個單元存儲結(jié)點數(shù)據(jù)，n*n個單元存儲鄰接矩陣；無向圖的鄰接矩陣是對稱的,可以壓縮存儲;存儲量與結(jié)點數(shù)有關(guān),與邊數(shù)無關(guān);若邊數(shù)n2,則鄰接矩陣是稀疏矩陣;,鄰接表,每個結(jié)點拉出一個鄰接邊鏈表(以此結(jié)點為始點的所有鄰接點),所有結(jié)點存儲與一個表中,以A為始點的邊鏈,以A為終點的邊鏈,鄰接表,圖的鄰接表存儲表示,#defineMAX_VERTEX_NUM20typedefstructArcNode/單鏈表結(jié)點結(jié)構(gòu)intadjvex；/該弧所指向的頂點的位置structArcNode*nextarc；/指向下一條弧的指針I(yè)nfoType*info；/該弧相關(guān)信息的指針ArcNode；typedefstructVNode/頂點結(jié)構(gòu)VertexTypedata；/頂點信息ArcNode*firstarc;/指向第一條依附該頂點的弧的指針VNode，AdjListMAX_VERTEX_NUM,Typedefstruct/鄰接表結(jié)構(gòu)AdjListvertices；intvexnum，arcnum；/圖的當(dāng)前頂點數(shù)和弧數(shù)ALGraph；,頂點vi的度恰為第i個鏈表中的結(jié)點數(shù)；在有向圖中，第i個鏈表(出邊表)中的結(jié)點個數(shù)是頂點的出度;,鄰接表的特點,求入度必須遍歷整個鄰接表:在所有鏈表中其鄰接點域的值為i的結(jié)點的個數(shù)是頂點vi的入度。為了求入度的便利,可以建立逆鄰接表,即鏈表為入邊表;,設(shè)圖中有n個頂點，e條邊，則用鄰接表表示無向圖時，需要n個頂點結(jié)點，2e個邊結(jié)點；用鄰接表表示有向圖時，若不考慮逆鄰接表，只需n個頂點結(jié)點，e個邊結(jié)點。,鄰接表,(B,D)邊出現(xiàn)在D的邊鏈表中,(B,D)邊出現(xiàn)在B的邊鏈表中,如果以邊為處理對象,如刪除一個邊,則需掃描每個結(jié)點的邊表,找到同一條邊.,鄰接多重表,將鄰接表中代表同一個邊的結(jié)點合并;邊表合并為多重表;在鄰接多重表中，每一條邊只有一個邊結(jié)點,為有關(guān)邊的處理提供了方便。,邊結(jié)點結(jié)構(gòu)：,mark:記錄是否處理過的標(biāo)記;ivex,jvex:該邊的兩頂點位置;ilink:指向下一條依附于頂點ivex的邊；jlink:指向下一條依附于頂點jvex的邊。,markivexjverxilinkjlink,typedefemnuunvisited，visitedVisited；typedefstructEBoxVisitedmark；/訪問標(biāo)記intivex，jvex；/該邊依附的兩個頂點的位置structEBox*ilink，*jlink；/分別指向依附這兩個頂點的下一條邊InfoType*info；/該邊信息指針EBox；,markivexjverxilinkjlink,data:存放與該頂點相關(guān)的信息，firstedge:指示第一條依附于該頂點的邊的指針,頂點結(jié)點的結(jié)構(gòu)：,datafirstedge,typedefstructVexBoxVertexTypedata；EBox*firstedge/指向第一條依附該頂點的邊VexBox；,typedefstructVexBoxadjmulistMAX_VERTEX_NUM；intvexnum，edgenum；/無向圖的當(dāng)前頂點數(shù)和邊數(shù)AMLGraph;,圖的抽象數(shù)據(jù)類型,ADTGraph數(shù)據(jù)對象V：V是具有相同特性的數(shù)據(jù)元素的頂點集。數(shù)據(jù)關(guān)系R：R=VRVR=|v，wV且P(v，w)，謂詞P(v，w)定義了弧的意義或信息,基本操作P：CreateGraph(/使用全局變量VisitFunc，使DFS不必設(shè)函數(shù)指針參數(shù)for(v=0；v=0;w=NextAdjVex(G,v,w)if(!visitedw)DFS(G，w)；/對v的尚未訪問的鄰接頂點w遞歸調(diào)用DFS,每個結(jié)點最多調(diào)用一次,每個結(jié)點一次,循環(huán)工作量：尋找結(jié)點v的鄰接點,時間復(fù)雜度：訪問每個結(jié)點的時間：O(n);尋找每個結(jié)點的所有鄰接結(jié)點工作量;設(shè)圖中有n個頂點，e條邊。如果用鄰接表表示圖，沿Firstedgelink鏈可以找到某個頂點v的所有鄰接頂點w。無向圖有2e個邊結(jié)點，有向圖有e個邊，所以掃描邊的時間為O(e);時間復(fù)雜度為O(n)+O(e)=O(n+e);如果用鄰接矩陣表示圖，則查找每一個頂點的所有的邊，所需時間為O(n)，則遍歷圖中所有的頂點所需的時間為O(n)+O(n2)=O(n2).,廣度優(yōu)先遍歷,基本思想訪問v1;訪問v1的鄰接點w1,w2,wm;依次訪問w1,w2,的未被訪問的鄰接點，如此進(jìn)行下去，直至訪問完所有結(jié)點。,算法的實現(xiàn)需要設(shè)置一個數(shù)組visited標(biāo)記結(jié)點是否訪問過；設(shè)置一個隊列紀(jì)錄當(dāng)前層訪問的結(jié)點以備訪問下一層結(jié)點。,取一個結(jié)點未訪問結(jié)點v,訪問v，標(biāo)記，入隊；（訪問v的所有鄰接點）：取隊頭元素，每次取v的下一個未訪問的鄰接點訪問，標(biāo)記并入隊；重復(fù)2,直至隊列空；如果圖中仍然有未訪問的結(jié)點，重復(fù)1，直至所有結(jié)點均已標(biāo)記為訪問過。,基本思想訪問v1;訪問v1的鄰接點w1,w2,wm;依次訪問w1,w2,的未被訪問的鄰接點，如此進(jìn)行下去，直至訪問完所有結(jié)點。,voidBFSTraverse(GraphG，Status(*Visit)(intv)/按廣度優(yōu)先非遞歸遍歷圖G。/使用輔助隊列Q和訪問標(biāo)志數(shù)組visited。for(v=0；vG.vexnum；+v)visitedv=FALSE；InitQueue(Q)；/置空的輔助隊列Q,for(v=0；vG.vexnum；+v)if(!visitedv)/v尚未訪問visitedv=TRUE；visit(v)；EnQueue(Q，v)；/v入隊列while(!QueueEmpty(Q)DeQueue(Q，u)/隊頭元素出隊并置為ufor(w=FirstAdjVex(G,u);w;w=NextAdjVex(G,u,w)if(!Visitedw)/w為u的尚未訪問的鄰接頂點visitedw=TRUE;Visit(w);EnQueue(Q,w);/if/while/if/BFSTraverse,復(fù)雜度與深度優(yōu)先相同,圖的連通性,對于連通的無向圖，從一個結(jié)點出發(fā)可以訪問所有結(jié)點；結(jié)點與遍歷時通過的邊構(gòu)成圖的生成樹；,深度優(yōu)先生成樹,廣度優(yōu)先生成樹,對于不連通的無向圖，則需從多個頂點出發(fā)訪問；結(jié)點與遍歷時經(jīng)過的邊構(gòu)成生成樹林。,深度優(yōu)先生成森林,voidDFSTraverse(GraphG，Status(*visit)(intv)visitFunc=Visit;for(v=0；vlchild=p；first=FALSE；elseq-nextsibling=p；q=p；DFSTree(G,w,q)；/if/DFSTree,T,p,q,最小生成樹,問題：設(shè)在n個城市間建立通信網(wǎng)絡(luò)，要求建設(shè)費(fèi)用盡可能低。,模型：n個結(jié)點的圖，結(jié)點連線的權(quán)表示建設(shè)兩點間通信線路的費(fèi)用。在此網(wǎng)絡(luò)的生成樹中找出建設(shè)費(fèi)用最小的生成樹。,最小生成樹,設(shè)G是一個帶權(quán)的無向圖（網(wǎng)絡(luò)），則G的生成樹可能有多個，生成樹各邊的權(quán)之和稱為生成樹的權(quán)。網(wǎng)絡(luò)G的具有最小權(quán)的生成樹稱為G的最小生成樹。,模型：n個結(jié)點的圖，結(jié)點連線的權(quán)表示建設(shè)兩點間通信線路的費(fèi)用。求此網(wǎng)絡(luò)的最小生成樹。,應(yīng)用：設(shè)在n個城市間建立通信網(wǎng)絡(luò)，要求建設(shè)費(fèi)用盡可能低。,Prim算法,假設(shè)N=(V，E)是連通網(wǎng)，T=(U,TE)表示下列算法構(gòu)造的N上最小生成樹。算法從U=u0(u0V)，TE=開始;重復(fù)執(zhí)行下述操作,直至U=V為止：在所有uU，vV-U的邊(u，v)E中找一條權(quán)最小的邊(u，v)，將v并入U，同時邊(u，v)并入集合TE。,設(shè)N有n個結(jié)點.則算法結(jié)束時,T中必有n個結(jié)點,n-1條邊.在2中,如果有相同權(quán)的邊,可任選一條,故最小生成樹不唯一.,例:求下圖的最小生成樹,初始狀態(tài):U=v0,循環(huán):對于每個結(jié)點viU，在vi與U中所有結(jié)點的鄰接邊中找出權(quán)最小的邊ei=(vi,uk),并在這些邊ei中求出權(quán)最小的邊,設(shè)為(vi,uk).將uk并入U,(vi,uk)并入構(gòu)造中的生成樹。,MST性質(zhì),定理:假設(shè)N=(V，E)是一個連通網(wǎng),T=(U,TE)是正在構(gòu)造的生成樹,若(u，v)是一條端點分別在U和V-U,并具有最小權(quán)值的邊，則必存在一棵包含T和邊(u，v)的最小生成樹。,證明:用反證法.設(shè)任何包含T的最小生成樹均不包含邊e=(u,v).設(shè)T是一顆這樣的樹.將e加到T中必然得到一條回路:u,w1,wk,v,u其中必然存在邊e=(wp,wp+1),wpU,wp+1U去掉邊e后打開回路,又形成一顆生成樹T,因為W(e)=W(e),故T是一顆包含T和e的最小生成樹.矛盾!,Prim算法的實現(xiàn),需要設(shè)置一個數(shù)組closedge,紀(jì)錄當(dāng)前每個結(jié)點viU到達(dá)U的最小權(quán)邊(vi,uk)的信息,即closedegei為(uk,minimumW(vi,uk)|ukU)structVertexTypeadjvex；VRTypelowcost；closedgeMAX_VERTEX_NUM,初始狀態(tài):U=v0closedge0=(v0,0);/0表示相應(yīng)結(jié)點屬于Uclosedgei=(v0,W(vi,v0),在closedge中選擇最小權(quán)的邊。假設(shè)vkU是closedge中具有最小權(quán)邊的結(jié)點,則置closedgeklowcost=0,即將vk并入U修改closedge:對于vjU,只需考慮可能出現(xiàn)的新邊(vj,vk)是否具有更小的權(quán)closedgej=minclosedgej.lowcost,W(vj,vk),循環(huán)：,voidMiniSpanTree_PRIM(MGraphG，VertexTypeu)/用普里姆算法從第u個頂點出發(fā)構(gòu)造網(wǎng)G的最小生成樹T，/輸出T的各條邊。假設(shè)用鄰接矩陣存儲G.k=LocateVex(G，u)；for(j=0；j0)邊printf(closedgek.adjvex,G.vexsk);/輸出生成樹的邊closedgek.lowcost=0;/第k個頂點并入U集for(j=0;jG.vexnum;+j)if(G.acrskj.adjclosedgej.lowcost)closedgej=G.vexsk,G.arcskj.adj;/for/MiniSpanTree,時間復(fù)雜度：O(n)+O(n2)=O(n2),Kruskal算法,假設(shè)連通網(wǎng)N=(V，E)，使用Kruskal構(gòu)造最小生成樹的算法：最小生成樹的初始狀態(tài)為只有n個頂點而無邊的非連通圖T=(V，)，圖中每個頂點自成一個連通分量在E中選擇代價最小且頂點落在T中不同的連通分量上的邊，將此邊加入到T中；重復(fù)上述過程2，直至所有頂點都在同一連通分量上為止。,克魯斯卡爾算法構(gòu)造最小生成樹的過程,Kruskal算法可以用堆來實現(xiàn)。設(shè)e是圖的邊數(shù)，則構(gòu)造最小生成樹的總時間代價是O(eloge).,可見，Prim算法適合于邊數(shù)多的圖，而Kruskal算法適合于邊數(shù)少(eadivex；/對i號頂點的每個鄰接點的入度減1if(！(-indegreek)Push(S，k)；/若入度減為0，則入棧/for/whileif(countadivex；/對i號頂點的每個鄰接點的入度減1if(！(-indegreek)Push(S，k)；/若入度減為0，則入棧/for/whileif(countvej)vej=r;當(dāng)j的所有前驅(qū)已經(jīng)排序時,vej便是所求的值.,datafirstarc,StatusTopologicalOrder(ALGraphG，Stack/i號頂點入T棧并計數(shù)for(p=G.verticesi.firstarc；p；p=p-nextarc)j=p-adjvex；/對i號頂點的每個鄰接點的入度減1if(-indegreej=0)Push(S，j)；/若入度減為0，則入棧if(vei+*(p-info)vej)vej=vei+*(p-info)；/for*(p-info)=dut()/whileif(countadjvex；dut=*(p-info)；/dutif(vlk-dutadjvex；dut=*(p-info)；ee=vej；el=vlk-dut；tag=(ee=e1)?*：；printf(j，k，dut，ee，el，tag)；/輸出關(guān)鍵活動/CriticalPath,在拓?fù)渑判蚯髒ei和逆拓?fù)溆行蚯髒li時,所需時間為O(n+e),求各個活動的ek和lk時所需時間為O(e),總時間復(fù)雜度仍然是O(n+e)。,最短路徑,問題的提出：一位旅客要從A城到B城他希望選擇一條途中中轉(zhuǎn)次數(shù)最少的路線；他希望選擇一條途中所花時間最短的路線；他希望選擇一條途中費(fèi)用最小的路線；,這些問題均是帶權(quán)圖上的最短路徑問題。,邊上的權(quán)表示一站邊上的權(quán)代表距離邊的權(quán)代表費(fèi)用,設(shè)G是帶權(quán)有向圖，稱路徑上的第一個頂點為源點(Source)，最后一個頂點為終點(Destination)；一條路經(jīng)的長度是路徑上邊的權(quán)之和；最短路徑問題：如果從圖中某一頂點出發(fā)到達(dá)另一頂點的路徑可能不止一條，如何找到一條長度最小的路徑。,單源最短路徑問題：設(shè)G是帶權(quán)(=0)有向圖，給定一個頂點v，求v到其余頂點的最短距離。,最短路徑的Dijkstra算法,Dijkstra算法基本思想:按路徑長度的遞增次序，逐步產(chǎn)生最短路徑.設(shè)源點為v0首先求出v0為源點長度最短的一條最短路徑，即具有最小權(quán)的邊;求出源點到各個頂點下一個最短路徑：設(shè)其終點是u，則v0到u的最短路徑或者是邊，或者由一條已求得的最短路徑（v0v)和邊構(gòu)成；重復(fù)2直到從頂點v0到其它各頂點的最短路徑全部求出為止。,例：求v0其他各點的最短路徑用S表示已求出最短路徑的結(jié)點集初始狀態(tài)：S=v0,第一條最短路徑：(v0,v2)S=v0,v2,求下一條最短路徑：先求v0到其他頂點vi的只經(jīng)過S結(jié)點的路徑：,v0-v1:v0-v3:(v0,v2,v3)60v0-v4:(v0,v4)30v0-v5:(v0,v5)100,第二條最短路徑：(v0,v4)，S=v0,v2,v4,第一條最短路徑：(v0,v2)S=v0,v2,求下一條最短路徑：先求v0到其他頂點vi的只經(jīng)過S結(jié)點的路徑：,v0-v1:v0-v3:(v0,v2,v3)60,(v0,v4,v3)50v0-v5:(v0,v5)100,(v0,v4,v5)90,第二條最短路徑：(v0,v4)，S=v0,v2,v4,第三條最短路徑：(v0,v4,v3)，S=v0,v2,v4,v3,第四條最短路徑：(v0,v4,v3,v5)，S=v0,v2,v4,v3,v5,用S表示當(dāng)前找到最短路徑的終點集；引入一個輔助數(shù)組D