1、7.1圖的定義和術7.2圖結圖7.1圖的定義和術7.2圖結圖的遍圖的連通性問7.4.3最小生成有向無環圖及其應最短路1圖的結構定義圖是由一個頂點集V 圖的結構定義圖是由一個頂點集V 和一個弧集據結構Graph=(V,R其中，Vx|x的R=/數據VR|v,wV表示vw弧v弧尾， w為弧頭。P(v,w)定義了弧的意義或信息2的圖為有向圖G1=(V1,的圖為有向圖G1=(V1,V1=A,C,D,E VR1=, ,3ABECD,由頂點集和集的,由頂點集和集的圖則稱 (v,w)為頂點v和頂w邊作無向圖,V2=A,B,C,D,E,VR2=(A,B),(B,E),(C,D),(D,F), (B,F),(C,

2、F)BCADFE4名詞和術名詞和術5A9弧（或邊）帶的圖分別稱作網（或無向網）A9弧（或邊）帶的圖分別稱作網（或無向網）BE73CF2AA設圖G=(V,VR)且VVG 為G子圖BECF6假設圖中有假設圖中有n 個頂點，e 條邊，含有e=n(n-1)/2 條邊的無向圖稱完全圖含有 e=n(n-1)條弧的有向圖有向完全圖若邊或弧的個數 enlogn，則稱稀疏圖，否則稱作稠密圖7假若頂點v 和頂點w 之間存在一條邊假若頂點v 和頂點w 之間存在一條邊則稱頂點和互為鄰接點邊(v,w) 和頂點v和相關聯和頂點v 關聯的邊的數目定義為頂點的度BCID(B)=ID(A)=DAEF8A頂點的出度: 以頂點BE

3、CF頂點的入度A頂點的出度: 以頂點BECF頂點的入度以頂點為弧頭的弧的數目OD(B) = ID(B)=TD(B)=頂點的度出度(OD)+入度9設圖G=(,VR) u=vi,0設圖G=(,VR) u=vi,0,vi,1, , vi,m=w中，(vi,j-1,vi,j)VR 1jm,則稱從頂點u 到頂點w 之間存在一條路徑。如:長度為3A不重復出現的路10 BECF若圖G點之間都有路徑相通CBD則稱此圖為連通圖AEFCB若圖G點之間都有路徑相通CBD則稱此圖為連通圖AEFCB子圖稱作此圖的DAEF分量一條有向路徑，則稱此有向圖為強連通圖否則，其各個強連通子圖強連通分量AABEBECF一條有向路徑

4、，則稱此有向圖為強連通圖否則，其各個強連通子圖強連通分量AABEBECFCFBC,通圖有 ne條邊其中 n-1條邊n通圖有 ne條邊其中 n-1條邊n的生成樹CBDAEF的生成森林基本操基本操結構的建CreatGraph(&G,結構的建CreatGraph(&G,按定義(,VR構造銷毀對頂點LocateVex(G,操/對頂點LocateVex(G,操/G中存在頂點u，則返回該頂/圖中“位置否則返回其它信息返回v的值PutVex(&G, v, / 對v賦值value對鄰接點AdjVex(G,對鄰接點AdjVex(G,/ 返回v的“第一個鄰接點。若該頂/在G中沒有鄰接點，則返回“空”NextAdj

5、Vex(G,v, / 返回v的（相對于w的）下一個鄰/點”。若w 是v的最后一個鄰接點，/返回“空”或刪InsertVex(&G, 或刪InsertVex(&G, /在圖G中增添新頂點vDeleteVex(&G, / 刪除G中頂點v及其相關的弧和刪除InsertArc(&G,v,和刪除InsertArc(&G,v,在G中增添弧，若G/則還增添對稱弧w,vDeleteArc(&G, v, /在G中刪除弧，若G/則還刪除對稱弧=0;ifDS(,對v的尚/ 遞歸調用的鄰接頂點/ void DFSTraverse(GraphSus(*void DFSTraverse(GraphSus(*isit)(v

6、)/ 對圖G 作深度優先遍isitFuncisit;for (v=0;vG.vexnum;+v) visitedv=ALSE;/for (v=0;vw1V-w2二、廣度優先搜索遍歷對連通圖，從起始點V其中，V-w1V-w2VV的路徑長度為-的路徑長度為-w8w4的路徑長度為3從圖中的某個頂點V0此V0的所有未頂點之后鄰接點，之后它們的鄰接點和V0從圖中的某個頂點V0此V0的所有未頂點之后鄰接點，之后它們的鄰接點和V0void BFSTraverse(GraphSus*for(v=0;vG.vvoid BFSTraverse(GraphSus*for(v=0;vG.vexn;visitedv=/

7、初始nu置空的輔助隊列for(vv+vif(!visitedv)v尚/ visitedv = EnQueue(Q, isit(v);vv入visitedv = EnQueue(Q, isit(v);vv入隊whileDeQueue(Q,隊頭元素出隊并置為AdjVex(G,u);if(!EnQueue(Q,w);/ /的頂點w的的7.1判斷下圖是否強連通圖。如果不是，則給出7.1判斷下圖是否強連通圖。如果不是，則給出強連通分ABDC7.2 寫出下圖從頂點1出發的一種廣度優123674589連通：頂點v至之間有路徑存連通圖：G則稱G是連通圖。連通分量：ABAB連通：頂點v至之間有路徑存連通圖：G則

8、稱G是連通圖。連通分量：ABABFGEEFGHHIJIJKLMMKLCDCD無向圖G的三個連通分無向圖通；也可通過對算法BFSTraverse()如何設計算法以求出無向圖G中的所有n一棵樹的n-1條邊ABABABABEHEHEHEH無向圖MMMMCDCDCDC中的所有n一棵樹的n-1條邊ABABABABEHEHEHEH無向圖MMMMCDCDCDCD一棵有n個頂點的生成樹有且僅有n-1圖。如果它多于n-1 條邊，則一定有環。DFS生成樹和BFS生成一個子圖，該子圖稱為生成樹。因此有DFS生成樹aBFS生成樹BFS生成acdefacdeDFS生成樹和BFS生成一個子圖，該子圖稱為生成樹。因此有DF

9、S生成樹aBFS生成樹BFS生成acdefacdefhkcdefhkDFS生成h無向圖(連通網(連通網的)最小生成假設要在n聯絡網，則連通n e條帶權的邊中選取n-1條邊（回路），使“權值之和”為最小1e條帶權的邊中選取n-1條邊（回路），使“權值之和”為最小1615234344325656左圖的最小代價生成MST性通圖，U是結點集合VG=V,E。若(u,v)是一條代價最小的邊，且u屬于U,v屬于V - U,存在一棵包括邊(u,v)設其為T。將邊(u,v)添加到樹 T,則形成一條包含(u v)。因此，必定MST性通圖，U是結點集合VG=V,E。若(u,v)是一條代價最小的邊，且u屬于U,v屬于

10、V - U,存在一棵包括邊(u,v)設其為T。將邊(u,v)添加到樹 T,則形成一條包含(u v)。因此，必定存在另一條邊(u，v),且u屬于,v屬于- 。刪去邊(u,v)，得到另一棵生成樹因為邊(u,v)小于邊(u，v)的代價，所以新的生成樹T將是代價最小的U。vV-uT算法一：（普里姆算法算法二：（克魯斯卡爾算法算法一：（普里姆算法算法二：（克魯斯卡爾算法:普里:普里之后往生成樹上添加新的頂點 w。在添加的頂點w和已經在生成樹上的頂點v之間連通頂點v 和 w 之間的邊中取值最小。之上含有n-1個頂點為止ab5cegdfab5cegdf=14+8+3+5+16+2162 條件在生成樹的構造過

11、程中，圖中條件在生成樹的構造過程中，圖中nU 和尚未落在生成樹上的頂點集 V-U，則應在所有連通U中頂點和V-U中頂點的邊中選取權值最小的邊設置一個輔助數組，對當前VU設置一個輔助數組，對當前VU和頂點集U中頂structU集中的頂點邊的權wcosedgeMAX_EE_N;abec37d8gfabcdefg0123456cdeadews53 abec37d8gfabcdefg0123456cdeadews53 /用普里姆算法從頂點u出發構造網G的最小生for(j=0;jexnu;+jif/輔助數組初始closedgej=u,G.arcskj.adjclosedgek.lowcost=/ 初始f

12、or (i=0;iG.vexnum;+i)繼續向生成樹上添加頂點;k=ik=il)/ 求出加入生成樹的下一個頂點f(closedgek.adjvex,輸出生成樹上一closedgek.lowcost=/k頂點并入Ufor (j=0;jexnu;/修改其它頂點的最小if (G.arcskj.adj closedgej.lowcost) closedgej = G.vexsk, G.arcskj.adj ;：考慮問題的出發點: 為使生成樹上值之和達到最小具體做法：考慮問題的出發點: 為使生成樹上值之和達到最小具體做法先構造一個只含nSG加不使SGSG條邊，如此重復，直至加上 n-1 條邊為。ab5

13、cegdfab5cegdf算法描述構造非連通圖算法描述構造非連通圖ST=,k=i=k計選中的邊while(kn-1)E第 i條權值最小的邊若(u,v)加入ST后不使ST中產生回路輸出邊則且當前形成的集合樹一個無環的有向圖稱為一個無環的有向圖稱為有向無環圖(directedacycline DAG7.5.1問題7.5.1問題課課程代課程名先修程序設計基離散數計算機原編譯原操作系高等數線性代普通物數值分C1,79,C10何謂“何謂“拓撲排序BADCABADCABCACB或BADC因為圖中存BADC因為圖中存在一個回路,C,如何進行拓撲排序如何進行拓撲排序有以它為尾的弧abhcdgfe沒有前驅的頂點

14、 入度為零的頂刪除頂點及以它為尾的弧 弧頭頂點的入79減abhcdgfe沒有前驅的頂點 入度為零的頂刪除頂點及以它為尾的弧 弧頭頂點的入79減取入度為零的頂點while (v0)取入度為零的頂點while (v0)while (w0)inDegreew-取下一個入度為零的頂點iff(“圖中有回路述”for (i=0;iexnu;ifPush(S,/入度為零的頂點入/對輸出頂點計while (!EmptyStack(S)Pop(S,for/對輸出頂點計while (!EmptyStack(S)Pop(S,forAdj(v);-弧頭頂點的入度減ifPush(S,/新產生的入度為零的頂點入if (c

15、ountG.vexnum)f(“圖中有回路)問題問題AOEOnEdge)帶權的AOEAOEOnEdge)帶權的AOE向無環圖，其中頂點表示事件，弧表整個工程完成的時間為：從有向圖的源點到的最長路徑bg26整個工程完成的時間為：從有向圖的源點到的最長路徑bg2618aek47145ch42df“關鍵活動”指的是：該弧上的權值增加 有向圖上的最長路徑的長度增加“事件(頂點)” “事件(頂點)” 的最早發生時間“事件(頂點)” 的最遲發生時間假設第i條弧為j,假設第i條弧為V1再下一條路徑長度次短的最短路徑的特點它可能有三種情況：或者是再下一條路徑長度次短的最短路徑的特點它可能有三種情況：或者是該點

16、(只含一條弧或者是從源點經過頂點 從源點經過頂點v2它或者是直接從源點到該點(只含一或者是從源點經過已求得最短路的頂點，再到達該頂點設置輔助數組Dist，其中設置輔助數組Dist，其中每個分量當前所求得的從源點到其余各頂點的最短路徑。Distk源點到頂點k的弧上的權值或者= + 其它頂點到頂點k 的弧上的權值1）Distk1）DistkG.arcsv0kV0和k之間存在V0和k其中的最小值即為最短路徑的長度2）修改其它各頂點的Distk值若 Distu+G.arcsukDistk則將Distk改為Distu+G.arcsuk4設一個集合U，存放以產生的最短路徑的頂點。初始，U含源點52dist

17、第二條路：1到2、5、84設一個集合U，存放以產生的最短路徑的頂點。初始，U含源點52dist第二條路：1到2、5、8中后，某些頂點的值應調整471945336x的中間點必定都在U屬于U，如左Ux則必定有disuu, dist按算法，原點到u106 路徑應已產生，即u屬于u678dist54976. Dijkr算法描5932867g6. Dijkr算法描5932867g123458123445566778111123182345672357234567467652345672圖用鄰接矩陣表示，設置集合U與輔助數源點vo圖的頂點數為ngi,j代表上的權(1) disti=gv0,i(2) U=v0;(3) 下面步驟重復n-1選擇v使得滿足 distv=mindistu|uU v加到集合U中 6. Dijkr算法描1826. Dijkr算法描182375466257. Dijk7. Dijkr 算法的C由于C/C+的下標從0開始，所以算法中作相應的改動，用NUM圖的頂點間分析#definevoid shortpath_dij(gNUM,v0) /v0為源點，值為1到setv0-/用1表示源點屬于U集 if(setw= =0 & distwmin) v=w; min=d