1、第七章 圖,圖（Graph）是一種較線性表和樹更為復(fù)雜的非線性結(jié)構(gòu)。在線性結(jié)構(gòu)中，結(jié)點(diǎn)之間的關(guān)系是線性關(guān)系，除開始結(jié)點(diǎn)和終端結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)只有一個(gè)直接前趨和直接后繼。在樹形結(jié)構(gòu)中，結(jié)點(diǎn)之間的關(guān)系實(shí)質(zhì)上是層次關(guān)系，同層上的每個(gè)結(jié)點(diǎn)可以和下一層的零個(gè)或多個(gè)結(jié)點(diǎn)（即孩子）相關(guān)，但只能和上一層的一個(gè)結(jié)點(diǎn)（即雙親）相關(guān)（根結(jié)點(diǎn)除外）。然而在圖結(jié)構(gòu)中，對結(jié)點(diǎn)（圖中常稱為頂點(diǎn)）的前趨和后繼個(gè)數(shù)都是不加限制的，即結(jié)點(diǎn)之間的關(guān)系是任意的。圖中任意兩個(gè)結(jié)點(diǎn)之間都可能相關(guān)。由此，圖的應(yīng)用極為廣泛，特別是近年來的迅速發(fā)展，已滲透到諸如語言學(xué)、邏輯學(xué)、物理、化學(xué)、電訊工程、計(jì)算機(jī)科學(xué)以及數(shù)學(xué)的其它分支中。,7.1 圖

2、的定義和術(shù)語 圖(Graph)圖G是由兩個(gè)集合V(G)和E(G)組成的,記為G=(V,E) 其中：V(G)是頂點(diǎn)的非空有限集 E(G)是邊的有限集合，邊是頂點(diǎn)的無序?qū)蛴行驅(qū)?有向圖有向圖G是由兩個(gè)集合V(G)和E(G)組成的 其中：V(G)是頂點(diǎn)的非空有限集 E(G)是有向邊（也稱弧）的有限集合，弧是頂點(diǎn)的有序?qū)Γ洖?，v,w是頂點(diǎn)，v為弧尾，w為弧頭,V(G1)= 1, 2, 3, 4, 5, 6 E(G1)=, , , , , , ,無向圖無向圖G是由兩個(gè)集合V(G)和E(G)組成的 其中：V(G)是頂點(diǎn)的非空有限集 E(G)是邊的有限集合，邊是頂點(diǎn)的無序?qū)?，記為（v,w）或（w,v)，

3、并且（v,w)=(w,v),V(G2)= 1, 2, 3, 4, 5, 6, 7 E(G1)=(1,2), (1,3), (2,3), (2,4),(2,5), (5,6), (5,7),有向完備圖n個(gè)頂點(diǎn)的有向圖最大邊數(shù)是n(n-1) 無向完備圖n個(gè)頂點(diǎn)的無向圖最大邊數(shù)是n(n-1)/2 權(quán)與圖的邊或弧相關(guān)的數(shù)叫 網(wǎng)帶權(quán)的圖叫 子圖如果圖G(V, E)和圖G(V,E),滿足： V V E E 則稱G為G的子圖 頂點(diǎn)的度 無向圖中，頂點(diǎn)的度為與每個(gè)頂點(diǎn)相連的邊數(shù) 有向圖中，頂點(diǎn)的度分成入度與出度 入度：以該頂點(diǎn)為頭的弧的數(shù)目 出度：以該頂點(diǎn)為尾的弧的數(shù)目 路徑路徑是頂點(diǎn)的序列V=Vi0,Vi1

4、,Vin，滿足(Vij-1,Vij)E 或 E,(1jn),路徑長度沿路徑邊的數(shù)目或沿路徑各邊權(quán)值之和 回路第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑叫 簡單路徑序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑叫 簡單回路除了第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)外，其余頂點(diǎn)不重復(fù)出現(xiàn)的回路叫 連通從頂點(diǎn)V到頂點(diǎn)W有一條路徑，則說V和W是 連通圖圖中任意兩個(gè)頂點(diǎn)都是連通的叫 連通分量非連通圖的每一個(gè)連通部分叫 強(qiáng)連通圖有向圖中，如果對每一對Vi,VjV, ViVj,從Vi到Vj 和從Vj到 Vi都存在路徑，則稱G是,路徑：1，2，3，5，6，3 路徑長度：5 簡單路徑：1，2，3，5 回路：1，2，3，5，6，3，1 簡單回路：3，5，

5、6，3,路徑：1，2，5，7，6，5，2，3 路徑長度：7 簡單路徑：1，2，5，7，6 回路：1，2，5，7，6，5，2，1 簡單回路：1，2，3，1,連通圖,強(qiáng)連通圖,非連通圖 連通分量,若將圖的每條邊都賦上一個(gè)權(quán)，則稱這種帶權(quán)圖為網(wǎng)絡(luò)(Network)。 通常權(quán)是具有某種意義的數(shù)，它們可以表示兩個(gè)頂點(diǎn)之間的距離，耗費(fèi)等。,圖的存儲表示分析 特點(diǎn)：頂點(diǎn)之間的關(guān)系是多對多(m : n)m 和 n 都是不定的，無法進(jìn)行非線性結(jié)構(gòu)的線性化圖中的關(guān)系不能通過順序映像(即通過頂點(diǎn)之間的存儲位置反映頂點(diǎn)之間的邏輯關(guān)系)反映；必須另外引入存儲空間反映頂點(diǎn)之間的鄰接關(guān)系。 圖的存儲信息頂點(diǎn)信息、邊/弧信息

