圖的定義和術(shù)語

第七章圖7.1圖的定義和術(shù)語7.2圖的存儲結(jié)構(gòu)7.3圖的遍歷7.4圖的連通性問題7.5有向無環(huán)圖及其應(yīng)用7.6最短路徑1精選課件第七章圖在線性結(jié)構(gòu)中，數(shù)據(jù)元素之間是一對一的線性關(guān)系，除第一個數(shù)據(jù)元素和最后一個數(shù)據(jù)元素之外，每個數(shù)據(jù)元素只有一個直接前驅(qū)和一個直接后繼。在樹型結(jié)構(gòu)中，數(shù)據(jù)元素之間是一對多的層次和分支的關(guān)系，除根結(jié)點外，每個數(shù)據(jù)元素都只有一個直接前驅(qū)〔即雙親結(jié)點〕，但每個數(shù)據(jù)元素都可能有多個直接后繼〔即孩子結(jié)點〕。然而在圖型結(jié)構(gòu)中，數(shù)據(jù)元素之間的關(guān)系是任意的，是多對多的關(guān)系，既圖中任意兩個結(jié)點之間都可能相關(guān)。2精選課件7.1圖的定義和術(shù)語圖中的數(shù)據(jù)元素通常稱為頂點。圖G由兩個集合V和E組成，通常記為G＝(V，E)其中，V是圖中頂點的有窮非空集合，E是V中頂點間的邊的有窮集。

除此之外，也通常將圖G的頂點集和邊集分別記為V(G)和E(G)。E(G)可以是空集。假設(shè)E(G)為空，那么圖G只有頂點而沒有邊。圖可分為無向圖和有向圖兩類。3精選課件7.1圖的定義和術(shù)語無向圖：圖中的每條邊都是無方向的。在無向圖中，一條無向邊是由兩個頂點組成的無序?qū)?，通常用圓括號表示。例如〔vi，vj〕表示一條無向邊，在無向圖中，〔vi，vj〕和〔vj，vi〕是兩條相同的無向邊?！矡o向〕完全圖：任意兩個頂點之間都有一條無向邊的無向圖。〔無向〕完全圖是含有n個頂點和n(n-1)/2條邊的無向圖。4精選課件7.1圖的定義和術(shù)語如以下圖G是一個無向圖BCAFED圖G可記作：G＝〔V，E〕，其中V＝{A,B,C,D,E,F}E={(A,B),(A,E),(B,F),(B,E),(C,F),(C,D),(D,F)}假設(shè)(vi，vj)是一條無向邊，那么稱頂點vi和vj互為鄰接點，或稱vi和vj相鄰接；同時稱邊(vi，vj)依附于頂點vi和vj，或稱邊(vi，vj)與頂點vi和vj相關(guān)聯(lián)。5精選課件7.1圖的定義和術(shù)語有向圖：圖中的每條邊都是有方向的。在有向圖中，一條有向邊是由兩個頂點組成的有序?qū)?，通常用尖括號表示。例?lt;vi，vj>表示一條有向邊，vi是邊的起始點，vj是邊的終點。因此，<vi，vj>和<vj，vi>是兩條不同的有向邊。有向邊也稱為弧，邊的起始點稱為弧尾，終點稱為弧頭。6精選課件7.1圖的定義和術(shù)語如以下圖G是一個有向圖ABECF圖G可記作：G＝〔V，E〕，其中V＝{A,B,C,D,E,F}E={<A,B>,<A,E>,<B,C>,<C,F>,<F,A>,<F,B>,<E,C>}假設(shè)＜vi,vj＞是圖中的一條有向邊，那么稱頂點vj是vi的領(lǐng)接點，或稱頂點vi鄰接到vj，或頂點vj鄰接自頂點vi，并稱弧＜vi,vj＞依附于頂點vi和vj，或稱?。紇i,vj＞與頂點vi和vj相關(guān)聯(lián)。7精選課件7.1圖的定義和術(shù)語有向完全圖：任意兩個頂點之間都有一對相向的有向邊的有向圖。即含有n個頂點和n(n-1)條弧〔有向邊〕的有向圖。ABECF1597211132權(quán)：與圖的邊或弧相關(guān)的數(shù)。這些權(quán)可以表示從一個頂點到另一個頂點的距離或者消耗。網(wǎng)：弧〔或邊〕帶權(quán)的圖稱為網(wǎng)。8精選課件7.1圖的定義和術(shù)語子圖：給定圖G1=〔V1，E1〕、圖G2=〔V2，E2〕，假設(shè)V1是V2的子集，E1是E2的子集，那么稱G1是G2的子圖。例：ABECF圖GAB圖G1CF圖G3E圖G2CE圖G49精選課件7.1圖的定義和術(shù)語無向圖中頂點v的度：指的是和v相關(guān)聯(lián)的邊的數(shù)目，通常記為D(v)。BCAFED例：在右圖中D(B)=D(F)＝

3D(A)=D(C)

