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

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

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

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

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

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

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

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

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

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

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

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

13、cegdfab5cegdf算法描述構(gòu)造非連通圖算法描述構(gòu)造非連通圖ST=,k=i=k計選中的邊while(kn-1)E第 i條權(quán)值最小的邊若(u,v)加入ST后不使ST中產(chǎn)生回路輸出邊則且當(dāng)前形成的集合樹一個無環(huán)的有向圖稱為一個無環(huán)的有向圖稱為有向無環(huán)圖(directedacycline DAG7.5.1問題7.5.1問題課課程代課程名先修程序設(shè)計基離散數(shù)計算機(jī)原編譯原操作系高等數(shù)線性代普通物數(shù)值分C1,79,C10何謂“何謂“拓?fù)渑判駼ADCABADCABCACB或BADC因?yàn)閳D中存BADC因?yàn)閳D中存在一個回路,C,如何進(jìn)行拓?fù)渑判蛉绾芜M(jìn)行拓?fù)渑判蛴幸运鼮槲驳幕bhcdgfe沒有前驅(qū)的頂點(diǎn)

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

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

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

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