6、、整體信息：頂點(diǎn)數(shù)、邊/弧數(shù)、圖的種類(有向圖/有向網(wǎng)/無向圖/無向網(wǎng)) 頂點(diǎn)集：順序表存儲，不是順序映像！ 關(guān)系集：鄰接矩陣、鄰接表、多重鄰接表、十字鏈表,7.2 存儲結(jié)構(gòu),（1）圖的鄰接矩陣表示法,鄰接矩陣表示頂點(diǎn)間相聯(lián)關(guān)系的矩陣 定義：設(shè)G=(V,E)是有n1個(gè)頂點(diǎn)的圖，G的鄰接矩陣A是具有以下性質(zhì)的n階方陣,圖：鄰接關(guān)系用1/0表示 網(wǎng)：鄰接關(guān)系需要進(jìn)一步反映權(quán)值，用INFINITY表示無窮大，反映頂點(diǎn)之間無鄰接關(guān)系 #defineINT_MAX32767/* 最大整數(shù)*/ #defineINFINITYINT_MAX,1) 鄰接矩陣 typedef struct ArcCell in

7、tadj;/ 頂點(diǎn)間關(guān)系，無權(quán)圖：0-不相鄰，1-相鄰 / 有權(quán)圖，權(quán)值，INFINITY-不相鄰 InfoType*info;/ 該弧相關(guān)信息的指針 ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;,2) 圖的整體結(jié)構(gòu) typedef struct VertexTypevexsMAX_VERTEX_NUM; /* 有效的頂點(diǎn)下標(biāo)從0開始 */ AdjMatrixarcs;/* 關(guān)系集 */ intvexnum, arcnum; /* 頂點(diǎn)數(shù)、邊/弧數(shù) */ GraphKindkind;/* 圖的種類*/ MGraph;,V1,V3,V2,V4,V

8、1 V2 V3 V4 V1 0 0 1 0 V2 0 0 0 1 V3 0 0 0 1 V4 1 0 0 0,V1 V2 V3 V4 V1 0 1 1 1 V2 1 0 0 1 V3 1 0 0 0 V4 1 1 0 0,圖的連接矩陣表示法,特點(diǎn)： 無向圖的鄰接矩陣對稱，可壓縮存儲；有n個(gè)頂點(diǎn)的無向圖需存儲空間為n(n+1)/2 有向圖鄰接矩陣不一定對稱；有n個(gè)頂點(diǎn)的有向圖需存儲空間為n 無向圖中頂點(diǎn)Vi的度TD(Vi)是鄰接矩陣A中第i行元素之和 有向圖中， 頂點(diǎn)Vi的出度是A中第i行元素之和 頂點(diǎn)Vi的入度是A中第i列元素之和 網(wǎng)絡(luò)的鄰接矩陣可定義為：,V1 V2 V3 V4 V1 0 0

9、 1 0 V2 0 0 0 1 V3 0 0 0 1 V4 1 0 0 0,V1 V2 V3 V4 V1 0 1 1 1 V2 1 0 0 1 V3 1 0 0 0 V4 1 1 0 0,入度 出度,1 1,1 1,2 1,0 1,度數(shù),3,2,1,2,（2）圖的鄰接表示法 即對圖中每個(gè)頂點(diǎn)建立一個(gè)單鏈表，第i個(gè)單鏈表中的結(jié)點(diǎn)表示依附于該頂點(diǎn)Vi的邊（或?。?圖的整體結(jié)構(gòu) typedef struct AdjListvertices; intvexnum, arcnum; GraphKindkind; ALGraph;,特點(diǎn) 無向圖中頂點(diǎn)Vi的度為第i個(gè)單鏈表中的結(jié)點(diǎn)數(shù) 有向圖中 頂點(diǎn)Vi的

10、出度為第i個(gè)單鏈表中的結(jié)點(diǎn)個(gè)數(shù) 頂點(diǎn)Vi的入度為整個(gè)單鏈表中鄰接點(diǎn)域值是i的結(jié)點(diǎn)個(gè)數(shù) 逆鄰接表：有向圖中對每個(gè)結(jié)點(diǎn)建立以Vi為頭的弧的單鏈表,7.3 圖的遍歷 和樹的遍歷類似，圖的遍歷也是從某個(gè)頂點(diǎn)出發(fā)，沿著某條搜索路徑對圖中所有頂點(diǎn)各作一次訪問。若給定的圖是連通圖，則從圖中任一頂點(diǎn)出發(fā)順著邊可以訪問到該圖的所有頂點(diǎn)。然而，圖的遍歷比樹的遍歷復(fù)雜得多，這是因?yàn)閳D中的任一頂點(diǎn)都可能和其余頂點(diǎn)相鄰接，故在訪問了某個(gè)頂點(diǎn)之后，可能順著某條回路又回到了該頂點(diǎn)。為了避免重復(fù)訪問同一個(gè)頂點(diǎn)，必須記住每個(gè)頂點(diǎn)是否被訪問過。,1、深度優(yōu)先遍歷(DFS) 方法：從圖的某一頂點(diǎn)V0出發(fā)，訪問此頂點(diǎn)；然后依次從V0