=D(D)=D(E)=2結(jié)論無向圖中：頂點的度之和=邊數(shù)的兩倍10精選課件7.1圖的定義和術(shù)語有向圖中頂點v的度分為入度和出度。頂點v的入度：以頂點v為終點的有向邊的數(shù)目，記為ID(v)；頂點v的出度：以頂點v為起始點的有向邊的數(shù)目，記為OD(v)；有向圖中頂點v的度那么定義為該頂點的入度和出度之和，即D(v)＝ID(v)十OD(v)。11精選課件7.1圖的定義和術(shù)語例：在下面的有向圖中ID(A)=1；OD(A)=2;D(A)=3ID(C)=1；OD(C)=1;D(C)=3ABECF結(jié)論有向圖中：頂點入度之和=頂點出度之和=弧數(shù)12精選課件7.1圖的定義和術(shù)語在無向圖G中，假設(shè)存在一個頂點序列〔vp,vi1,…，vin，vq〕，使得(vp，vil)，(vi1,vi2)，…，(vin，vq)均屬于邊集E(G)，那么稱頂點vp到vq存在一條路徑。假設(shè)G是有向圖，那么路徑也是有向的，它由E(G)中的有向邊＜vp，vil＞,＜vil，vi2＞,…，＜vin，vq＞組成。路徑長度：該路徑上邊的數(shù)目。序列中頂點不重復(fù)出現(xiàn)的路徑稱為簡單路徑。起點和終點相同(vp＝vq)的路徑稱為回路。假設(shè)一條路徑上除了vp和vq可以相同外，其余頂點均不相同，那么稱此路徑為簡單回路或簡單環(huán)。13精選課件7.1圖的定義和術(shù)語例如：在有向圖G中：〔A,B,C,F〕是圖G的一條路徑，它是由有向邊序列<A,B>,<B,C>,<C,F>組成，它是一條簡單路徑，路徑的長度是3?！睞,B,C,F,B,E〕也是圖G的一條路徑，它是由有向邊序列〈A,B>,<B,C>,<C,F>,<F,B>,<B,E>組成，它不是簡單路徑，這條路徑的長度是5。<A,B>,<B,C>,<C,F>,<F,A>也是圖G的一條路徑，這條路徑的長度是4，它是一條簡單回路。ABECF14精選課件7.1圖的定義和術(shù)語在無向圖G中，假設(shè)從頂點vi到頂點vj有路徑，那么稱vi和vj是連通的。假設(shè)圖G中任意兩個不同的頂點vi和vj都連通，那么稱G為連通圖。無向圖G的一個極大連通子圖稱為G的一個連通分量。顯然，任何連通圖的連通分量只有一個，就是它自身，而非連通的無向圖有多個連通分量。15精選課件7.1圖的定義和術(shù)語例如：以下圖所示為兩個無向圖G1和G2，其中:G1是一個連通圖G2是由4個連通分量組成的非連通圖。BCAFED無向圖G1BEADCGHIFJ無向圖G216精選課件7.1圖的定義和術(shù)語在有向圖G中，假設(shè)對于其中的任意兩個不同的頂點vi和vj，從vi到vj和從vj到vi都存在路徑，那么稱G是強連通圖。有向圖G的極大強連通子圖稱為G的強連通分量。顯然，強連通圖只有一個強連通分量，即是其自身。非強連通的有向圖有多個強連通分量。17精選課件7.1圖的定義和術(shù)語例如：以下圖所示為兩個有向圖G1和G2，其中:G1是一個強連通圖，G2是由3個強連通分量組成的非連通圖。ABECF有向圖G1ABECF有向圖G218精選課件7.1圖的定義和術(shù)語結(jié)論有n個頂點的有向圖最多有條邊，最少有條邊。有n個頂點的無向圖最多有條邊，最少有條邊。有n個頂點的連通圖最少有條邊，假設(shè)少于條邊，圖一定是非連通圖，多于條邊，連通圖中一定有環(huán)路存在。n(n-1)n(n-1)/200n-1n-1n-119精選課件7.1圖的定義和術(shù)語生成樹：一個連通圖的生成樹是一個極小連通子圖，它含有圖中全部頂點，但只含有足以構(gòu)成一棵樹的n-1條邊。如下圖：連通圖G的一棵生成樹注意:

