數(shù)據(jù)結(jié)構(gòu)(C描述)電子教案第7章.ppt

第7章 圖,數(shù)據(jù)結(jié)構(gòu)（C+描述）,目錄,7.6拓?fù)渑判?7.1 圖的基本概念,7.2 圖的存貯結(jié)構(gòu),7.3 圖的遍歷,7.4 生成樹和最小生成樹,7.5最短路徑,退出,7.1 圖的基本概念,7.1.1 圖的定義,圖是由頂點(diǎn)集V和頂點(diǎn)間的關(guān)系集合E（邊的集合）組成的一種數(shù)據(jù)結(jié)構(gòu)，可以用二元組定義為：G=（V,E）。,例如，對于圖7-1所示的無向圖G1和有向圖G2，它們的數(shù)據(jù)結(jié)構(gòu)可以描述為：G1=(V1,E1), 其中 V1=a,b,c,d,E1=(a,b),(a,c),(a,d),(b,d),(c,d),而G2=(V2,E2)，其中V2=1,2,3, E2=,。,7.1.2 圖的基本術(shù)語,1. 有向圖和無向圖,在圖中，若用箭頭標(biāo)明了邊是有方向性的，則稱這樣的圖為有向圖，否則稱為無向圖。如圖7-1中，G1為無向圖，G2為有向圖。 在無向圖中，一條邊（x,y）與（y,x）表示的結(jié)果相同，用圓括號表示，在有向圖中，一條邊與表示的結(jié)果不相同，故用尖括號表示。x,y表示從頂點(diǎn)x發(fā)向頂點(diǎn)y的邊，x為始點(diǎn)，y為終點(diǎn)。有向邊也稱為弧，x為弧尾，y為弧頭,則x,y表示為一條弧,而y,x表示y為弧尾，x為弧頭的另一條弧 。,2. 完全圖、稠密圖、稀疏圖,具有n個頂點(diǎn)，n(n-1)/2條邊的圖，稱為完全無向圖，具有n個頂點(diǎn)，n(n-1) 條弧的有向圖,稱為完全有向圖。完全無向圖和完全有向圖都稱為完全圖。,對于一般無向圖，頂點(diǎn)數(shù)為n，邊數(shù)為e，則 0e n(n-1)/2。 對于一般有向圖，頂點(diǎn)數(shù)為n，弧數(shù)為e， 則 0en(n-1) 。 當(dāng)一個圖接近完全圖時，則稱它為稠密圖，相反地，當(dāng)一個圖中含有較少的邊或弧時，則稱它為稀疏圖。,3. 度、入度、出度,在圖中，一個頂點(diǎn)依附的邊或弧的數(shù)目，稱為該頂點(diǎn)的度。在有向圖中，一個頂點(diǎn)依附的弧頭數(shù)目，稱為該頂點(diǎn)的入度。一個頂點(diǎn)依附的弧尾數(shù)目，稱為該頂點(diǎn)的出度，某個頂點(diǎn)的入度和出度之和稱為該頂點(diǎn)的度。,另外，若圖中有n個頂點(diǎn)，e條邊或弧，第i個頂點(diǎn)的度為di，則有e=,4. 子圖,若有兩個圖G1和G2， G1=(V1,E1)， G2=(V2,E2)， 滿足如下條件： V2V1 ，E2 E1，即V2為V1的子集，E2為E1的子集，稱圖G2為圖G1的子圖。,圖和子圖的示例具體見圖7-2。,5 權(quán),在圖的邊或弧中給出相關(guān)的數(shù)，稱為權(quán)。 權(quán)可以代表一個頂點(diǎn)到另一個頂點(diǎn)的距離，耗費(fèi)等，帶權(quán)圖一般稱為網(wǎng)。,帶權(quán)圖的示例具體見圖7-3。,6 連通圖和強(qiáng)連通圖,在無向圖中，若從頂點(diǎn)i到頂點(diǎn)j有路徑，則稱頂點(diǎn)i和頂點(diǎn)j是連通的。若任意兩個頂點(diǎn)都是連通的，則稱此無向圖為連通圖，否則稱為非連通圖。,連通圖和非連通圖示例見圖7-4。,在有向圖中，若從頂點(diǎn)i到頂點(diǎn)j有路徑，則稱從頂點(diǎn)i和頂點(diǎn)j是連通的，若圖中任意兩個頂點(diǎn)都是連通的，則稱此有向圖為強(qiáng)連通圖，否則稱為非強(qiáng)連通圖。,強(qiáng)連通圖和非強(qiáng)連通圖示例見圖7-5。,7 連通分量和強(qiáng)連通分量,無向圖中，極大的連通子圖為該圖的連通分量。顯然，任何連通圖的連通分量只有一個，即它本身，而非連通圖有多個連通分量。,對于圖7-4 中的非連通圖，它的連通分量見圖7-6。,有向圖中，極大的強(qiáng)連通子圖為該 圖的強(qiáng)連通分量。顯然，任何強(qiáng)連通圖的強(qiáng)連通分量只有一個，即它本身，而非強(qiáng)連通圖有多個強(qiáng)連通分量。,對于圖7-5 中的非強(qiáng)連通圖，它的強(qiáng)連通分量見圖7-7。,8路徑、回路,在無向圖G中，若存在一個頂點(diǎn)序列Vp ,Vi1，Vi2，Vin，Vq, 使得（Vp,Vi1）,(Vi1,Vi2),，(Vin,Vq)均屬于E（G），則稱頂點(diǎn)Vp到Vq存在一條路徑。若一條路徑上除起點(diǎn)和終點(diǎn)可以相同外，其余頂點(diǎn)均不相同，則稱此路徑為簡單路徑。起點(diǎn)和終點(diǎn)相同的路徑稱為回路，簡單路徑組成的回路稱為簡單回路。路徑上經(jīng)過的邊的數(shù)目稱為該路徑的路徑長度。,9 有根圖,在一個有向圖中，若從頂點(diǎn)V有路徑可以到達(dá)圖中的其它所有頂點(diǎn)，則稱此有向圖為有根圖，頂點(diǎn)V稱作圖的根。,10 生成樹、生成森林,連通圖的生成樹是一個極小連通子圖，它包含圖中全部n個頂點(diǎn)和n-1條不構(gòu)成回路的邊。非邊通圖的生成樹則組成一個生成森林。若圖中有n個頂點(diǎn)，m個連通分量，則生成森林中有n-m條邊。,7.2 圖的存貯結(jié)構(gòu),7.2.1 鄰接矩陣,1 圖的鄰接矩陣表示,在鄰接矩陣表示中，除了存放頂點(diǎn)本身信息外，還用一個矩陣表示各個頂點(diǎn)之間的關(guān)系。若（i,j）E(G)或i,jE(G),則矩陣中第i行 第j列元素值為1，否則為0 。,圖的鄰接矩陣定義為： 1 若（i,j）E(G)或i,jE(G) Aij= 0 其它情形,例如, 對圖7-8所示的無向圖和有向圖,它們的鄰接矩陣見圖7-9。,2 從無向圖的鄰接矩陣可以得出如下結(jié)論,（1）矩陣是對稱的; （2）第i行或第i 列1的個數(shù)為頂點(diǎn)i 的度; （3）矩陣中1的個數(shù)的一半為圖中邊的數(shù)目; （4）很容易判斷頂點(diǎn)i 和頂點(diǎn)j之間是否有邊相連(看矩陣中i行j列值是否為1)。,3 從有向圖的鄰接矩陣可以得出如下結(jié)論,（1） 矩陣不一定是對稱的; （2） 第i 行中1的個數(shù)為頂點(diǎn)i 的出度; （3） 第i列中1的個數(shù)為頂點(diǎn) i的入度; （4） 矩陣中1的個數(shù)為圖中弧的數(shù)目; （5） 很容易判斷頂點(diǎn)i 和頂點(diǎn)j 是否有弧相連.,4 網(wǎng)的鄰接矩陣表示,類似地可以定義網(wǎng)的鄰接矩陣為： wij 若（i,j）E(G)或i,jE(G) Aij= 0 若i=j 其它情形 網(wǎng)及網(wǎng)的鄰接矩陣見圖7-10。,5 圖的鄰接矩陣數(shù)據(jù)類型描述,圖的鄰接矩陣數(shù)據(jù)類型描述如下: const int n= maxn； / 圖中頂點(diǎn)數(shù) const int e=maxe ； / 圖中邊數(shù) struct graph elemtype Vn+1; / 存放頂點(diǎn)信息v1,v2,.vn，不使用v0存儲空間 int arcsn+1n+1 / 鄰接矩陣 ;,6 建立無向圖的鄰接矩陣,void creatadj(graph 該算法的時間復(fù)雜度為O（n2）。,7.建立有向圖的鄰接矩陣,void creatadj(graph 該算法的時間復(fù)雜度為O（n2）。,8.建立無向網(wǎng)的鄰接矩陣,void creatadj(graph 該算法的時間復(fù)雜度為O（n2）。,9.建立有向網(wǎng)的鄰接矩陣,void creatadj(graph 該算法的時間復(fù)雜度為O（n2）。,7.2.2 鄰接表,1 圖的鄰接表表示,將每個結(jié)點(diǎn)的邊用一個單鏈表鏈接起來，若干個結(jié)點(diǎn)可以得到若干個單鏈表，每個單鏈表都有一個頭結(jié)點(diǎn)，所有頭結(jié)點(diǎn)組成一個一維數(shù)組，稱這樣的鏈表為鄰接表。 例如，圖7-8所示的無向圖G3和有向圖G4的鄰接表見圖7-11所示,2 從無向圖的鄰接表可以得到如下結(jié)論,（1）第i 個鏈表中結(jié)點(diǎn)數(shù)目為頂點(diǎn)i的度； （2）所有鏈表中結(jié)點(diǎn)數(shù)目的一半為圖中邊數(shù)； （3）占用的存儲單元數(shù)目為n+2e 。,3 從有向圖的鄰接表可以得到如下結(jié)論,（1）第i 個鏈表中結(jié)點(diǎn)數(shù)目為頂點(diǎn)i的出度； （2）所有鏈表中結(jié)點(diǎn)數(shù)目為圖中弧數(shù)； （3）占用的存儲單元數(shù)目為n+e 。,從有向圖的鄰接表可知，不能求出頂點(diǎn)的入度。為此，我們必須另外建立有向圖的逆鄰接表，以便求出每一個頂點(diǎn)的入度。逆鄰接表在圖7-11(c)中已經(jīng)給出，從該圖中可知。有向圖的逆鄰接表與鄰接表類似，只是它是從入度考慮結(jié)點(diǎn)，而不是從出度考慮結(jié)點(diǎn)。,4 圖的鄰接表數(shù)據(jù)類型描述,圖的鄰接表數(shù)據(jù)類型描述如下： const int n =maxn； / maxn表示圖中最大頂點(diǎn)數(shù) const int e= maxe ； / maxe圖中最大邊數(shù) struct link /定義鏈表類型 elemtype data ; link *next ; struct node /定義鄰接表的表頭類型 elemtype v; /頂點(diǎn)信息 link *next; an+1;,5.無向圖的鄰接表建立,void creatlink( ) int i,j,k ; link *s ; for(i=1; iij ; /輸入一條邊 (i,j) s=new link; /申請一個動態(tài)存儲單元 sdata=j ; s-next=ai.next ;ai.next=s ; s=new link; s-data=i ; s-next=aj.next ;aj.next=s ;,該算法的時間復(fù)雜度為O（n+e）。,6.有向圖的鄰接表建立,void creatlink( ) int i,j,k ; link *s ; for(i=1; iij ; /輸入一條邊 s=new link; /申請一個動態(tài)存儲單元 sdata=j ;s-next=ai.next ; ai.next=s ; 該算法的時間復(fù)雜度為O（n+e）。,7.網(wǎng)的鄰接表的數(shù)據(jù)類型描述,網(wǎng)的鄰接表的數(shù)據(jù)類型可描述如下： const int n =maxn； / maxn表示網(wǎng)中最大頂點(diǎn)數(shù) const int e= maxe ； / maxe網(wǎng)中最大邊數(shù) struct link /定義鏈表類型 elemtype data ; float w; /定義網(wǎng)上的權(quán)值類型為浮點(diǎn)型 link *next ; struct node /定義鄰接表的表頭類型 elemtype v; /頂點(diǎn)信息 link *next; an+1;,8 無向網(wǎng)的鄰接表建立,void creatlink( ) float w; int i,j,k ; link *s ; for(i=1; iijw ; /輸入一條邊 (i,j)及該邊上的權(quán)值 s=new link; /申請一個動態(tài)存儲單元 sdata=j ;s-w=w; s-next=ai.next ;ai.next=s ;s=new link; s-data=i ;s-w=w;s-next=aj.next ; aj.next=s ; 該算法的時間復(fù)雜度為O（n+e）。,9 有向網(wǎng)的鄰接表建立,void creatlink( ) float w;int i,j,k ; link *s ; for(i=1; iijw ; /輸入一條弧 及該弧上的權(quán)值 s=new link; /申請一個動態(tài)存儲單元 sdata=j ;s-w=w; s-next=ai.next ; ai.next=s ; 該算法的時間復(fù)雜度為O（n+e）。,另外，請注意上面的算法中，建立的鄰接表不是唯一的,與你從鍵盤輸入邊的順序有關(guān)，輸入的邊的順序不同，則得到的鏈表也不同。,7.2.3 鄰接多重表,在無向圖的鄰接表中，每條邊（Vi,Vj）由兩個結(jié)點(diǎn)表示，一個結(jié)點(diǎn)在第i個鏈表中，另一個結(jié)點(diǎn)在第j個鏈表中，當(dāng)需要對邊進(jìn)行操作時，就需要找到表示同一條邊的兩個結(jié)點(diǎn)，這給操作帶來不便，在這種情況下采用鄰接多重表較方便。 在鄰接多重表中，每條邊用一個結(jié)點(diǎn)表示，每個結(jié)點(diǎn)由五個域組成，其結(jié)點(diǎn)結(jié)構(gòu)為 ：,其中mark為標(biāo)志域，用來標(biāo)記這條邊是否被訪問過，i和j域為一條邊的兩個頂點(diǎn)，next1 和next2為兩個指針域，分別指向依附于i頂點(diǎn)的下一條邊和j頂點(diǎn)的下一條邊。而表頭與鄰接表的表頭類似。 鄰接多重表的形式見圖7-12。,7.3 圖的遍歷,和樹的遍歷類似，圖的遍歷也是從某個頂點(diǎn)出發(fā)，沿著某條搜索路徑對圖中所有頂點(diǎn)各作一次訪問。若給定的圖是連通圖，則從圖中任一頂點(diǎn)出發(fā)順著邊可以訪問到該圖中所有的頂點(diǎn)，但是，在圖中有回路，從圖中某一頂點(diǎn)出發(fā)訪問圖中其它頂點(diǎn)時，可能又會回到出發(fā)點(diǎn)，而圖中可能還剩余有頂點(diǎn)沒有訪問到，因此，圖的遍歷較樹的遍歷更復(fù)雜。我們可以設(shè)置一個全局型標(biāo)志數(shù)組visited來標(biāo)志某個頂點(diǎn)是否被訪過，未訪問的值為0，訪問過的值為1。根據(jù)搜索路徑的方向不同，圖的遍歷有兩種方法：深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷。,7.3.1深度優(yōu)先搜索遍歷 1 深度優(yōu)先搜索思想,深度優(yōu)先搜索遍歷類似于樹的先序遍歷。假定給定圖G的初態(tài)是所有頂點(diǎn)均未被訪問過，在G中任選一個頂點(diǎn)i作為遍歷的初始點(diǎn)，則深度優(yōu)先搜索遍歷可定義如下： (1) 首先訪問頂點(diǎn)i，并將其訪問標(biāo)記置為訪問過，即visitedi=1； (2) 然后搜索與頂點(diǎn)i有邊相連的下一個頂點(diǎn)j，若j未被訪問過，則訪問它，并將j的訪問標(biāo)記置為訪問過，visitedj=1，然后從j開始重復(fù)此過程，若j已訪問，再看與i有邊相連的其它頂點(diǎn)； (3) 若與i有邊相連的頂點(diǎn)都被訪問過，則退回到前一個訪問頂點(diǎn)并重復(fù)剛才過程，直到圖中所有頂點(diǎn)都被訪問完止。,例如，對圖7-13所示無向圖G7，從頂點(diǎn)1出發(fā)的深度優(yōu)先搜索遍歷序列可有多種，下面僅給出三種，其它可作類似分析。 在無向圖G7中，從頂點(diǎn)1出發(fā)的深度優(yōu)先搜索遍歷序列舉三種為：,1, 2, 4, 8, 5, 6, 3, 7 1, 2, 5, 8, 4, 7, 3, 6 1, 3, 6, 8, 7, 4, 2, 5,2 連通圖的深度優(yōu)先搜索,若圖是連通的或強(qiáng)連通的，則從圖中某一個頂點(diǎn)出發(fā)可以訪問到圖中所有頂點(diǎn)，否則只能訪問到一部分頂點(diǎn)。 另外，從剛才寫出的遍歷結(jié)果可以看出，從某一個頂點(diǎn)出發(fā)的遍歷結(jié)果是不唯一的。但是,若我們給定圖的存貯結(jié)構(gòu),則從某一頂點(diǎn)出發(fā)的遍歷結(jié)果應(yīng)是唯一的。,(1) 用鄰接矩陣實現(xiàn)圖的深度優(yōu)先搜索 以圖7-13中無向圖G7 為例，來說明算法的實現(xiàn)，G7的鄰接矩陣見圖7-14。,算法描述為下面形式：,void dfs (int i) / 從頂點(diǎn)i 出發(fā)遍歷 int j; coutg.vi; /輸出訪問頂點(diǎn) visitedi=1; /全局?jǐn)?shù)組訪問標(biāo)記置1表示已經(jīng)訪問 for(j=1; j=n; j+) if (g.arcsi j= =1) ,用上述算法和無向圖G7，可以描述從頂點(diǎn)1出發(fā)的深度優(yōu)先搜索遍歷過程，示意圖見圖7-15，其中實線表示下一層遞歸調(diào)用，虛線表示遞歸調(diào)用的返回。 從圖7-15中，可以得到從頂點(diǎn)1的遍歷結(jié)果為 1, 2, 4, 8, 5, 6, 3, 7。同樣可以分析出從其它頂點(diǎn)出發(fā)的遍歷結(jié)果。,(2)用鄰接表實現(xiàn)圖的深度優(yōu)先搜索 仍以圖7-13中無向圖G7 為例，來說明算法的實現(xiàn)，G7的鄰接表見圖7-16，,算法描述為下面形式： void dfs1(int i) link *p; coutdata) dfs1(p-data);p=p-next; ,用剛才算法及圖7-16，可以描述從頂點(diǎn)7出發(fā)的深度優(yōu)先搜索遍歷示意圖，見圖7-17,其中實線表示下一層遞歸，虛線表示遞歸返回，箭頭旁邊數(shù)字表示調(diào)用的步驟。 于是，從頂點(diǎn)7出發(fā)的深度優(yōu)先搜索遍歷序列，從圖7-17中可得出為 7， 3， 1， 2， 4， 8， 5， 6。從其它頂點(diǎn)出發(fā)的深度優(yōu)先搜索序列，請讀者自已寫出。,3非連通圖的深度優(yōu)先搜索,若圖是非連通的或非強(qiáng)連通圖，則從圖中某一個頂點(diǎn)出發(fā)。不能用深度優(yōu)先搜索訪問到圖中所有頂點(diǎn)，而只能訪問到一個連通子圖（既連通分量）或只能訪問到一個強(qiáng)連通子圖（既強(qiáng)連通分量）。這時，可以在每個連通分量或每個強(qiáng)連通分量中都選一個頂點(diǎn)，進(jìn)行深度優(yōu)先搜索遍歷，最后將每個連通分量或每個強(qiáng)連通分量的遍歷結(jié)果合起來，則得到整個非連通圖的遍歷結(jié)果。 遍歷算法實現(xiàn)與連通圖的只有一點(diǎn)不同，即對所有頂點(diǎn)進(jìn)行循環(huán)，反復(fù)調(diào)用連通圖的深度優(yōu)先搜索遍歷算法即可。具體實現(xiàn)如下：,for(int i=1;i=n;i+) if(!visitedi) dfs(i) ;,for(int i=1;i=n;i+) if(!visitedi) dfs1(i);,或者,7.3.2 廣度優(yōu)先搜索遍歷 1 廣度優(yōu)先搜索的思想,廣度優(yōu)先搜索遍歷類似于樹的按層次遍歷。設(shè)圖G的初態(tài)是所有頂點(diǎn)均未訪問，在G 中任選一頂點(diǎn)i作為初始點(diǎn)，則廣度優(yōu)先搜索的基本思想是： (1) 首先訪問頂點(diǎn)i，并將其訪問標(biāo)志置為已被訪問，即visitedi=1； (2) 接著依次訪問與頂點(diǎn)i有邊相連的所有頂點(diǎn)W1，W2，Wt； (3) 然后再按順序訪問與W1，W2，Wt有邊相連又未曾訪問過的頂點(diǎn)； 依此類推，直到圖中所有頂點(diǎn)都被訪問完為止 。,例如，對圖7-13所示無向圖G7，從頂點(diǎn)1出發(fā)的廣度優(yōu)先搜索遍歷序列可有多種，下面僅給出三種，其它可作類似分析。,在無向圖G7中，從頂點(diǎn)1出發(fā)的廣度優(yōu)先搜索遍歷序列舉三種為： 1, 2, 3, 4, 5, 6, 7, 8 1, 3, 2, 7, 6, 5, 4, 8 1, 2, 3, 5, 4, 7, 6, 8,2 連通圖的廣度優(yōu)先搜索,(1) 用鄰接矩陣實現(xiàn)圖的廣度優(yōu)先搜索遍歷 仍以圖7-13中無向圖G7及7-14所示的鄰接矩陣來說明對無向圖G7的遍歷過程,根據(jù)該算法用及圖7-14中的鄰接矩陣，可以得到圖7-13的無向圖G7 的廣度優(yōu)先搜索序列，若從頂點(diǎn)1 出發(fā)，廣度優(yōu)先搜索序列為：1，2，3， 4，5， 6，7，8。若從頂點(diǎn)3出發(fā)，廣度優(yōu)先搜索序列為：3， 1， 6， 7， 2， 8， 4， 5,從其它點(diǎn)出發(fā)的廣度優(yōu)先搜索序列可根據(jù)同樣類似方法分析。,算法描述如下： void bfs( int i) /從頂點(diǎn)i出發(fā)遍歷 int Qn+1 ; /Q為隊列 int f,r,j ; / f,r分別為隊列頭，尾指針 f=r=0 ; /設(shè)置空隊列 coutg.vi ; / 輸出訪問頂點(diǎn) visitedi=1 ; /全局?jǐn)?shù)組標(biāo)記置1表示已經(jīng)訪問 r+; qr=i ; /入隊列 while (fr) f+; i=qf ; /出隊列 for (j=1; j=n; j+) if (g.arcsij=1) ,（2）用鄰接表實現(xiàn)圖的廣序優(yōu)先搜索遍歷 仍以無向圖G7及圖7-16所示鄰接表來說明鄰接表上實現(xiàn)廣度優(yōu)先搜索遍歷的過程,根據(jù)該算法及圖7-16，可以得到圖G7的廣度優(yōu)先搜索序列，若從頂點(diǎn)1出發(fā)，廣度優(yōu)先搜索序列為：1，2，3，4，5，6，7，8，若從頂點(diǎn)7出發(fā)，廣度優(yōu)先搜索序列為：7，3，8，1，6，4，5，2，從其它頂點(diǎn)出發(fā)的廣度優(yōu)先搜索序列可根據(jù)同樣類似方法分析。,算法描述如下： void BFS1(int i) int qn+1 ; /定義隊列 int f,r ; link *p ; /P為搜索指針 f=r=0 ; coutdata) coutdata.v; visitedp-data=1 ; r+;qr=p-data ; p=p-next; ,3.非連通圖的廣度優(yōu)先搜索,若圖是非連通的或非強(qiáng)連通圖，則從圖中某一個頂點(diǎn)出發(fā)。不能用廣度優(yōu)先搜索遍歷訪問到圖中所有頂點(diǎn)，而只能訪問到一個連通子圖（既連通分量）或只能訪問到一個強(qiáng)連通子圖（既強(qiáng)連通分量）。這時，可以在每個連通分量或每個強(qiáng)連通分量中都選一個頂點(diǎn)，進(jìn)行廣度優(yōu)先搜索遍歷，最后將每個連通分量或每個強(qiáng)連通分量的遍歷結(jié)果合起來，則得到整個非連通圖或非強(qiáng)連通圖的廣度優(yōu)先搜索遍歷序列。 遍歷算法實現(xiàn)與連通圖的只有一點(diǎn)不同，即對所有頂點(diǎn)進(jìn)行循環(huán)，反復(fù)調(diào)用連通圖的廣度優(yōu)先搜索遍歷算法即可。具體可以表示如下：,for(int i=1;i=n;i+) for(int i=1;i=n;i+) if(!visitedi) 或 if(!visitedi) bfs(i) ; bfs1(i);,7.4 生成樹和最小生成樹,7.4.1 基本概念 1 生成樹,在圖論中，常常將樹定義為一個無回路連通圖。例如，圖7-18中的兩個圖就是無回路的連通圖。乍一看它似乎不是不是樹，但只要選定某個頂點(diǎn)做根并以樹根為起點(diǎn)對每條邊定向，就可以將它們變?yōu)橥ǔ５臉洹?在一個連通圖中，有n個頂點(diǎn)，若存在這樣一個子圖，含有n個頂點(diǎn)，n-1條不構(gòu)成回路的邊，則這個子圖稱為生成樹，或者定義為：一個連通圖G的子圖如果是一棵包含G的所有頂點(diǎn)的樹，則該子圖為圖G 的生成樹。,由于n個頂點(diǎn)的連通圖至少有n-1條邊，而所有包含n-1 條邊及n個頂點(diǎn)的連通圖都是無回路的樹，所以生成樹是連通圖中的極小連通子圖，所謂極小是指邊數(shù)最少，若在生成樹中去掉任何一條邊，都會使之變?yōu)榉沁B通圖，若在生成樹上任意增加一條邊，就會構(gòu)成回路。那么，對給定的連通圖，如何求得它的生成樹呢？回到我們前面提到的圖的遍歷，訪問過圖中一個頂點(diǎn)后，要訪問下一個頂點(diǎn)， 一般要求兩個頂點(diǎn)有邊相連，即必須經(jīng)過圖中的一條邊，要遍歷圖中n 個頂點(diǎn)且每個頂點(diǎn)都只遍歷一次，則必須經(jīng)過圖中的n-1條邊，這n-1條邊構(gòu)成連通圖的一個極小連通子圖，所以它是連通圖的生成樹，由于遍歷結(jié)果可能不唯一，所以得到的生成樹也是不唯 一的。,要求得生成樹，可考慮用剛才講過的深度優(yōu)先搜索遍歷算法及廣度優(yōu)先搜索遍歷算法。對于深度優(yōu)先搜索算法DFS或DFS1，由DFS（i）遞歸到DFS（j），中間必經(jīng)過一條邊（i,j），因此，只需在DFS(j)調(diào)用前輸出這條邊或保存這條邊，即可求得生成樹的一條邊，整個遞歸完成后，則可求得生成樹的所有邊。對于廣度優(yōu)先搜索算法BFS或BFS1，若i 出隊， j 入隊，則(i,j)為一條樹邊。因此，可以在算法的if 語句中輸出這條邊，算法完成后，將會輸出n-1條邊，也可求得生成樹。由深度優(yōu)先搜索遍歷得到的生成樹，稱為深度優(yōu)先生成樹，由廣度優(yōu)先搜索遍歷得到的生成樹，稱為廣度優(yōu)先生成樹。圖7-13中無向圖G7的兩種生成樹見 圖7-19。,若一個圖是強(qiáng)連通的有向圖，同樣可以得到它的生成樹。生成樹可以利用連通圖的深度優(yōu)先搜索遍歷或連通圖的廣度優(yōu)先搜索遍歷算法得到。,2生成森林,若一個圖是非連通圖或非強(qiáng)連通圖，但有若干個連通分量或若干個強(qiáng)連通分量，則通過深度優(yōu)先搜索遍歷或廣度優(yōu)先搜索遍歷，不可以得到生成樹，但可以得到生成森林，且若非連通圖有 n 個頂點(diǎn)，m 個連通分量或強(qiáng)連通分量，則可以遍歷得到m棵生成樹，合起來為生成森林，森林中包含n-m條樹邊。,生成森林可以利用非連通圖的深度優(yōu)先搜索遍歷或非連通圖的廣度優(yōu)先搜索遍歷算法得到。,3 最小生成樹,在一般情況下，圖中的每條邊若給定了權(quán)，這時，我們所關(guān)心的不是生成樹，而是生成樹中邊上權(quán)值之和。若生成樹中每條邊上權(quán)值之和達(dá)到最小，稱為最小生成樹。 下面將介紹求最小生成樹的兩種方法：普里姆算法和克魯斯卡爾算法。,7.4.2 普里姆算法,1 普里姆(prim)算法思想,下面僅討論無向網(wǎng)的最小生成樹問題。 普里姆方法的思想是：在圖中任取一個頂點(diǎn)K作為開始點(diǎn)，令U=k，W=V-U，其中V為圖中所有頂點(diǎn)集，然后找一個頂點(diǎn)在U中，另一個頂點(diǎn)在W中的邊中最短的一條，找到后，將該邊作為最小生成樹的樹邊保存起來，并將該邊頂點(diǎn)全部加入U集合中，并從W中刪去這些頂點(diǎn)，然后重新調(diào)整U中頂點(diǎn)到W中頂點(diǎn)的距離, 使之保持最小，再重復(fù)此過程，直到W為空集止。求解過程參見圖7-20 。,假設(shè)開始頂點(diǎn)就選為頂點(diǎn)1，故首先有U=1，W=2，3，4，5，6,7.4.3 克魯斯卡爾（kruskal）算法 1 克魯斯卡爾算法基本思想,克魯斯卡爾算法的基本思想是：將圖中所有邊按權(quán)值遞增順序排列，依次選定取權(quán)值較小的邊，但要求后面選取的邊不能與前面選取的邊構(gòu)成回路，若構(gòu)成回路，則放棄該條邊，再去選后面權(quán)值較大的邊，n個頂點(diǎn)的圖中，選夠n-1條邊即可。,例如，對圖7-20（a） 中無向網(wǎng)，用克魯斯卡爾算法求最小生成樹的過程見圖7-22。,7.5最短路徑,交通網(wǎng)絡(luò)中常常提出這樣的問題：從甲地到乙地之間是否有公路連通?在有多條通路的情況下，哪一條路最短? 交通網(wǎng)絡(luò)可用帶權(quán)圖來表示。頂點(diǎn)表示城市名稱，邊表示兩個城市有路連通，邊上權(quán)值可表示兩城市之間的距離、交通費(fèi)或途中所花費(fèi)的時間等。求兩個頂點(diǎn)之間的最短路徑，不是指路徑上邊數(shù)之和最少，而是指路徑上各邊的權(quán)值之和最小。 另外，若兩個頂點(diǎn)之間沒有邊，則認(rèn)為兩個頂點(diǎn)無通路，但有可能有間接通路(從其它頂點(diǎn)達(dá)到)。路徑上的開始頂點(diǎn)(出發(fā)點(diǎn))稱為源點(diǎn)，路徑上的最后一個頂點(diǎn)稱為終點(diǎn)，并假定討論的權(quán)值不能為負(fù)數(shù)。,7.5.1單源點(diǎn)最短路徑 1 單源點(diǎn)最短路徑,單源點(diǎn)最短路徑是指：給定一個出發(fā)點(diǎn)(單源點(diǎn))和一個有向網(wǎng)G=(V，E),求出源點(diǎn)到其它各頂點(diǎn)之間的最短路徑。,那么怎樣求出單源點(diǎn)的最短路徑呢?我們可以將源點(diǎn)到終點(diǎn)的所有路徑都列出來,然后在里面選最短的一條即可。但是這樣做,用手工方式可以,當(dāng)路徑特別多時,顯得特別麻煩,并且沒有什么規(guī)律,不能用計算機(jī)算法實現(xiàn)。,迪杰斯特拉(Dijkstra)在做了大量觀察后,首先提出了按路長度遞增序產(chǎn)生各頂點(diǎn)的最短路徑算法,我們稱之為迪杰斯特拉算法。,2 迪杰斯特拉算法的基本思想,算法的基本思想是:設(shè)置并逐步擴(kuò)充一個集合S，存放已求出其最短路徑的頂點(diǎn)，則尚未確定最短路徑的頂點(diǎn)集合是V-S，其中V為網(wǎng)中所有頂點(diǎn)集合。按最短路徑長度遞增的順序逐個以V-S中的頂點(diǎn)加到S中，直到S中包含全部頂點(diǎn)，而V-S為空。,具體做法是:設(shè)源點(diǎn)為Vl,則S中只包含頂點(diǎn)Vl，令W=V-S，則W中包含除Vl外圖中所有頂點(diǎn)，Vl對應(yīng)的距離值為0，W中頂點(diǎn)對應(yīng)的距離值是這樣規(guī)定的：若圖中有弧則Vj頂點(diǎn)的距離為此弧權(quán)值，否則為(一個很大的數(shù))，然后每次從W中的頂點(diǎn)中選一個其距離值為最小的頂點(diǎn)Vm加入到S中，每往S中加入一個頂點(diǎn)Vm，就要對W中的各個頂點(diǎn)的距離值進(jìn)行一次修改。若加進(jìn)Vm做中間頂點(diǎn)，使+的值小于值，則用+代替原來Vj的距離，修改后再在W中選距離值最小的頂點(diǎn)加入到S中，如此進(jìn)行下去，直到S中包含了圖中所有頂點(diǎn)為止,迪杰斯特拉算法的求解過程,7.5.2所有頂點(diǎn)對之間的最短路徑,1 頂點(diǎn)對之間的最短路徑概念,所有頂點(diǎn)對之間的最短路徑是指：對于給定的有向網(wǎng)G=(V,E),要對G中任意一對頂點(diǎn)有序?qū)、W(VW),找出V到W的最短距離和W到V的最短距離。 解決此問題的一個有效方法是:輪流以每一個頂點(diǎn)為源點(diǎn),重復(fù)執(zhí)行迪杰斯特拉算法n次,即可求得每一對頂點(diǎn)之間的最短路徑,總的時間復(fù)雜度為O(n3)。,下面將介紹用弗洛伊德(Floyd)算法來實現(xiàn)此功能,時間復(fù)雜度仍為O(n3),但該方法比調(diào)用n次迪杰斯特拉方法更直觀一些。,2 弗洛伊德算法的基本思想,弗洛伊德算法仍然使用前面定義的圖的鄰接矩陣arcsn+1n+1來存儲帶權(quán)有向圖。算法的基本思想是:設(shè)置一個nxn的矩陣A(k)，其中除對角線的元素都等于0外，其它元素a(k)ij表示頂點(diǎn)i到頂點(diǎn)j的路徑長度，K表示運(yùn)算步驟。開始時，以任意兩個頂點(diǎn)之間的有向邊的權(quán)值作為路徑長度，沒有有向邊時，路徑長度為，當(dāng)K=O時,A (0)ij=arcsij,以后逐步嘗試在原路徑中加入其它頂點(diǎn)作為中間頂點(diǎn)，如果增加中間頂點(diǎn)后，得到的路徑比原來的路徑長度減少了，則以此新路徑代替原路徑，修改矩陣元素。具體做法為： 第一步，讓所有邊上加入中間頂點(diǎn)1，取Aij與Ai1+A1j中較小的值作Aij的值，完成后得到A(1)，,因此，弗洛伊德算法可以描述為: A(0)ij=arcsij; /arcs為圖的鄰接矩陣 A(k)ij=minA(k-1) ij,A(k-1) ik+A(k-1) kj 其中 k=1,2,n,第二步，讓所有邊上加入中間頂點(diǎn)2，取Aij與Ai2+A2j中較小的值，完成后得到A(2)，如此進(jìn)行下去，當(dāng)?shù)趎步完成后，得到A(n)，A(n)即為我們所求結(jié)果,A(n)ij表示頂點(diǎn)i到頂點(diǎn)j的最短距離。,3 弗洛伊德算法實現(xiàn),在用弗洛伊德算法求最短路徑時,為方便求出中間經(jīng)過的路徑,增設(shè)一個輔助二維數(shù)組pathn+1n+1，其中pathij是相應(yīng)路徑上頂點(diǎn)j的前一頂點(diǎn)的頂點(diǎn)號。 算法描述如下：,Void floyd ( const int n) for (int i=1;i=n;i+) for (int j=1;j=n; j+)