11、的未被訪問的鄰接點(diǎn)出發(fā)，深度優(yōu)先遍歷圖，直至圖中所有和V0相通的頂點(diǎn)都被訪問到；若此時(shí)圖中尚有頂點(diǎn)未被訪問，則另選圖中一個(gè)未被訪問的頂點(diǎn)作起點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問為止。,深度遍歷：V1 V2 V4 V8 V5 V3 V6 V7,深度遍歷：V1 V2 V4 V8 V5 V6 V3 V7,深度遍歷：V1 V2 V4 V8 V5 V6 V3 V7,深度遍歷：V1 V2 V4 V8 V3 V6 V7 V5,深度優(yōu)先遍歷算法 遞歸算法,Firstadj(G,v)返回圖G中頂點(diǎn)v的第一個(gè)鄰接點(diǎn)的編號，若不存在，則返回0； Nextadj(G,v,w)返回圖G中頂點(diǎn)v的鄰接點(diǎn)中處于w之后

12、的那個(gè)鄰接點(diǎn)的編號，若不存在，則返回0； 約定：搜索鄰接點(diǎn)將按從小到大的次序進(jìn)行。,void traver(TD g) int i; static int visitedM; for(i=1;i=n;i+) visitedi= FALSE; / 訪問標(biāo)志數(shù)組初始化 for(i=1;i=n;i+) if(!visitedi) dfs(i); ,void dfs(int v0) / 從頂點(diǎn)v0出發(fā)，深度優(yōu)先搜索遍歷連通圖 G printf(“%d ”, v0); visitedv0=true; /訪問頂點(diǎn)v0 w=firstadjG, v0; /返回v0的第一個(gè)鄰接點(diǎn) while(w!=0) if