一棵有n個頂點的生成樹一定有n-1條邊。但有n個頂點和n-1條邊的圖，一定是一棵生成樹嗎？ABECFABECF1棵生成樹20精選課件7.2圖的存儲結(jié)構(gòu)由于圖的結(jié)構(gòu)比較復(fù)雜，除了要把圖的各頂點存入計算機，還應(yīng)該把各頂點之間的關(guān)系也輸入計算機，而圖中任意兩個頂點之間都可能存在聯(lián)系，因此無法以數(shù)據(jù)元素在存儲區(qū)中的物理位置來表示元素之間的關(guān)系，即圖沒有順序映象的存儲結(jié)構(gòu)，但可以借助數(shù)組的數(shù)據(jù)類型表示圖中頂點之間的關(guān)系，即圖的領(lǐng)接矩陣的存儲結(jié)構(gòu)。另一方面，也可以用鏈表表示圖，如領(lǐng)接表、領(lǐng)接多重表和十字鏈表是圖常用的三種鏈式存儲結(jié)構(gòu)。21精選課件7.2圖的存儲結(jié)構(gòu)對于具體問題中的圖來說,要為其選擇最好的存儲結(jié)構(gòu)，不僅僅要依賴于圖的性質(zhì)如有向圖還是無向圖,以及圖中的數(shù)據(jù),例如:頂點數(shù),邊數(shù)等,而且還與在圖上所實施的操作有關(guān)，例如對圖中的頂點進行插入或刪除操作的頻率等.下面將主要介紹圖的領(lǐng)接矩陣和領(lǐng)接表這兩種存儲方式。22精選課件7.2.1鄰接矩陣鄰接矩陣(數(shù)組表示法〕是用二維數(shù)組表示頂點之間相鄰關(guān)系的存儲結(jié)構(gòu)。設(shè)G＝(V，E)是具有n個頂點的無權(quán)圖，那么G的鄰接矩陣是具有如下性質(zhì)的n階方陣：A[i,j]={若(vi,vj)或<vi,vj>是E(G)中的邊

0

反之23精選課件7.2.1鄰接矩陣例1：給定4個頂點的有向圖24精選課件7.2.1鄰接矩陣例2：給定6個頂點的無向圖①⑥⑤

④

③

②A注:無向圖的鄰接矩陣是對稱的，即

A[i][j]=A[j][i]

25精選課件7.2.1鄰接矩陣假設(shè)G＝(V，E)是具有n個頂點的帶權(quán)圖〔網(wǎng)〕那么G的鄰接矩陣是具有如下性質(zhì)的n階方陣：A[i,j]={Wij若(vi,vj)或<vi,vj>是E(G)中的邊，Wij為邊上的權(quán)值∞

反之26精選課件7.2.1鄰接矩陣例１：給定6個頂點的無向網(wǎng)〔無向帶權(quán)圖〕①⑥⑤

④

③

②5781014124A=∞5

∞∞8∞

∞∞∞107∞∞

∞4∞14∞∞4

∞∞12810∞∞∞∞∞71412∞∞無向網(wǎng)G1及其領(lǐng)接矩陣存儲結(jié)構(gòu)27精選課件7.2.1鄰接矩陣例2：給定6個頂點的有向網(wǎng)〔有向帶權(quán)圖〕

v0v1v2v3v4v5v0∞∞10∞30100v1∞∞∞∞∞∞v2∞5∞50∞∞v3∞∞∞∞∞10v4∞∞∞20∞60v5∞∞∞∞∞∞v0v5v1v2v4v33010205051010060圖G2的領(lǐng)接矩陣存儲結(jié)構(gòu)有向帶權(quán)圖G228精選課件7.2.1鄰接矩陣結(jié)論在無向圖的領(lǐng)接矩陣中,頂點vi的度等于鄰接矩陣中第i行(或第i列)上非零元素的個數(shù)；在有向圖的領(lǐng)接矩陣中，頂點vi的出度等于鄰接矩陣中的第i行上非零元素的個數(shù);在有向圖的領(lǐng)接矩陣中，頂點vi的入度等于鄰接矩陣中的第i列上非零元素的個數(shù).29精選課件7.2.1鄰接矩陣圖的領(lǐng)接矩陣存儲表示用鄰接矩陣表示法表示圖，除了存儲用于表示頂點間相鄰關(guān)系的鄰接矩陣外，通常還需要用一個順序表來存儲圖的頂點信息。其形式說明如下：#definen6 /*圖的頂點數(shù)*/#definee8 /*圖的邊〔弧〕數(shù)*/typedefstruct{charvexs[n+1]；/*設(shè)頂點的數(shù)據(jù)類型為char型*/intarcs[n+1][n+1]；/*設(shè)權(quán)值類型為int*/}Graph；GraphG;30精選課件7.2.1鄰接矩陣創(chuàng)立無向網(wǎng)的算法#defineMAX10000CreatGraph(Graph*G)/*建立無向網(wǎng)絡(luò)*/{inti，j，k；intw；for(i＝1；i＜=n；i++)G->vexs[i]＝getchar()；/*讀入n個頂點信息*/for(i＝1；i＜=n；i++)for(j＝1；j＜=n；j++)G->arcs[i][j]＝MAX；/*鄰接矩陣初始化*/for(k＝1；k＜=e；k++)/*讀入e條邊*/{scanf(〞％d％d％d〞，&i,&j,&w)；G->arcs[i][j]＝w；G->arcs[j][i]＝w；}}31精選課件7.2.1鄰接矩陣分析該算法的時間復(fù)雜度算法的執(zhí)行時間是O(n+n2+e)，其中O(n2)的時間消耗在鄰接矩陣的初始化操作上。因為e＜n2，所以，算法的時間復(fù)雜度是O(n2)。32精選課件7.2.2

鄰接表領(lǐng)接表是圖的一種鏈式存儲結(jié)構(gòu)。類似于樹的孩子鏈表表示法。在領(lǐng)接表存儲結(jié)構(gòu)中，對于圖G中的每個頂點vi，把vi的所有鄰接點鏈成一個單鏈表，這個單鏈表就稱為頂點vi的鄰接點單鏈表。那么，假設(shè)圖有n個頂點，就有n個領(lǐng)接點單鏈表。為了便于隨機訪問任一頂點的鄰接點單鏈表，通常將所有鄰接點單鏈表的頭結(jié)點順序存儲在一個結(jié)構(gòu)體數(shù)組中。33精選課件7.2.2

鄰接表n個領(lǐng)接點單鏈表的表頭結(jié)點結(jié)構(gòu)均為：含有兩個域，一個是頂點域，用來存放頂點vi的信息；另一個是指針域，用來指向vi的領(lǐng)接點單鏈表中的第一個結(jié)點。在頂點vi的鄰接點單鏈表中，每個結(jié)點均有兩個域，一個是鄰接點域，用以存放與vi的領(lǐng)接點vj的信息；另一個是指針域，用來指向與vi相鄰的下一個領(lǐng)接點。34精選課件7.2.2

鄰接表v0v5v1v2v4v32361534^^^V0V1V2V3V4V55^^^例1：圖的領(lǐng)接表存儲結(jié)構(gòu)

注意：圖的鄰接矩陣表示是唯一的，但其鄰接表不唯一35精選課件7.2.2

鄰接表例2：圖的領(lǐng)接表存儲結(jié)構(gòu)

V5V3V2V6V1V425516664322431^^^^^^V1V2V3V4V5V636精選課件7.2.2

鄰接表創(chuàng)立領(lǐng)接表的算法思想建立無向圖的鄰接表時，每讀入一個頂點對〔i,j〕時，就創(chuàng)立一個鄰接點序號為j的新結(jié)點，將其插入到vi為表頭結(jié)點的領(lǐng)接點單鏈表中；同時生成一個鄰接點序號為i的新結(jié)點，將其插入到vj為表頭結(jié)點的單鏈表中。建立有向圖的鄰接表與此類似，只是更加簡單，每讀入一個頂點對序號＜i，j＞時，僅需生成一個鄰接點序號為j的新結(jié)點，將其插入到vi為表頭結(jié)點的領(lǐng)接點單鏈表中即可。假設(shè)建立網(wǎng)絡(luò)的鄰接表，那么需在鏈表的每個結(jié)點中增加一個存儲邊上的權(quán)值的數(shù)據(jù)域。37精選課件7.2.2

鄰接表領(lǐng)接表存儲結(jié)構(gòu)的結(jié)論在無向圖的領(lǐng)接表中頂點vi的度等于vi的鄰接點鏈表中的結(jié)點個數(shù)在有向圖的領(lǐng)接表中頂點vi的出度等于vi的鄰接點鏈表中的結(jié)點個數(shù)；頂點vi的入度等于vi在所有領(lǐng)接點鏈表中出現(xiàn)的次數(shù)；38精選課件7.2.2

鄰接表對于有向圖G中的每個頂點vj，把所有鄰接到vj的頂點vi鏈成一個單鏈表，這個單鏈表就稱為頂點vj的逆鄰接表。如下例2162643^^^^^^123456①⑥⑤

④

③

②39精選課件7.3

圖的遍歷和樹的遍歷類似，圖的遍歷也是從某個頂點出發(fā),沿著某條搜索路徑訪問圖中所有頂點，且每個頂點僅被訪問一次。假設(shè)給定的圖是連通圖，那么從圖中任一頂點出發(fā)均可以訪問到該圖的所有頂點。由于圖中的任一頂點都可能和其余頂點相鄰接，故在訪問了某個頂點之后，可能順著某條回路又回到了該頂點。因此，在遍歷圖的過程中，為了防止重復(fù)訪問同一個頂點，必須記住每個頂點是否被訪問過。為此，可設(shè)置一個輔助數(shù)組visited[n]，它的初值為全為0，一旦訪問了頂點vi，便將visited[i]置為1。通常圖的遍歷有兩種路徑：深度優(yōu)先搜索和廣度優(yōu)先搜索。40精選課件7.3.1圖的深度優(yōu)先搜索深度優(yōu)先搜索類似于樹的先序遍歷。假設(shè)給定圖G的初態(tài)是所有頂點均未訪問過，在G中任選一頂點vi作為初始出發(fā)點，那么深度優(yōu)先搜索可定義為：首先，訪問出發(fā)點vi，并將其標記為已訪問過，然后，依次從vi的未曾訪問過的鄰接點出發(fā)繼續(xù)進行深度優(yōu)先搜索,直到圖中所有與vi有路徑相通的頂點都被訪問到；假設(shè)此時圖中還有頂點未被訪問〔即當(dāng)圖為非連通圖時〕，那么另選圖中一個未曾被訪問的頂點作起始點，重復(fù)上述過程，直到圖中所有頂點都被訪問到為止。41精選課件7.3.1圖的深度優(yōu)先搜索例1:圖的深度優(yōu)先搜索12345678圖7.13(a)深度優(yōu)先搜索結(jié)果:v1-v2-v4-v8-v5-v3-v6-v742精選課件7.3.1圖的深度優(yōu)先搜索深度優(yōu)先搜索算法如下：voidDFSTraverse(GraphG,intv){for(v=0;v<G.vexnum;v++)visited[v]=0;for(v=0;v<G.vexnum;v++)if(!visited[v])DFS(G,v);}voidDFS(GraphG,intv〕{visited[v]=1;printf(“％d〞，v);w=FirstAdjVex(G,v);//找v的第一個領(lǐng)接點while(w!＝NULL){if(!visited[w])DFS(G,w);//假設(shè)該頂點w未被訪問過，那么從它出發(fā)進行深度優(yōu)先搜索，否那么，找v的下一個鄰接點w=w－>next;}}43精選課件7.3.2圖的廣度優(yōu)先搜索廣度優(yōu)先搜索類似于樹的按層次遍歷。設(shè)圖G的初態(tài)是所有頂點均未訪問過，在G中任選一頂點Vi為初始出發(fā)點，那么廣度優(yōu)先搜索的根本思想是：首先訪問出發(fā)點Vi，接著依次訪問vi的所有鄰接點wl，w2，…，wt，然后，再依次訪問與wl，w2，…，wt鄰接的所有未曾訪問過的頂點，依此類推，直至圖中所有和出發(fā)點v有路徑相通的頂點都已訪問到為止;假設(shè)此時圖中尚有頂點未被訪問〔即當(dāng)圖為非連通圖時〕，那么另選圖中一個未曾被訪問的頂點作起始點，重復(fù)上述過程，直到圖中所有頂點都被訪問到為止。44精選課件7.3.2圖的廣度優(yōu)先搜索例1:圖的廣度優(yōu)先搜索12345678圖7.13(a)廣度優(yōu)先搜索結(jié)果：v1-v2-v3-v4-v5-v6-v7-v845精選課件7.3.2圖的廣度優(yōu)先搜索廣度優(yōu)先搜索算法如下：voidBFS(GraphG,intv〕{InitQueue(Q);visited[v]=1;printf(“％d〞，v);EnQueue(Q,v);while(!QueueEmpty(Q)){DelQueue(Q,u);for(w=FirstAdjVex(G,u);w;w=w－>next)if(!visited[w]){visited[w]=1;printf(“％d〞，w);EnQueue(Q,w);}}}46精選課件7.3.2圖的廣度優(yōu)先搜索voidBFSTraverse(GraphG,intv){for(v=0;v<G.vexnum;v++)visited[v]=false;for(v=0;v<G.vexnum;v++)if(!visited[v])BFS(G,v);}47精選課件7.4圖的連通性問題7.4.1無向圖的連通分量和生成樹在無向圖的遍歷算法中，假設(shè)從某個頂點出發(fā)訪問下一個頂點時增加這兩個頂點之間的邊，那么可得到連通圖的一棵生成樹或不連通的圖的生成森林。由深度優(yōu)先遍歷得到的生成樹稱為深度優(yōu)先生成樹。由廣度優(yōu)先遍歷得到的生成樹稱為廣度優(yōu)先生成樹。48精選課件7.4.2

最小生成樹圖的生成樹不是唯一的，從不同的頂點出發(fā)進行遍歷，可以得到不同的生成樹。對于連通網(wǎng)G＝(V，E)而言，圖中的邊是帶權(quán)的，因而G的生成樹的各條邊也是帶權(quán)的。我們把生成樹各條邊的權(quán)值總和稱為生成樹的權(quán)〔或稱代價〕，并把權(quán)最小的生成樹稱為G的最小生成樹。生成樹和最小生成樹有許多重要的應(yīng)用。例如：令圖G的頂點表示城市，邊表示連接兩個城市之間的通訊線路。n個城市之間最多可設(shè)立n(n-1)／2條線路，把n個城市連接起來至少要n-1條線路,那么圖G的生成樹表示了建立通訊網(wǎng)絡(luò)的可行方案。49精選課件7.4.2

最小生成樹如果給圖中的邊都賦予權(quán)，而這些權(quán)可表示兩個城市之間通訊線路的長度或建造代價，那么，如何選擇n-1條線路，使得建立的通訊網(wǎng)絡(luò)其線路的總長度最短或總代價最小呢?這就轉(zhuǎn)換為如何構(gòu)造該圖的一棵最小生成樹的問題。以下我們只討論無向圖的最小生成樹問題。50精選課件7.4.2

最小生成樹V1V2V4V3V5V6613555664251精選課件7.4.2

最小生成樹構(gòu)造最小生成樹可以有多種算法，其中大多數(shù)構(gòu)造算法都是利用了最小生成樹的下述性質(zhì)：設(shè)G＝(V,E)是一個連通帶權(quán)圖，U是頂點集V的一個真子集。假設(shè)邊(u,v)〔u∈U，v∈V-U〕是圖G的所有邊中權(quán)值最小的一條邊，那么一定存在圖G的一棵最小生成樹包含此邊(u,v)。這個性質(zhì)稱為MST性質(zhì)?？捎梅醋C法證明(略)下面將重點介紹兩個利用MST性質(zhì)構(gòu)造最小生成樹的算法：普里姆〔Prim〕算法和克魯斯卡爾〔Kruskal〕算法。52精選課件7.4.2

最小生成樹Prim算法的根本思想是：假設(shè)G=(V，E〕是連通網(wǎng)，設(shè)T=(U，TE)是最小生成樹初始情況下設(shè)U＝{u0}(u0∈V〕,TE＝{}.重復(fù)執(zhí)行下述操作：在所有的u∈U，v∈V－U的邊(u，v)∈E中，找一條權(quán)值最小的邊〔u0,v0)，將其并入集合TE，同時將v0并入集合U，直至U＝V為止，此時TE中必有n－1條邊，那么T=(U,TE)即為G的一棵最小生成樹。53精選課件7.4.2

最小生成樹Prim算法求最小生成樹：1.〔1,2〕被選中U={1,2}2.〔2,5〕被選中U={1,2,5}3.〔2,3〕被選中U={1,2,3,5}4.〔1,4〕被選中U={1,2,3,4,5}6.〔5,7〕被選中U={1,2,3,4,5,6,7}7.〔7,8〕被選中U={1,2,3,4,5,6,7,8}5.〔3,6〕被選中U={1,2,3,4,5,6}U={1},TE={}

①1②2③31453

④4⑤9⑥10589

⑦6⑧①1②2③3④1⑤4⑥5⑦6⑧54精選課件7.4.2

最小生成樹Kruskal算法的根本思想：假設(shè)G=(V，E〕是連通網(wǎng)，設(shè)T=(U，TE)是要求的最小生成樹。初始情況下設(shè)U＝V,TE＝{}.并將連通網(wǎng)中的所有邊按權(quán)值的非遞減次序進行排列，然后執(zhí)行：依次將連通網(wǎng)中有序排列的各條邊〔u,v〕作如下處理：假設(shè)將〔u,v〕參加TE中后，TE中的邊構(gòu)成了一條回路，那么不將〔u,v〕參加TE中；否那么將〔u,v〕參加TE中。重復(fù)上述過程，直至TE中已有n-1條邊為止。此時T=(U,TE)即為G的一棵最小生成樹。55精選課件7.4.2

最小生成樹Kruskal算法求最小生成樹過程：1.〔1，2〕被選中2.〔2，5〕被選中3.〔2，3〕被選中4.〔1，4〕被選中6.〔5，6〕不被選中8.〔5，7〕被選中7.〔7，8〕被選中5.〔3，6〕被選中①②③

④⑤⑥

⑦5⑧1312464

①1②2③31455

④8⑤4⑥96109

⑦5⑧56精選課件7.4.2

最小生成樹練習(xí)題：分別用Prim算法和Kruskal算法求如下無向圖的最小生成樹。V1V2V4V3V5V66135556642V2V4V5V6V1V313542V1V2V4V3V5V613542無向帶權(quán)圖G用Prim算法求其最小生成樹用Kruskal算法求其最小生成樹57精選課件7.5有向無環(huán)圖及其應(yīng)用有向無環(huán)圖:是一個無環(huán)的有向圖.簡稱DAG圖.有向無環(huán)圖的作用:常用來描述一個過程〔如一個系統(tǒng)進行的過程，一個工程進行的過程〕.通常我們把方案、施工過程、生產(chǎn)流程、程序流程等都當(dāng)成一個工程，一個大的工程常常被劃分成許多較小的子工程，通常我們把這些子工程稱為活動，當(dāng)這些活動完成時，整個工程也就完成了。58精選課件7.5.1AOV網(wǎng)而在各個活動之間,有些必須按規(guī)定的先后次序進行，有些那么沒有先后次序要求.那么，工程中的這種各個活動之間的次序要求,可以用一個有向圖來表示：圖中每個頂點代表一個活動.如果從頂點vi到頂點vj之間存在有向邊<vi,vj>，那么表示活動vi必須先于活動vj進行.這種用頂點表示活動,用有向邊〔弧〕表示頂點間優(yōu)先關(guān)系的有向圖稱為AOV網(wǎng).比方教學(xué)方案的制定.

59精選課件7.5.1AOV網(wǎng)C7C1C2C4C9C12C11C10C6C8C5C3表示必修課程優(yōu)先關(guān)系的有向圖〔AOV網(wǎng)〕必修課程關(guān)系表課程編號課程名稱先決條件

C1

程序設(shè)計基礎(chǔ)無

C2離散數(shù)學(xué)C1C3數(shù)據(jù)結(jié)構(gòu)C1

，C2C4匯編語言C1C5語言的設(shè)計與分析C3，C4C6計算機原理C11C7編譯原理C3，C5C8操作系統(tǒng)C3，C6C9高等數(shù)學(xué)無

C10線性代數(shù)C9C11普通物理C9C12數(shù)值分析C9，C10，C160精選課件7.5.1AOV網(wǎng)AOV網(wǎng)的特點:在AOV網(wǎng)中一定不能有回路。在AOV-網(wǎng)中如果出現(xiàn)了有向環(huán)，那么意味著某項活動應(yīng)以自己的完成作為先決條件，這是不合理的，工程將無法進行。因此，對給定的有向圖，判斷它是否是一個AOV-網(wǎng)，應(yīng)先判斷有向圖中是否存在環(huán)路。檢測有向圖中是否存在有向環(huán),可用拓撲排序的方法即對AOV-網(wǎng)構(gòu)造其頂點的拓撲有序序列，假設(shè)網(wǎng)中所有頂點都在它的拓撲有序序列中，那么AOV-網(wǎng)中必定無環(huán)，否那么，AOV-網(wǎng)中一定存在環(huán)路。61精選課件7.5.1AOV網(wǎng)拓撲排序：1.在有向圖中選一個沒有前驅(qū)的頂點〔即入度為0的頂點〕且輸出之。2.從圖中刪除該頂點和所有從它發(fā)出的邊。重復(fù)上述兩步，直到全部頂點均已輸出或當(dāng)前圖中不存在無前驅(qū)的頂點為止。假設(shè)所有頂點均已輸出，那么說明有向圖中無有向環(huán)，得到的頂點輸出序列即為拓撲序列；否那么說明未輸出的頂點構(gòu)成了有向環(huán)。62精選課件7.5.1AOV網(wǎng)C7C1C2C4C9C12C11C10C6C8C5C3舉例：拓撲序列為：C1C4C2C3C5C7C9C11C6C10C12C863精選課件7.5.2關(guān)鍵路徑與AOV網(wǎng)相對應(yīng)的是AOE網(wǎng)(ActivityOnEdgenetwork)，AOE網(wǎng)即邊表示活動的網(wǎng)絡(luò)。AOE網(wǎng)是一個有向帶權(quán)圖，圖中的：

邊：表示活動(子工程)，

邊上的權(quán)：表示該活動的持續(xù)時間，即完成該活動所需要的時間； 頂點：表示事件，每個事件是活動與活動之間的轉(zhuǎn)接點，即表示在它之前的所有活動已經(jīng)完成，在它之后的活動可以開始。AOE網(wǎng)的作用：它通常用來表示一個工程的方案或進度，可用來估算工程的完成時間。64精選課件7.5.2關(guān)鍵路徑V1V2V3V4V5V6V7V8V9a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4有9個事件、11個活動的AOE-網(wǎng)舉例：工程的開始點〔源點〕工程的完成點〔終點〕65精選課件7.5.2關(guān)鍵路徑關(guān)鍵路徑：路徑長度最長的路徑。關(guān)鍵活動：關(guān)鍵路徑上的活動。求工程的最短工期：在AOE網(wǎng)上求一條關(guān)鍵路徑的長度。

問題：

1.完成此工程最短需要多長時間？

2.影響此工程進度的活動是哪些？

3.如何加快工程進度、縮短工程完成時間？——源點到終點的最長路徑的長度——最長路徑上的所有活動——縮短最長路徑長度66精選課件7.5.2關(guān)鍵路徑設(shè)源點是v1,定義：事件vi的最早發(fā)生時間ve(i)：事件vi最早可以發(fā)生的時間，即從v1到vi的最長路徑長度。事件vi的最遲發(fā)生時間vl(i)

：在不影響整個工程進度的前提下事件vi最遲必須發(fā)生的時間?；顒觓k=<vi,vj>的最早開始時間ee(k)

：等于事件vi的最早發(fā)生時間ve(i)。活動ak=<vi,vj>的最遲開始時間el(k)

：在不影響整個工程進度的前提下，活動ak最遲必須開始的時間，等于事件vj的最遲發(fā)生時間vl(j)減去活動ak的持續(xù)時間dut(<i,j>)。關(guān)鍵活動ak=<vi,vj>

即為ee(k)=el(k)的活動。67精選課件7.5.2關(guān)鍵路徑ve(1)=0ve(j)=max{ve(i)+dut(<i,j>)}j=2,3,…,n按拓撲有序求ve(j){vl(n)=ve(n)vl(i)=min{vl(j)-dut(<i,j>)}j=n-1,n-2,…,1按拓撲有序求vl(i){ee(k)=ve(i)el(k)=vl(j)-dut(<i,j>)其中活動ak=<vi，vj>{<i,j>∈E<i,j>∈E68精選課件7.5.2關(guān)鍵路徑頂點Ive(i)vl(i)V1

v2

v3

v4

v5

v6v7v8

v9

0645771614180668710161418活動kdut(k)ee(k)el(k)el(k)-ee(k)

a1

a2

a3

a4

a5

a6

a7

a8

a9

a10

a11

645112974240006457771614023668771016140230230030069精選課件7.5.2關(guān)鍵路徑V1V2V3V4V5V6V7V8V9a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=42條關(guān)鍵路徑V1V2V5V7V8V9a1=6a4=1a7=9a8=7a10=2a11=4關(guān)鍵路徑長度均為18，關(guān)鍵活動為：a1a4a7a8a10a1170精選課件7.5.2關(guān)鍵路徑由此可見，用AOE網(wǎng)來估算某些工程完成的時間是非常有用的。要想加快整個工程的完成速度，縮短整個工期，只有提高關(guān)鍵活動的速度才有效。另外，假設(shè)網(wǎng)中有幾條關(guān)鍵路徑，那么只提高一條關(guān)鍵路徑上的關(guān)鍵活動的速度還不能導(dǎo)致整個工程縮短工期，而必須提高同時在幾條關(guān)鍵路徑上的活動的速度。注意：關(guān)鍵活動的速度提高是有限度的。71精選課件7.5.2關(guān)鍵路徑練習(xí)題：求以下圖所示的AOE網(wǎng)的所有關(guān)鍵路徑。有10個事件、14個活動的AOE-網(wǎng)V1V2V3V4V5V7V8V9V10a1=3a2=5a3=1a4=2a5=3a7=7a8=4a11=8a12=8a13=5V6a14=2a9=7a10=9a6=172精選課件7.6最短路徑在復(fù)雜的交通網(wǎng)絡(luò)中，人們常常會提出這樣的問題：從A地到B地之間是否有道路相通?在有多條通路的情況下，哪一條道路長度最短〔最省時、最省錢〕等?解決這類問題也就是在帶權(quán)圖中求最短路徑的問題。交通網(wǎng)絡(luò)可用帶權(quán)圖來表示。圖中的頂點表示城市，邊表示兩個城市之間有路相通，邊上的權(quán)值可表示兩個城市之間的距離〔或交通費用或途中所花費的時間等〕。那么，求兩個頂點之間的最短路徑，是指在連接兩個頂點的所有路徑中，選擇一條路徑上各邊權(quán)值之和最小的路徑。最短路徑的問題常見兩種:從某源點到其余各頂點之間的最短路徑(要求)

每一對頂點之間的最短路徑(不要求)73精選課件7.6.1單源點最短路徑——求從某個源點到其余各個頂點的最短路徑例1：如有向帶權(quán)圖G源點終點最短路徑長度v0v1∞v0v2〔v0v2)10v0v3〔v0v4v3〕50v0v4〔v0v4〕30v0v5〔v0v4v3v5〕60v0v5v1v2v4v33010205051010060有向帶權(quán)圖G74精選課件7.6.1單源點最短路徑 v0v1v2v3v4v5012345v00 ∞∞10∞30100v11 ∞∞∞∞∞∞v22 ∞5∞50∞∞v33 ∞∞∞∞∞10v44 ∞∞∞20∞60v55 ∞∞∞∞∞∞圖G的領(lǐng)接矩陣存儲結(jié)構(gòu)A[6][6]有向帶權(quán)圖G圖G以及它的領(lǐng)接矩陣的存儲結(jié)構(gòu)如下所示：v0v5v1v2v4v3301020505101006075精選課件7.6.1單源點最短路徑迪杰斯特拉〔Dijkstra〕算法算法的核心思想：按最短路徑長度遞增的次序依次求出各條最短路徑。為了描述算法步驟，需要引入幾個輔助向量：D[i]：表示當(dāng)前所找到的從源點V0出發(fā)到終點Vi的最短路徑的長度；初始狀態(tài)D[i]=A[0][i]S：為已經(jīng)求出了最短路徑的頂點組成的集合；初始狀態(tài)為S={V0}；P[i]：記錄當(dāng)前所找到的從源點出發(fā)只經(jīng)過S中的頂點到達Vi的最短路徑中Vi的前驅(qū)頂點；那么當(dāng)S中包含了圖中所有頂點時，D[i]即為最終找到的從源點出發(fā)到達Vi的最短路徑長度，P[i]即為最終找到的從源點出發(fā)到達Vi的最短路徑中Vi的前驅(qū)頂點。76精選課件7.6.1單源點最短路徑分析：顯然，長度最短的一條最短路徑就是長度為：D[j]=min{D[i]|Vi∈V}的路徑。此路徑是：〔V0，Vj〕那么下一條長度次短的最短路徑是哪一條呢？假設(shè)該次短路徑的終點是Vk，那么可想而知，這條路徑或者是〔V0，Vk〕或者是〔V0，Vj，Vk〕。即它的長度或者是從V0到Vk的弧上的權(quán)值，或者是D[j]加上從Vj到Vk的弧上的權(quán)值之和。那么，長度倒數(shù)第三短的最短路徑是？依次下去，一般情況下下一條最短路徑是？77精選課件7.6.1單源點最短路徑S集合是已經(jīng)求得了最短路徑的終點的集合，那么一般情況下，可以證明：下一條長度次短的最短路徑〔設(shè)其終點是Vx)或者是〔V0，Vx〕，或者是中間只經(jīng)過S中的頂點而最后到達頂點Vx的路徑。反證法證明：假設(shè)下一條要找的長度次短的最短路徑上有一個頂點不在S中，那么說明存在一條終點不在S中，而路徑長度比此路徑長度更短的路徑。但這是不可能的。因為我們是按最短路徑長度遞增的次序來產(chǎn)生各條最短路徑的，故長度比此路徑更短的所有最短路徑都已經(jīng)產(chǎn)生，它們的終點必定在S中，即假設(shè)不成立！78精選課件7.6.1單源點最短路徑因此，一般情況下：下一條長度次短的最短路徑〔設(shè)其終點是Vx)，或者是〔V0，Vx〕，或者是中間只經(jīng)過S中的頂點而最后到達頂點Vx的路徑。那么下一條長度次短的最短路徑的長度或者是弧(V0，Vx)上的權(quán)值A(chǔ)[0][x];或者是D[k](Vk∈S)加上弧(Vk,Vx)的權(quán)值:D[k]＋A[k][x](Vk∈S,Vx∈V-S)。即下一條長度次短的最短路徑的長度一定是D[j]=min{D[i]|Vi∈V－S}，其中，{A[0][i]D[k]＋A[k][i]〔Vk∈S,Vi∈V-S〕D[i]=

79精選課件7.6.1單源點最短路徑求解過程(重點〕:源點終點D[i]從V0到各終點的最短路徑D[i]的值和最短路徑i=1i=2i=3i=4i=5V0V1D[1]V2D[2]V3D[3]V4D[4]V5D[5]S{v0}10(v0,v2)∞∞30(v0,v4)100(v0,v5)∞∞∞∞60(v0,v2,v3)50(v0,v4,v3)30(v0,v4)100(v0,v5)90(v0,v4,v5)60(v0,v4,v3,v5){v0,v2}{v0,v2,v4}{v0,v2,v3,v4}{v0,v2,v3,v4,v5}S＝V

80精選課件7.6.1單源點最短路徑

初始狀態(tài)：

S={V0}D[i]=A[0][i]

P[i]=i=1,2,…,n{0A[0][i]<∞時-1A[0][i]=∞時

取min{D[i]}=D[j]

S=S+{Vj}

P[i]=

D[i]=min{D[i],D[j]+A[j][i]}i∈V-S{jD[i]>D[j]+A[j][i]時P[i]D[i]≤D[j]+A[j][i]時i∈V-S重復(fù)以下過程n-1次：81精選課件7.6.1單源點最短路徑Dijkstra算