13、(!visitedw) dfs(w); /從v0的鄰接點(diǎn)出發(fā)做深度遍歷 w=nextadj(G, v0, w); /取下一個(gè)鄰接點(diǎn) ,深度遍歷：V1,V3 ,V7 ,V6 ,V2 ,V5 ,V8 ,V4,深度遍歷：V1,V3 ,V7 ,V6 ,V2 ,V4 ,V8 ,V5,基于某種存儲結(jié)構(gòu)的DFS算法 根據(jù)選擇的存儲結(jié)構(gòu)，決定 FirstAdjVex()和NextAdjVex()的實(shí)現(xiàn)，重新整合算法。 如采用鄰接矩陣表示法表示的圖，則DFS算法如下： void DFS (MGraph G, int v, Status ( *Visit ) (MGraph G, int v) visitedv

14、= TRUE; Visit(G, v); for ( w = 0; w G.vexnum; w +) if ( G.arcsvw.adj ,采用鄰接表表示法表示的圖，則DFS算法如下： void DFS (ALGraph G, int v, Status ( *Visit ) (ALGraph G, int v) ) visitedv = TRUE; Visit(G, v); for ( p = G.verticesv.firstarc; p ; p = p-nextarc) if (!visitedp-adjvex )DFS(G, p-adjvex, Visit); ,應(yīng)用：圖的深度優(yōu)先遍歷

15、： 1、 求一條包含圖中所有頂點(diǎn)的簡單路徑(簡單回路) 2、 判斷圖中是否存在環(huán) 3、 求圖中通過給定頂點(diǎn)vk的簡單回路 4、 判斷是否存在從頂點(diǎn)vi到頂點(diǎn)vj的路徑 5、 判別v0和v1之間是否存在一條長度為k的路徑,求一條包含圖中所有頂點(diǎn)的簡單路徑,1、思路 對于任意的有向圖或無向圖G，并不一定都能找到符合題意的簡單路徑。這樣的簡單路徑要求包含G.vexnum個(gè)頂點(diǎn)，且互不相同。它的查找可以基于深度優(yōu)先遍歷。,在一個(gè)存在包含全部頂點(diǎn)的簡單路徑的圖中，以下因素會影響該簡單路徑是否能順利地查到： 1） 起點(diǎn)的選擇：如圖(a)，其符合題意的一條簡單路徑如圖(b)。若起點(diǎn)為1，則不能找到符合題意的

16、簡單路徑； 2）頂點(diǎn)的鄰接點(diǎn)次序：進(jìn)一步考察圖(a)，即使以2為起點(diǎn)，但是2的鄰接點(diǎn)選擇的是1，而不是5，此時(shí)也不能找到符合題意的解。,在基于DFS的查找算法中，由于起點(diǎn)和鄰接點(diǎn)的選取是與頂點(diǎn)和鄰接點(diǎn)的存儲次序以及算法的搜索次序有關(guān)，不可能依據(jù)特定的圖給出特定的解決算法。因此，在整個(gè)搜索中應(yīng)允許有查找失敗，此時(shí)可采取回溯到上一層的方法，繼續(xù)查找其他路徑。 這樣，引入數(shù)組Path用來保存當(dāng)前已搜索的簡單路徑上的頂點(diǎn)，引入計(jì)數(shù)器n用來記錄當(dāng)前該路徑上的頂點(diǎn)數(shù)。,對DFS算法的修改如下： 1） 計(jì)數(shù)器n的初始化，放在visited的初始化前后； 2） 訪問頂點(diǎn)時(shí)，增加將該頂點(diǎn)序號入數(shù)組Path中，計(jì)

17、數(shù)器n+；判斷是否已獲得所求路徑，是則輸出結(jié)束，否則繼續(xù)遍歷鄰接點(diǎn)； 3） 某頂點(diǎn)的全部鄰接點(diǎn)都訪問后，仍未得到簡單路徑，則回溯，將該頂點(diǎn)置為未訪問，計(jì)數(shù)器n-。,1）,1、算法 /* 鄰接矩陣表示法*/ voidHamilton(MGraph G) for ( i=0; iG.vexnum; i+ ) visitedi = FALSE; n = 0; for ( i=0; iG.vexnum; i+ ) if ( !visitedi ) DFS (G, i); voidDFS(MGraph G, int i) visitedi = TRUE; Pathn = i; n+; if ( n =

18、G.vexnum )Print(Path);/* 符合條件，輸出該簡單路徑*/ for( j=0; jG.vexnum; j+ ) if ( G.arcsij.adj ,2、廣度優(yōu)先遍歷(BFS) 方法：從圖的某一頂點(diǎn)V0出發(fā)，訪問此頂點(diǎn)后，依次訪問V0的各個(gè)未曾訪問過的鄰接點(diǎn)；然后分別從這些鄰接點(diǎn)出發(fā)，廣度優(yōu)先遍歷圖，直至圖中所有已被訪問的頂點(diǎn)的鄰接點(diǎn)都被訪問到；若此時(shí)圖中尚有頂點(diǎn)未被訪問，則另選圖中一個(gè)未被訪問的頂點(diǎn)作起點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問為止。,廣度遍歷：V1 V2 V3 V4 V5 V6 V7 V8,廣度遍歷：V1 V2 V3 V4 V5 V6 V7 V8,廣度遍

19、歷：V1 V2 V3 V4 V6 V7 V8 V5,廣度遍歷：V1 V2 V3 V4 V5 V6 V7 V8,算法思路： （1）訪問V0 （2）依次訪問V0 的所有鄰接點(diǎn)v11,v12, ,v1k （3）設(shè)剛剛被訪問過的一層頂點(diǎn)依次為vi1,vi2, ,vik 則依次訪問vi1,vi2, ,vik的未被訪問的鄰接點(diǎn) （4）重復(fù)（3）,廣度優(yōu)先遍歷算法,void traver(graph G) int i; static int visitedM; for(i=1;i=n;i+) visitedi=false; for(i=1;i=n;i+) if(!visitedi) bfs(i); ,voi

20、d bfs(graph G,int v0) printf(“%dn”,v); visitedv0=true; /訪問頂點(diǎn)v0，置訪問隊(duì)列 Q.enqueue(v0); /v0 入隊(duì) while(!Q.empty( ) /隊(duì)列Q不空時(shí) v=Q.delqueue( ); /取隊(duì)頭 w=firstadj(G,v); /取v第一個(gè)鄰接點(diǎn) while(w!=0) if (! Visitedw) printf(%dn,w); visitedw=true; Q.enqueue(w); /訪問W入隊(duì)，置訪問標(biāo)志 w=nextadj(G,v,w); /求下一個(gè)鄰接點(diǎn) ,應(yīng)用：圖的廣度優(yōu)先遍歷： 1、 判斷是否存

21、在從頂點(diǎn)vi到頂點(diǎn)vj的路徑 2、 求距v0的各頂點(diǎn)中最短路徑長度最長的一個(gè)頂點(diǎn)。 3、 求v0和v1之間的最短路徑. 4、 在頂點(diǎn)子集U中找出距離頂點(diǎn)v0最近的頂點(diǎn) 5、 求頂點(diǎn)v0到其余每個(gè)頂點(diǎn)的最短路徑 6、 求距離頂點(diǎn)v0的最短路徑長度為k的所有頂點(diǎn),求距v0的各頂點(diǎn)中最短路徑長度最長的一個(gè)頂點(diǎn),1、思路 由于題意強(qiáng)調(diào)為最短路徑，因此應(yīng)當(dāng)考慮BFS的算法應(yīng)用。本問題的求解轉(zhuǎn)變成：從v0出發(fā)進(jìn)行BFS，最后一層的頂點(diǎn)距離v0的最短路徑長度最長。 由于BFS類似于樹的按層次遍歷，需要引入隊(duì)列用來保存本身已訪問但其鄰接點(diǎn)尚未全部訪問的頂點(diǎn)。BFS遍歷中最后一層的頂點(diǎn)一定是最后出隊(duì)的若干頂點(diǎn)，

22、隊(duì)列中最后一個(gè)出隊(duì)的頂點(diǎn)必定是符合題意的頂點(diǎn)。 這樣，只需調(diào)用BFS的算法，將最后出隊(duì)的元素返回即可。,2、算法 int MaxDistance (MGraph G, int v0 ) /* 初始化各頂點(diǎn)的訪問標(biāo)志，設(shè)置為未訪問*/ for ( i=0; iG.vexnum; i+ ) visitedi = FALSE; InitQueue(Q); /* 不需要考慮其他的連通分量，因?yàn)樗蟮捻旤c(diǎn)必定與v0在同一個(gè)連通分量中 */ EnQueue (Q, v0 ); visitedv0 = TRUE; while( !QueueEmpty(Q) ) DeQueue(Q, v); for( w=0

23、; wG.vexnum; w+ ) if ( G.arcsvw.adj ,7.4 最小生成樹 圖的生成樹不是唯一的，從不同的頂點(diǎn)出發(fā)進(jìn)行遍歷，可以得到不同的生成樹。對于連通網(wǎng)絡(luò)G(V，E)，邊是帶權(quán)的，因而G的生成樹的各邊也是帶權(quán)的。我們把生成樹各邊的權(quán)值總和稱為生成樹的權(quán)，并把權(quán)最小的生成樹稱為G的最小生成樹(Minimum Spanning Tree)。 生成樹和最小生成樹有許多重要的應(yīng)用。令圖G的頂點(diǎn)表示城市，邊表示連接兩個(gè)城市之間的通訊線路。n個(gè)城市之間最多可設(shè)立的線路有n(n-1)2條，把n個(gè)城市連接起來至少要有n-1條線路，則圖G的生成樹表示了建立通訊網(wǎng)絡(luò)的可行方案。如果給圖中的邊

24、都賦予權(quán)，而這些權(quán)可表示兩個(gè)城市之間通訊線路的長度或建造代價(jià)，那么，如何選擇n-1條線路，使得建立的通訊網(wǎng)絡(luò)其線路的總長度最短或總代價(jià)最小呢?這就是要構(gòu)造該圖的一棵最小生成樹。,生成樹 定義：所有頂點(diǎn)均由邊連接在一起，但不存在回路的圖叫 深度優(yōu)先生成樹與廣度優(yōu)先生成樹 生成森林：非連通圖每個(gè)連通分量的生成樹一起組成非連通圖的 說明 一個(gè)圖可以有許多棵不同的生成樹 所有生成樹具有以下共同特點(diǎn)： 生成樹的頂點(diǎn)個(gè)數(shù)與圖的頂點(diǎn)個(gè)數(shù)相同 生成樹是圖的極小連通子圖 一個(gè)有n個(gè)頂點(diǎn)的連通圖的生成樹有n-1條邊 生成樹中任意兩個(gè)頂點(diǎn)間的路徑是唯一的 在生成樹中再加一條邊必然形成回路 含n個(gè)頂點(diǎn)n-1條邊的圖不

25、一定是生成樹,深度遍歷：V1 V2 V4 V8 V5 V3 V6 V7,廣度遍歷：V1 V2 V3 V4 V5 V6 V7 V8,最小生成樹 問題提出,要在n個(gè)城市間建立通信聯(lián)絡(luò)網(wǎng)， 頂點(diǎn)表示城市， 權(quán)城市間建立通信線路所需花費(fèi)代價(jià)， 希望找到一棵生成樹，它的每條邊上的權(quán)值之和（即建立該通信網(wǎng)所需花費(fèi)的總代價(jià)）最小最小代價(jià)生成樹。,問題分析,n個(gè)城市間，最多可設(shè)置n(n-1)/2條線路， n個(gè)城市間建立通信網(wǎng)，只需n-1條線路， 問題轉(zhuǎn)化為：如何在可能的線路中選擇n-1條，能把所有城市（頂點(diǎn)）均連起來，且總耗費(fèi)（各邊權(quán)值之和）最小。,構(gòu)造最小生成樹方法 方法一：普里姆(Prim)算法 算法思想

26、：設(shè)N=(V,E)是連通網(wǎng)，TE是N上最小生成樹中邊的集合 初始令U=u0,(u0V), TE= 在所有uU,vV-U的邊(u,v)E中，找一條代價(jià)最小的邊(u0,v0) 將(u0,v0)并入集合TE，同時(shí)v0并入U(xiǎn) 重復(fù)上述操作直至U=V為止，則T=(V,TE)為N的最小生成樹 算法實(shí)現(xiàn)：圖用鄰接矩陣表示 算法描述 算法評價(jià)：T(n)=O(n),#define M 30 #define MAX 100 void minispantree_PRIM(int adM,int n) int i,j,k,p,q,wm; q=p=n-1; adqq=1; for(k=0;kq) adpq=-adpq;

27、 else adqp=-adqp; ,1,1,1,-2,1,-4,1,-1,1,-5,1,-3,方法二：克魯斯卡爾(Kruskal)算法 算法思想：設(shè)連通網(wǎng)N=(V,E)，令最小生成樹 初始狀態(tài)為只有n個(gè)頂點(diǎn)而無邊的非連通圖T=(V,)，每個(gè)頂點(diǎn)自成一個(gè)連通分量 在E中選取代價(jià)最小的邊，若該邊依附的頂點(diǎn)落在T中不同的連通分量上，則將此邊加入到T中；否則，舍去此邊，選取下一條代價(jià)最小的邊 依此類推，直至T中所有頂點(diǎn)都在同一連通分量上為止,（0）用頂點(diǎn)數(shù)組和邊數(shù)組存放頂點(diǎn)和邊信息 （1）初始時(shí)，令每個(gè)頂點(diǎn)的jihe互不相同；每個(gè)邊的flag為0 （2）選出權(quán)值最小且flag為0的邊 （3）若該邊依

28、附的兩個(gè)頂點(diǎn)的jihe 值不同，即非連通，則令該邊的flag=1, 選中該邊；再令該邊依附的兩頂點(diǎn)的jihe以及兩集合中所有頂點(diǎn)的jihe 相同若該邊依附的兩個(gè)頂點(diǎn)的jihe 值相同，即連通，則令該邊的flag=2, 即舍去該邊。 （4）重復(fù)上述步驟，直到選出n-1條邊為止。,頂點(diǎn)結(jié)點(diǎn)： typedef struct int data; /頂點(diǎn)信息 int jihe; VEX;,邊結(jié)點(diǎn)： typedef struct int vexh, vext; /邊依附的兩頂點(diǎn) int weight; /邊的權(quán)值 int flag; /標(biāo)志域 EDGE;,算法實(shí)現(xiàn)：,算法描述：,1,1,1,1,1,4,2

29、,1,1,1,2,2,2,2,2,void minitree_KRUSKAL(void) int n,i,m,min,k,j; VEX tM; EDGE eM; printf(Input number of vertex and edge:); scanf(%d,%d, ,i=1; while(in) min=MAX; for(j=0;jm;j+) if(ej.weightmin ,7.5 有向無環(huán)圖及應(yīng)用,通常我們把計(jì)劃、施工過程、生產(chǎn)流程、程序流程等都當(dāng)成一個(gè)工程，一個(gè)大的工程常常被劃分成許多較小的子工程，這些子工程稱為活動，這些活動完成時(shí)，整個(gè)工程也就完成了。例如，計(jì)算機(jī)專業(yè)學(xué)生的課程開

30、設(shè)可看成是一個(gè)工程，每一門課程就是工程中的活動，下圖給出了若干門所開設(shè)的課程，其中有些課程的開設(shè)有先后關(guān)系，有些則沒有先后關(guān)系，有先后關(guān)系的課程必須按先后關(guān)系開設(shè)，如開設(shè)數(shù)據(jù)結(jié)構(gòu)課程之前必須先學(xué)完程序設(shè)計(jì)基礎(chǔ)及離散數(shù)學(xué)，而開設(shè)離散數(shù)學(xué)則必須學(xué)完高等數(shù)學(xué)。我們用一種有向圖來表示課程開設(shè)，在這種有向圖中，頂點(diǎn)表示活動，有向邊表示活動的優(yōu)先關(guān)系，這有向圖叫做頂點(diǎn)表示活動的網(wǎng)絡(luò)(Activity On Vertex)簡稱為AOV網(wǎng)。,一、AOV網(wǎng)及拓?fù)渑判?問題提出：學(xué)生選修課程問題 頂點(diǎn)表示課程 有向弧表示先決條件，若課程i是課程j的先決條件， 則圖中有弧 學(xué)生應(yīng)按怎樣的順序?qū)W習(xí)這些課程，才能無矛盾

31、、順利地完成學(xué)業(yè)拓?fù)渑判?定義 AOV網(wǎng)用頂點(diǎn)表示活動，用弧表示活動間優(yōu)先關(guān)系的有向圖稱為頂點(diǎn)表示活動的網(wǎng)(Activity On Vertex network)，簡稱AOV網(wǎng)。 若是圖中有向邊，則vi是vj的直接前驅(qū)；vj是vi的直接后繼 AOV網(wǎng)中不允許有回路，這意味著某項(xiàng)活動以自己為先決條件 拓?fù)渑判虬袮OV網(wǎng)絡(luò)中各頂點(diǎn)按照它們相互之間的優(yōu)先關(guān)系排列成一個(gè)線性序列的過程叫。 檢測AOV網(wǎng)中是否存在環(huán)方法：對有向圖構(gòu)造其頂點(diǎn)的拓?fù)溆行蛐蛄校艟W(wǎng)中所有頂點(diǎn)都在它的拓?fù)溆行蛐蛄兄校瑒t該AOV網(wǎng)必定不存在環(huán),拓?fù)渑判虻姆椒?在有向圖中選一個(gè)沒有前驅(qū)的頂點(diǎn)且輸出之 從圖中刪除該頂點(diǎn)和所有以它為尾的

32、弧 重復(fù)上述兩步，直至全部頂點(diǎn)均已輸出；或者當(dāng)圖中不存在無前驅(qū)的頂點(diǎn)為止。,拓?fù)湫蛄校篊1-C2-C3-C4-C5-C7-C9-C10-C11-C6-C12-C8 或 ：C9-C10-C11-C6-C1-C12-C4-C2-C3-C5-C7-C8,一個(gè)AOV網(wǎng)的拓?fù)湫蛄胁皇俏ㄒ坏?算法實(shí)現(xiàn) 以鄰接表作存儲結(jié)構(gòu) 把鄰接表中所有入度為0的頂點(diǎn)進(jìn)棧 棧非空時(shí)，輸出棧頂元素Vj并退棧；在鄰接表中查找Vj的直接后繼Vk，把Vk的入度減1；若Vk的入度為0則進(jìn)棧 重復(fù)上述操作直至?？諡橹?。若?？諘r(shí)輸出的頂點(diǎn)個(gè)數(shù)不是n，則有向圖有環(huán)；否則，拓?fù)渑判蛲戤叀?鄰接表結(jié)點(diǎn)： typedef struct node

33、 int vex; /頂點(diǎn)域 struct node *next; /鏈域 JD;,表頭結(jié)點(diǎn)： typedef struct tnode int in; /入度域 struct node *link; /鏈域 TD; TD gM; /g0不用,算法描述,1,6,輸出序列：6,輸出序列：6,輸出序列：6,輸出序列：6,輸出序列：6,輸出序列：6,輸出序列：6 1,輸出序列：6 1,輸出序列：6 1,4,輸出序列：6 1,4,輸出序列：6 1,4,輸出序列：6 1,4,3,輸出序列：6 1,4,3,輸出序列：6 1,4,3,輸出序列：6 1,4,3,輸出序列：6 1,4,3,輸出序列：6 1 3,

34、4,3,輸出序列：6 1 3,4,輸出序列：6 1 3,4,輸出序列：6 1 3,4,輸出序列：6 1 3,4,2,輸出序列：6 1 3,4,2,輸出序列：6 1 3,4,2,輸出序列：6 1 3 2,4,2,輸出序列：6 1 3 2,4,輸出序列：6 1 3 2 4,4,輸出序列：6 1 3 2 4,輸出序列：6 1 3 2 4,5,輸出序列：6 1 3 2 4,5,輸出序列：6 1 3 2 4 5,5,輸出序列：6 1 3 2 4 5,算法分析,建鄰接表：T(n)=O(e) 搜索入度為0的頂點(diǎn)的時(shí)間：T(n)=O(n) 拓?fù)渑判颍篢(n)=O(n+e),void toposort(TD g

35、,int n) int top,m,k,j; JD *p; top=0; m=0; for(j=1;j0) j=top; top=gtop.in; printf(%dn,j); m+; p=gj.link; while(p!=NULL) k=p-vex; gk.in-; if(gk.in=0) gk.in=top; top=k; p=p-next; printf(m=%dn,m); if(mn) printf(The network has a cyclen); ,二、關(guān)鍵路徑 問題提出,把工程計(jì)劃表示為有向圖，用頂點(diǎn)表示事件，弧表示活動； 每個(gè)事件表示在它之前的活動已完成，在它之后的活動可以

36、開始,例 設(shè)一個(gè)工程有11項(xiàng)活動，9個(gè)事件 事件 V1表示整個(gè)工程開始 事件V9表示整個(gè)工程結(jié)束 問題：（1）完成整項(xiàng)工程至少需要多少時(shí)間？ （2）哪些活動是影響工程進(jìn)度的關(guān)鍵？,定義 AOE網(wǎng)(Activity On Edge)也叫邊表示活動的網(wǎng)。AOE網(wǎng)是一個(gè)帶權(quán)的有向無環(huán)圖，其中頂點(diǎn)表示事件，弧表示活動，權(quán)表示活動持續(xù)時(shí)間 路徑長度路徑上各活動持續(xù)時(shí)間之和 關(guān)鍵路徑路徑長度最長的路徑叫 Ve(j)表示事件Vj的最早發(fā)生時(shí)間 Vl(j)表示事件Vj的最遲發(fā)生時(shí)間 e(i)表示活動ai的最早開始時(shí)間 l(i)表示活動ai的最遲開始時(shí)間 l(i)-e(i)表示完成活動ai的時(shí)間余量 關(guān)鍵活動關(guān)

37、鍵路徑上的活動叫，即l(i)=e(i)的活動,問題分析 如何找e(i)=l(i)的關(guān)鍵活動？,設(shè)活動ai用弧表示，其持續(xù)時(shí)間記為：dut() 則有：（1）e(i)=Ve(j) （2）l(i)=Vl(k)-dut(),如何求Ve(j)和Vl(j)？,(1)從Ve(1)=0開始向前遞推,(2)從Vl(n)=Ve(n)開始向后遞推,求關(guān)鍵路徑步驟 求Ve(i) 求Vl(j) 求e(i) 求l(i) 計(jì)算l(i)-e(i),V1 V2 V3 V4 V5 V6 V7 V8 V9,0 6 4 5 7 7 16 14 18,0 6 6 8 7 10 16 14 18,a1 a2 a3 a4 a5 a6 a7

38、 a8 a9 a10 a11, ,算法實(shí)現(xiàn) 以鄰接表作存儲結(jié)構(gòu) 從源點(diǎn)V1出發(fā)，令Ve1=0,按拓?fù)湫蛄星蟾黜旤c(diǎn)的Vei 從匯點(diǎn)Vn出發(fā)，令Vln=Ven,按逆拓?fù)湫蛄星笃溆喔黜旤c(diǎn)的Vli 根據(jù)各頂點(diǎn)的Ve和Vl值，計(jì)算每條弧的ei和li,找出ei=li的關(guān)鍵活動,鄰接表結(jié)點(diǎn)： typedef struct node int vex; /頂點(diǎn)域 int length; struct node *next; /鏈域 JD;,表頭結(jié)點(diǎn)： typedef struct tnode int vexdata; int in; /入度域 struct node *link; /鏈域 TD; TD gM;

39、/g0不用,算法描述 輸入頂點(diǎn)和弧信息，建立其鄰接表 計(jì)算每個(gè)頂點(diǎn)的入度 對其進(jìn)行拓?fù)渑判?排序過程中求頂點(diǎn)的Vei 將得到的拓?fù)湫蛄羞M(jìn)棧 按逆拓?fù)湫蛄星箜旤c(diǎn)的Vli 計(jì)算每條弧的ei和li,找出ei=li的關(guān)鍵活動,問題提出,用帶權(quán)的有向圖表示一個(gè)交通運(yùn)輸網(wǎng)，圖中： 頂點(diǎn)表示城市 邊表示城市間的交通聯(lián)系 權(quán)表示此線路的長度或沿此線路運(yùn)輸所花的時(shí)間或費(fèi)用等 問題：從某頂點(diǎn)出發(fā)，沿圖的邊到達(dá)另一頂點(diǎn)所經(jīng)過的路徑中， 各邊上權(quán)值之和最小的一條路徑最短路徑,7.6 最短路徑,1、從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑,13,8,13,19,21,20,迪杰斯特拉(Dijkstra)算法思想,按路徑長度遞增

40、次序產(chǎn)生最短路徑算法： 把V分成兩組： （1）S：已求出最短路徑的頂點(diǎn)的集合 （2）V-S=T：尚未確定最短路徑的頂點(diǎn)集合 將T中頂點(diǎn)按最短路徑遞增的次序加入到S中， 保證：（1）從源點(diǎn)V0到S中各頂點(diǎn)的最短路徑長度都不大于 從V0到T中任何頂點(diǎn)的最短路徑長度 （2）每個(gè)頂點(diǎn)對應(yīng)一個(gè)距離值 S中頂點(diǎn)：從V0到此頂點(diǎn)的最短路徑長度 T中頂點(diǎn)：從V0到此頂點(diǎn)的只包括S中頂點(diǎn)作中間 頂點(diǎn)的最短路徑長度,依據(jù)：可以證明V0到T中頂點(diǎn)Vk的最短路徑，或是從V0到Vk的 直接路徑的權(quán)值；或是從V0經(jīng)S中頂點(diǎn)到Vk的路徑權(quán)值之和 （反證法可證）,求最短路徑步驟 初使時(shí)令 S=V0,T=其余頂點(diǎn)，T中頂點(diǎn)對應(yīng)

41、的距離值 若存在，為弧上的權(quán)值 若不存在，為 從T中選取一個(gè)其距離值為最小的頂點(diǎn)W，加入S 對T中頂點(diǎn)的距離值進(jìn)行修改：若加進(jìn)W作中間頂點(diǎn)，從V0到Vi的距離值比不加W的路徑要短，則修改此距離值 重復(fù)上述步驟，直到S中包含所有頂點(diǎn)，即S=V為止,13 8 30 32 V2:8 ,13 - 13 30 32 V1:13 ,- - 13 30 22 20 V3:13 ,- - - 19 22 20 V4:19 ,- - - - 21 20 V6:20 ,算法實(shí)現(xiàn) 圖用帶權(quán)鄰接矩陣存儲ad 數(shù)組dist存放當(dāng)前找到的從源點(diǎn)V0到每個(gè)終點(diǎn)的最短路徑長度，其初態(tài)為圖中直接路徑權(quán)值 數(shù)組pre表示從V0到

42、各終點(diǎn)的最短路徑上，此頂點(diǎn)的前一頂點(diǎn)的序號；若從V0到某終點(diǎn)無路徑，則用0作為其前一頂點(diǎn)的序號,算法描述,1,13,3,1,22,20,2,2,19,4,1,21,5,1,1,1,13,8,13,19,21,20,算法分析：T(n)=O(n),void shortpath_DIJ(int adM,int k,int pre, int dist,int n) int i,j,p,wm; k=k-1; for(i=0;in;i+) disti=adki; if(distiMAX) prei=k+1; else prei=0; prek=0; distk=0; adkk=1; for(j=0;j(n

43、-1);j+) wm=MAX; p=-1; for(i=0;in;i+) if(adii=0) ,2、每一對頂點(diǎn)之間的最短路徑 方法一：每次以一個(gè)頂點(diǎn)為源點(diǎn)，重復(fù)執(zhí)行Dijkstra算法n次 T(n)=O(n) 方法二：弗洛伊德(Floyd)算法 算法思想：逐個(gè)頂點(diǎn)試探法 求最短路徑步驟 初始時(shí)設(shè)置一個(gè)n階方陣，令其對角線元素為0，若存在弧，則對應(yīng)元素為權(quán)值；否則為 逐步試著在原直接路徑中增加中間頂點(diǎn)，若加入中間點(diǎn)后路徑變短，則修改之；否則，維持原值 所有頂點(diǎn)試探完畢，算法結(jié)束,算法實(shí)現(xiàn) 圖用鄰接矩陣存儲 length存放最短路徑長度 pathij是從Vi到Vj的最短路徑上Vj前一頂點(diǎn)序號 算法描述,算法分析：T(n)=O(n),void shortpath_FLOYD(int costM,int pathM,int lengthM,int n) int i,j,k,wm; for(i=0;in;i+) for(j=0;jn;j+) lengthij=costij; if(i=j) pathij=0; else if(lengthijMAX) pathij=i+1; else pathij=0; for(k=0;kn;k+) fo