1、第第8章圖章圖2021年10月16日第第8章圖章圖一、一、現(xiàn)實(shí)中的圖現(xiàn)實(shí)中的圖8.1 8.1 圖的基本概念圖的基本概念 圖最常見的應(yīng)用是在交通運(yùn)輸和通信網(wǎng)絡(luò)中找出造價(jià)圖最常見的應(yīng)用是在交通運(yùn)輸和通信網(wǎng)絡(luò)中找出造價(jià)最低的方案。通信網(wǎng)絡(luò)示例如下圖所示：最低的方案。通信網(wǎng)絡(luò)示例如下圖所示： 圖圖G是由一個(gè)是由一個(gè)頂點(diǎn)集頂點(diǎn)集V和一個(gè)和一個(gè)邊邊集集E構(gòu)成的數(shù)據(jù)結(jié)構(gòu)。構(gòu)成的數(shù)據(jù)結(jié)構(gòu)。記為二元組形式：記為二元組形式： G= (V, E)其中其中: V是由頂點(diǎn)構(gòu)成的是由頂點(diǎn)構(gòu)成的非空非空有限集合，記為：有限集合，記為：VV0, V1, V2, Vn-1 E是由是由V中頂點(diǎn)的對偶構(gòu)成的有限集合，記為：中頂點(diǎn)的

2、對偶構(gòu)成的有限集合，記為：E=(V0, V2), (V3, V4), ，若若E為空，則圖中只有頂點(diǎn)而沒有邊為空，則圖中只有頂點(diǎn)而沒有邊。其中對偶可以表示成：其中對偶可以表示成： (Vi, Vj)無序的對偶稱為無序的對偶稱為邊邊，即，即(Vi, Vj)=(Vj, Vi) ，其圖稱為，其圖稱為無向圖無向圖 有序的對偶稱為有序的對偶稱為弧弧，即，即 ，則稱，則稱Vi為弧尾為弧尾，稱，稱Vj為弧頭為弧頭，該圖稱為，該圖稱為有向圖有向圖二、二、圖的定義圖的定義有向圖和無向圖示例：有向圖和無向圖示例： 無向圖無向圖G1的二元組表示：的二元組表示：V(G1)=V1, V2, V3, V4E(G1)=(V1,

3、 V2)，(V1, V3)，(V1, V4)，(V2, V3)，(V2, V4)，(V3, V4)有向圖有向圖G3的二元組表示：的二元組表示： V(G3)=V1, V2, V3 E(G3)=，l 在無向圖中，若存在一條邊（在無向圖中，若存在一條邊（Vi, Vj），則稱），則稱Vi和和Vj互為互為（Adjacent）l 在有向圖中，若存在一條弧在有向圖中，若存在一條弧，則稱，則稱Vi為此為此弧的弧的起點(diǎn)，起點(diǎn)，稱稱Vj為此弧的為此弧的終點(diǎn)，終點(diǎn)，稱稱Vi鄰接到鄰接到Vj，Vj鄰接自鄰接自Vi，Vi和和Vj互為鄰接點(diǎn)互為鄰接點(diǎn)。 2頂點(diǎn)的度、入度和出度頂點(diǎn)的度、入度和出度l 在無向圖中，與頂點(diǎn)在無

4、向圖中，與頂點(diǎn)v相鄰接的邊數(shù)稱為相鄰接的邊數(shù)稱為該頂點(diǎn)的該頂點(diǎn)的度度，記為，記為D(v)。l 在有向圖中，頂點(diǎn)在有向圖中，頂點(diǎn)v的度又分為的度又分為入度入度和和出度出度兩種：兩種：以頂點(diǎn)以頂點(diǎn)v為終點(diǎn)為終點(diǎn)(弧頭弧頭)的弧的數(shù)目稱為頂點(diǎn)的弧的數(shù)目稱為頂點(diǎn)v的的入度入度，記，記為為ID(v)；以頂點(diǎn)以頂點(diǎn)v為起點(diǎn)為起點(diǎn)(弧尾弧尾)的弧的數(shù)目稱為頂點(diǎn)的弧的數(shù)目稱為頂點(diǎn)v的的出度出度，記，記為為OD(v)；有向圖頂點(diǎn)有向圖頂點(diǎn)v的度為該頂點(diǎn)的入度和出度之和，即的度為該頂點(diǎn)的入度和出度之和，即 D(v)=ID(v)+OD(v)l 無論是有向圖還是無向圖，一個(gè)圖的頂點(diǎn)數(shù)無論是有向圖還是無向圖，一個(gè)圖的頂

5、點(diǎn)數(shù)n n、邊、邊( (弧弧) )數(shù)數(shù)e e和每個(gè)頂點(diǎn)的度和每個(gè)頂點(diǎn)的度d di i之間滿足以下的關(guān)系式：之間滿足以下的關(guān)系式：11()2niieD vl 即在有向圖或無向圖中：即在有向圖或無向圖中：所有頂點(diǎn)度數(shù)之和所有頂點(diǎn)度數(shù)之和 ：邊數(shù)：邊數(shù) = 2 = 2 ：1 13完全圖、稠密圖和稀疏圖完全圖、稠密圖和稀疏圖l 在圖在圖G中：中：若若G為無向圖，任意兩個(gè)頂點(diǎn)之間都有一條邊，稱為無向圖，任意兩個(gè)頂點(diǎn)之間都有一條邊，稱G為為無無向完全圖向完全圖。頂點(diǎn)數(shù)為。頂點(diǎn)數(shù)為n，無向完全圖的邊數(shù)：，無向完全圖的邊數(shù)： e=Cn2 =n(n 1)/2若若G為有向圖，任意兩個(gè)頂點(diǎn)為有向圖，任意兩個(gè)頂點(diǎn)Vi

6、, Vj之間都有弧之間都有弧 、 ，稱，稱G為為有向完全圖有向完全圖。如頂點(diǎn)數(shù)為。如頂點(diǎn)數(shù)為n，有向完全圖，有向完全圖的弧數(shù)：的弧數(shù)： e=Pn2 =n(n 1)l 例如，無向圖例如，無向圖G1就是就是4個(gè)頂點(diǎn)無向完全圖。個(gè)頂點(diǎn)無向完全圖。l 若一個(gè)圖接近完全圖，則稱其為若一個(gè)圖接近完全圖，則稱其為；反之，若一個(gè)圖含；反之，若一個(gè)圖含有很少條邊或弧（即有很少條邊或弧（即en2），則稱其為），則稱其為。l 若有圖若有圖G=(V, E)和和G=(V, E) l 且且V 是是V的子集，即的子集，即V V ， E是是E的子集，即的子集，即 E El 則稱圖則稱圖G為圖為圖G的子圖。的子圖。 5路徑、回

7、路和路徑長度路徑、回路和路徑長度l 在無向圖在無向圖G中，若存在一個(gè)頂點(diǎn)序列中，若存在一個(gè)頂點(diǎn)序列(Vp , Vi1 , Vi2 , , Vin , Vq)，使使(Vp, Vi1)，(Vi1, Vi2)，(Vin, Vq)均為圖均為圖G的邊，則該稱頂?shù)倪叄瑒t該稱頂點(diǎn)的序列為頂點(diǎn)點(diǎn)的序列為頂點(diǎn)Vp到頂點(diǎn)到頂點(diǎn)Vq的的路徑路徑。若。若G是有向圖，則路徑是有向圖，則路徑是有向的。是有向的。l 路徑長度路徑長度定義為路徑上的邊數(shù)或者弧的數(shù)目。定義為路徑上的邊數(shù)或者弧的數(shù)目。l 若一條路徑中不出現(xiàn)重復(fù)頂點(diǎn)，則稱此路徑為若一條路徑中不出現(xiàn)重復(fù)頂點(diǎn)，則稱此路徑為簡單路徑簡單路徑。l 若一條路徑的起點(diǎn)和終點(diǎn)相

8、同（若一條路徑的起點(diǎn)和終點(diǎn)相同（Vp=Vq）稱為）稱為回路回路或或環(huán)環(huán)。l 除了起點(diǎn)和終點(diǎn)相同外，其余頂點(diǎn)不相同的回路，稱為除了起點(diǎn)和終點(diǎn)相同外，其余頂點(diǎn)不相同的回路，稱為簡單簡單回路回路或或簡單環(huán)簡單環(huán)。l 例如，在無向圖例如，在無向圖G1中：中：頂點(diǎn)序列（頂點(diǎn)序列（V1, V2, V3, V4）是一條從頂點(diǎn)）是一條從頂點(diǎn)V1到頂點(diǎn)到頂點(diǎn)V4，長度為，長度為3的的簡單路徑簡單路徑；頂點(diǎn)序列（頂點(diǎn)序列（V1, V2, V4, V1, V3）是一條從頂點(diǎn)）是一條從頂點(diǎn)V1到到頂點(diǎn)頂點(diǎn)V3，長度為，長度為4的的路徑路徑，但不是簡單路徑；，但不是簡單路徑；頂點(diǎn)序列（頂點(diǎn)序列（V1, V2, V3,

9、V1）是一條長度為）是一條長度為3的的簡單簡單回路回路。l 在有向圖在有向圖G3中：中：頂點(diǎn)序列（頂點(diǎn)序列（V2, V3, V2）是一個(gè)長度為）是一個(gè)長度為2的的有向簡單有向簡單環(huán)環(huán)。6連通、連通分量和連通圖、生成樹連通、連通分量和連通圖、生成樹l 在無向圖在無向圖G中：中：如果從頂點(diǎn)如果從頂點(diǎn)Vi 到頂點(diǎn)到頂點(diǎn)Vj至少有一條路徑，則稱至少有一條路徑，則稱Vi與與Vj是是連通連通的。的。如果圖中任意兩個(gè)頂點(diǎn)都連通，則稱如果圖中任意兩個(gè)頂點(diǎn)都連通，則稱G為為連通圖連通圖，否則稱為，否則稱為非連通圖。非連通圖。在非連通圖在非連通圖G中，任何一個(gè)中，任何一個(gè)極大連通子圖極大連通子圖稱為稱為G的的連通

10、分量連通分量。任何連通圖的連通分量只有一個(gè)，即其自身，而非連通圖有任何連通圖的連通分量只有一個(gè)，即其自身，而非連通圖有多個(gè)連通分量。多個(gè)連通分量。在一個(gè)連通圖中，在一個(gè)連通圖中，含有全部頂點(diǎn)的極小含有全部頂點(diǎn)的極小(邊數(shù)最少邊數(shù)最少)連通子圖連通子圖，稱為該連通圖的稱為該連通圖的生成樹生成樹。(包含圖的所有包含圖的所有 n 個(gè)結(jié)點(diǎn)，但只含個(gè)結(jié)點(diǎn)，但只含圖的圖的 n-1 條邊。在生成樹中添加一條邊之后，必定會(huì)形成回條邊。在生成樹中添加一條邊之后，必定會(huì)形成回路或環(huán)路或環(huán))l 非連通圖非連通圖G4G4A AB BC CD DE EF FG GI IJ JK KA AB BC CD DE EI IJ

11、 JK KF FG Gl 圖圖G1G1和和G2G2為連通圖為連通圖l 非連通圖非連通圖G4G4的三個(gè)連通分量的三個(gè)連通分量l 連通圖連通圖G5G5A AB BC CD Dl 連通圖連通圖G5G5的兩棵生成樹的兩棵生成樹A AB BC CD DA AB BC CD D7強(qiáng)連通、強(qiáng)連通分量和強(qiáng)連通圖強(qiáng)連通、強(qiáng)連通分量和強(qiáng)連通圖l 在有向圖在有向圖G中：中：存在從頂點(diǎn)存在從頂點(diǎn)Vi 到頂點(diǎn)到頂點(diǎn)Vj的路徑，也存在從頂點(diǎn)的路徑，也存在從頂點(diǎn)Vj 到頂點(diǎn)到頂點(diǎn)Vi的路徑，則稱的路徑，則稱Vi與與Vj是是強(qiáng)連通強(qiáng)連通的。的。如果圖中任意兩個(gè)頂點(diǎn)都是強(qiáng)連通，則稱如果圖中任意兩個(gè)頂點(diǎn)都是強(qiáng)連通，則稱G為為強(qiáng)連

12、通圖強(qiáng)連通圖，否則稱為否則稱為非強(qiáng)連通圖。非強(qiáng)連通圖。在非強(qiáng)連通圖在非強(qiáng)連通圖G中，任何一個(gè)中，任何一個(gè)極大強(qiáng)連通子圖極大強(qiáng)連通子圖稱為稱為G的的強(qiáng)連強(qiáng)連通分量通分量。任何強(qiáng)連通圖的強(qiáng)連通分量只有一個(gè)，即其自身，而非強(qiáng)任何強(qiáng)連通圖的強(qiáng)連通分量只有一個(gè)，即其自身，而非強(qiáng)連通圖有多個(gè)強(qiáng)連通分量。連通圖有多個(gè)強(qiáng)連通分量。有向圖有向圖G G和強(qiáng)連通分量示例：和強(qiáng)連通分量示例： 8權(quán)、帶權(quán)圖、有向網(wǎng)和無向網(wǎng)權(quán)、帶權(quán)圖、有向網(wǎng)和無向網(wǎng)l 在一個(gè)圖中，各邊在一個(gè)圖中，各邊(或弧或弧)上可以帶一個(gè)數(shù)值，這個(gè)數(shù)值稱為上可以帶一個(gè)數(shù)值，這個(gè)數(shù)值稱為權(quán)權(quán)。l 這種每條邊都帶權(quán)的圖稱為這種每條邊都帶權(quán)的圖稱為8.2

13、圖的基本存儲(chǔ)結(jié)構(gòu)圖的基本存儲(chǔ)結(jié)構(gòu) V V0 0 V V4 4 V V3 3 V V1 1 V V2 2 V V0 0 V V1 1 V V2 2 V V3 3a ij=0 vi與與vj無邊無邊1 vi與與vj有邊有邊a ij=0 vi到到vj無弧無弧1 vi到到vj有弧有弧a ij=或或0 vi與與vj無邊（或無邊（或vi到到vj無弧）無弧）w vi與與vj有邊（或有邊（或vi到到vj有弧）有弧）W 表示邊上的權(quán)值；表示邊上的權(quán)值； 0 表示表示vi與與vj是同一個(gè)頂點(diǎn)是同一個(gè)頂點(diǎn) 表示一個(gè)計(jì)算機(jī)允許的、大于所有邊上權(quán)值的數(shù)。表示一個(gè)計(jì)算機(jī)允許的、大于所有邊上權(quán)值的數(shù)。 鄰接矩陣表示鄰接矩陣表

14、示0 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 00 1 1 0 0V1V2 V4 V5 V3 V1V2 V4 V5 V3 254311鄰接矩陣表示鄰接矩陣表示0 2 4 2 0 1 5 1 0 3 1 4 3 0 5 1 0 V1V2V3V4V5V1V2V3V4V5V1V2V3V4V5V1V2V3V4V5V1V2 V3 V4 0 1 1 00 0 0 00 0 0 11 0 0 0鄰接矩陣表示鄰接矩陣表示V1V2V3V4V1V2V3V4 容易實(shí)現(xiàn)圖的操作，如：求某頂點(diǎn)的度、判斷頂點(diǎn)之間是否容易實(shí)現(xiàn)圖的操作，如：求某頂點(diǎn)的度、判斷頂點(diǎn)之間是否有邊（弧）、找頂點(diǎn)的鄰接點(diǎn)等

15、等。有邊（弧）、找頂點(diǎn)的鄰接點(diǎn)等等。 n n個(gè)頂點(diǎn)需要個(gè)頂點(diǎn)需要n n* *n n個(gè)單元存儲(chǔ)邊個(gè)單元存儲(chǔ)邊( (弧弧););空間效率為空間效率為O(nO(n2 2) )。 對稀疏圖而言尤其浪費(fèi)空間。對稀疏圖而言尤其浪費(fèi)空間。鄰接矩陣法鄰接矩陣法優(yōu)點(diǎn)：優(yōu)點(diǎn)：鄰接矩陣法鄰接矩陣法缺點(diǎn)：缺點(diǎn)：2、鄰接矩陣法、鄰接矩陣法特點(diǎn)特點(diǎn)# define MAX 100 /* MAX為圖中頂點(diǎn)最多個(gè)數(shù)為圖中頂點(diǎn)最多個(gè)數(shù) */typedef int vextype; /* vextype為頂點(diǎn)的數(shù)據(jù)類型為頂點(diǎn)的數(shù)據(jù)類型 */typedef struct vextype vexMAX; /* 一維數(shù)組存儲(chǔ)頂點(diǎn)信息一

16、維數(shù)組存儲(chǔ)頂點(diǎn)信息 */ int arcMAXMAX; /*鄰接矩陣存儲(chǔ)邊（弧）信息鄰接矩陣存儲(chǔ)邊（弧）信息 */ int vn, en; /* vn頂點(diǎn)數(shù)和頂點(diǎn)數(shù)和en邊數(shù)邊數(shù) */MGraph; /* 圖類型圖類型 */注：注：MGraph 既可以表示有向圖、無向圖，也可以表示有既可以表示有向圖、無向圖，也可以表示有整型權(quán)的網(wǎng)整型權(quán)的網(wǎng)例：建一個(gè)如圖所示的無向圖例：建一個(gè)如圖所示的無向圖013420 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 00 1 1 0 0void CreateGraph(MGraph *g) int i, j, v, e; scanf(%d

17、%d, &g-vn, &g-en); /*輸入頂點(diǎn)數(shù)和邊數(shù)輸入頂點(diǎn)數(shù)和邊數(shù)*/ for(v=0;vvn;v+) scanf(%d, &g-vexv); /*頂點(diǎn)數(shù)據(jù)輸入頂點(diǎn)數(shù)據(jù)輸入*/ for(i=0;ivn;i+) for(j=0;jvn;j+) g-arcij=0; /*鄰接矩陣的初始值都為鄰接矩陣的初始值都為0*/ for(e=0;een;e+) /*共有共有g(shù)-en條邊條邊*/ scanf(%d %d, &i, &j); /*指明有邊的兩個(gè)頂點(diǎn)的序號(hào)指明有邊的兩個(gè)頂點(diǎn)的序號(hào)*/ g-arcij=1; /*有邊賦值為有邊賦值為1*/ g-arcji=1; /*建有向圖時(shí)此句不要建有向圖時(shí)

18、此句不要*/ 鄰接表表示鄰接表表示V1V2 V4 V5 V3 V1V2 V4 V5 V3 254311鄰接表表示鄰接表表示V1V2V3V4V501234130420212143V1V2V3V4V501234123402452111413304231521與頂點(diǎn)與頂點(diǎn)V1相鄰接的頂點(diǎn)相鄰接的頂點(diǎn)在數(shù)組中的下標(biāo)在數(shù)組中的下標(biāo)權(quán)值權(quán)值V1V2 V3 V4 鄰接表表示鄰接表表示12V1V2V3V4012330以頂點(diǎn)以頂點(diǎn)V1為始點(diǎn)的弧的終點(diǎn)為始點(diǎn)的弧的終點(diǎn)頂點(diǎn)在數(shù)組中的下標(biāo)頂點(diǎn)在數(shù)組中的下標(biāo)鄰接表的鄰接表的缺點(diǎn)：缺點(diǎn)：鄰接表的鄰接表的優(yōu)點(diǎn)：優(yōu)點(diǎn)：空間效率高；空間效率高；容易尋找頂點(diǎn)的鄰接點(diǎn)；容易尋找頂

19、點(diǎn)的鄰接點(diǎn)；判斷任意兩頂點(diǎn)間是否有邊或弧，需搜判斷任意兩頂點(diǎn)間是否有邊或弧，需搜索兩結(jié)點(diǎn)對應(yīng)的單鏈表，沒有鄰接矩陣索兩結(jié)點(diǎn)對應(yīng)的單鏈表，沒有鄰接矩陣方便。方便。2、鄰接表法、鄰接表法特點(diǎn)特點(diǎn)adjvexnext表結(jié)點(diǎn)：表結(jié)點(diǎn)：adjvexnextw鄰接點(diǎn)序號(hào)鄰接點(diǎn)序號(hào)(下標(biāo)下標(biāo))下一個(gè)鄰接下一個(gè)鄰接點(diǎn)地址點(diǎn)地址權(quán)值權(quán)值表結(jié)點(diǎn)類型表結(jié)點(diǎn)類型vertexfirstarc頂點(diǎn)結(jié)點(diǎn)：頂點(diǎn)結(jié)點(diǎn)：頂點(diǎn)信息頂點(diǎn)信息鏈表頭指針鏈表頭指針(指向第一個(gè)表結(jié)點(diǎn)指向第一個(gè)表結(jié)點(diǎn))頂點(diǎn)結(jié)點(diǎn)類型頂點(diǎn)結(jié)點(diǎn)類型頂點(diǎn)結(jié)點(diǎn)所在數(shù)組頂點(diǎn)結(jié)點(diǎn)所在數(shù)組例：建一個(gè)如圖所示的有向圖例：建一個(gè)如圖所示的有向圖01 2 31201230123

20、30void CreateAGraph(ALGraph *g) int i, j, v, e; ArcNode* p; scanf(%d %d, &g-vn, &g-en); /*輸入頂點(diǎn)數(shù)和邊數(shù)輸入頂點(diǎn)數(shù)和邊數(shù)*/ for(v=0;vvn;v+) /*頂點(diǎn)數(shù)組元素值的獲得頂點(diǎn)數(shù)組元素值的獲得*/ scanf(%d,&g-adjlistv.vertex); /*頂點(diǎn)數(shù)據(jù)鍵盤輸入頂點(diǎn)數(shù)據(jù)鍵盤輸入*/ g-adjlistv.firstarc=NULL; for(e=0;een;e+) /*共有共有g(shù)-en條邊條邊*/ scanf(%d %d, &i, &j); /*i j有弧，有弧，i、j為頂點(diǎn)序

21、號(hào)為頂點(diǎn)序號(hào)*/ p=(ArcNode*)malloc(sizeof(ArcNode); p-adjvex=j; /*把值為把值為j的結(jié)點(diǎn)頭插入到的結(jié)點(diǎn)頭插入到i頂點(diǎn)的鏈表中頂點(diǎn)的鏈表中*/ p-next=g-adjlisti.firstarc; g-adjlisti.firstarc=p; 0 A 1 41 B 0 4 52 C 3 53 D 2 54 E 0 15 F 1 2 3BACDFE補(bǔ)例：圖的鄰接表存儲(chǔ)表示補(bǔ)例：圖的鄰接表存儲(chǔ)表示有向圖的鄰接表有向圖的鄰接表1 4230 120 1 2 3 4 A B C D EABECD可見，在有向圖的鄰接表中不易找到指向該頂點(diǎn)的弧ABECD有向

22、圖的逆鄰接表有向圖的逆鄰接表A B C D E 303420 01234在有向圖的逆鄰接表中，對每個(gè)頂點(diǎn)，鏈接的是指向該頂點(diǎn)的弧 8.3 圖的遍歷圖的遍歷 從圖中某個(gè)頂點(diǎn)出發(fā)遍歷圖，訪遍圖中其余頂點(diǎn)，并且使圖中的每個(gè)頂點(diǎn)僅被訪問一次的過程。圖的遍歷有兩種方法： 深度優(yōu)先搜索遍歷（DFS） 廣度優(yōu)先搜索遍歷（BFS）。它們對無向圖和有向圖都適用。 8.3.1 連通圖的連通圖的深度優(yōu)先搜索遍歷深度優(yōu)先搜索遍歷l 首先訪問初始出發(fā)點(diǎn)首先訪問初始出發(fā)點(diǎn)V V0 0，并將其標(biāo)記設(shè)置為已訪問；，并將其標(biāo)記設(shè)置為已訪問；l 然后任選一個(gè)與然后任選一個(gè)與V V0 0相鄰接且沒有被訪問的鄰接點(diǎn)相鄰接且沒有被訪問

23、的鄰接點(diǎn)V V1 1作為新的作為新的出發(fā)點(diǎn)，訪問出發(fā)點(diǎn)，訪問V V1 1之后，將其標(biāo)記設(shè)置為已訪問；之后，將其標(biāo)記設(shè)置為已訪問；l 再以再以V V1 1為新的出發(fā)點(diǎn)，繼續(xù)進(jìn)行深度優(yōu)先搜索，訪問與為新的出發(fā)點(diǎn)，繼續(xù)進(jìn)行深度優(yōu)先搜索，訪問與V V1 1相相鄰接且沒有被訪問的任一個(gè)頂點(diǎn)鄰接且沒有被訪問的任一個(gè)頂點(diǎn)V V2 2；l 重復(fù)上述過程，若遇到一個(gè)所有鄰接點(diǎn)均被訪問過的頂點(diǎn)，重復(fù)上述過程，若遇到一個(gè)所有鄰接點(diǎn)均被訪問過的頂點(diǎn)，則回到已訪問頂點(diǎn)序列中最后一個(gè)還存在未被訪問的鄰接點(diǎn)則回到已訪問頂點(diǎn)序列中最后一個(gè)還存在未被訪問的鄰接點(diǎn)的頂點(diǎn)，再從該頂點(diǎn)出發(fā)繼續(xù)進(jìn)行深度優(yōu)先搜索，直到圖中的頂點(diǎn)，再從該

24、頂點(diǎn)出發(fā)繼續(xù)進(jìn)行深度優(yōu)先搜索，直到圖中所有頂點(diǎn)都被訪問過，搜索結(jié)束。所有頂點(diǎn)都被訪問過，搜索結(jié)束。 V0V0 V7V7 V6V6 V5V5 V4V4 V3V3 V2V2 V1V1 V0V0 V1V1 V3V3 V2V2 V7V7 V6V6 V5V5 V4V4例例l序列序列1： V0,V1,V3,V7,V4,V2,V5,V6l從從v0出發(fā)的出發(fā)的DFS序列為：序列為：由于沒有規(guī)定由于沒有規(guī)定訪問鄰接點(diǎn)的順序，訪問鄰接點(diǎn)的順序，DFSDFS序列不是唯一的序列不是唯一的l序列序列2： V0,V1,V4,V7,V3,V2,V5,V6算法描述：算法描述： 訪問開始頂點(diǎn)（如訪問開始頂點(diǎn)（如 v）；）； 尋

25、找尋找 v 頂點(diǎn)未被訪問的第一個(gè)鄰接頂點(diǎn)（如頂點(diǎn)未被訪問的第一個(gè)鄰接頂點(diǎn)（如 w）；）； 并把并把 w 作為開始頂點(diǎn)繼續(xù)深度優(yōu)先搜索遍歷（遞歸思想）；作為開始頂點(diǎn)繼續(xù)深度優(yōu)先搜索遍歷（遞歸思想）； 直到所有頂點(diǎn)被訪問；直到所有頂點(diǎn)被訪問； 其中處理：其中處理：（1）訪問頂點(diǎn)：自定義訪問函數(shù)）訪問頂點(diǎn)：自定義訪問函數(shù) visit()（2）未被訪問的鄰接點(diǎn)：定義一個(gè)標(biāo)記數(shù)組：）未被訪問的鄰接點(diǎn)：定義一個(gè)標(biāo)記數(shù)組：int visitedMAX visitedi= 0 i號(hào)頂點(diǎn)號(hào)頂點(diǎn)未未被訪問被訪問 1 i號(hào)頂點(diǎn)號(hào)頂點(diǎn)已已被訪問被訪問 注意：由于函數(shù)是遞歸的，數(shù)組定義成外部數(shù)組注意：由于函數(shù)是遞歸的，

26、數(shù)組定義成外部數(shù)組 （3）第一個(gè)鄰接點(diǎn)：按鄰接距陣或鄰接表中邊存儲(chǔ)的順序）第一個(gè)鄰接點(diǎn)：按鄰接距陣或鄰接表中邊存儲(chǔ)的順序 函數(shù)實(shí)現(xiàn)：函數(shù)實(shí)現(xiàn)：形參：形參：圖變量地址，開始頂點(diǎn)的序號(hào)（下標(biāo)）圖變量地址，開始頂點(diǎn)的序號(hào)（下標(biāo)）返回值：返回值：無無void dfs(MGraph *g, int v) int j, w; visit(g, v); /*訪問訪問v號(hào)頂點(diǎn)號(hào)頂點(diǎn)*/ visitedv=1; /*v號(hào)頂點(diǎn)為已訪問號(hào)頂點(diǎn)為已訪問*/ for(j=0; jvn; j+) /*找所有的鄰接頂點(diǎn)找所有的鄰接頂點(diǎn)*/ if( g-arcvj=1 & visitedj=0) /*v號(hào)頂點(diǎn)與號(hào)頂點(diǎn)與j號(hào)頂

27、點(diǎn)號(hào)頂點(diǎn) 間有邊，且間有邊，且j號(hào)頂點(diǎn)為被訪問號(hào)頂點(diǎn)為被訪問*/ w=j; dfs(g, w); 鄰接距陣存儲(chǔ)結(jié)構(gòu)的圖鄰接距陣存儲(chǔ)結(jié)構(gòu)的圖起始頂點(diǎn)的序號(hào)（下標(biāo)）起始頂點(diǎn)的序號(hào)（下標(biāo)）void visit (MGraph *g, int v) printf(n %d, g-vexv); 按算法實(shí)現(xiàn)的按算法實(shí)現(xiàn)的dfs遍歷舉例：遍歷舉例：V0頂點(diǎn)出發(fā)遍歷結(jié)果（唯一）頂點(diǎn)出發(fā)遍歷結(jié)果（唯一） ：V0、 V1、 V2、 V3、 V4V2頂點(diǎn)出發(fā)遍歷結(jié)果（唯一）頂點(diǎn)出發(fā)遍歷結(jié)果（唯一） ：V2、 V1、 V0、 V4、 V3V0V1V2V3V4無向圖：無向圖：0101110110010101110110

28、010鄰接矩陣存儲(chǔ)結(jié)構(gòu)：鄰接矩陣存儲(chǔ)結(jié)構(gòu)：V0V1V2V3V401234設(shè)計(jì)程序創(chuàng)建鄰接矩陣的無向圖，并用設(shè)計(jì)程序創(chuàng)建鄰接矩陣的無向圖，并用dfsdfs圖中頂點(diǎn)圖中頂點(diǎn)信息并輸出：信息并輸出：宏定義及數(shù)據(jù)類型：宏定義及數(shù)據(jù)類型：#include #define MAX 20 /*圖頂點(diǎn)最多不超過圖頂點(diǎn)最多不超過20*/typedef int vextype; /*圖頂點(diǎn)為圖頂點(diǎn)為int型型*/typedef struct vextype vexMAX; int arcMAXMAX; int vn, en; MGraph; /*鄰接矩陣圖類型鄰接矩陣圖類型*/int visitedMAX; /*

29、訪問標(biāo)記數(shù)組訪問標(biāo)記數(shù)組*/函數(shù)定義：函數(shù)定義：void CreateGraph(MGraph *g) /*創(chuàng)建無向圖創(chuàng)建無向圖*/ void visit(MGraph *g, int v) /*訪問圖中某個(gè)頂點(diǎn)訪問圖中某個(gè)頂點(diǎn)*/ void dfs(MGraph *g, int v) /*dfs遍歷圖遍歷圖*/ main() /*主函數(shù)主函數(shù)*/ MGraph mg; /*mg為圖結(jié)構(gòu)變量為圖結(jié)構(gòu)變量/ int i, start; /*start開始頂點(diǎn)序號(hào)開始頂點(diǎn)序號(hào)*/ CreateGraph(&mg); for(i=0; iadjlistw.firstarc; /*w號(hào)頂點(diǎn)的第一個(gè)鄰接

30、點(diǎn)地址號(hào)頂點(diǎn)的第一個(gè)鄰接點(diǎn)地址*/ 鄰接表存儲(chǔ)結(jié)構(gòu)的圖鄰接表存儲(chǔ)結(jié)構(gòu)的圖起始頂點(diǎn)的序號(hào)（下標(biāo)）起始頂點(diǎn)的序號(hào)（下標(biāo)）while(p!=NULL) i=p-adjvex; /*i為鄰接頂點(diǎn)的序號(hào)（下標(biāo)）為鄰接頂點(diǎn)的序號(hào)（下標(biāo)）*/ if(visitedi=0) EnQueue(&Q, i); visitedi=1; p=p-next; /*找所有未訪問的鄰接點(diǎn)的循環(huán)找所有未訪問的鄰接點(diǎn)的循環(huán)*/ /*隊(duì)列循環(huán)隊(duì)列循環(huán)*/ /*函數(shù)結(jié)束函數(shù)結(jié)束*/按算法實(shí)現(xiàn)的按算法實(shí)現(xiàn)的bfs遍歷舉例：遍歷舉例：V0頂點(diǎn)出發(fā)遍歷結(jié)果（唯一）頂點(diǎn)出發(fā)遍歷結(jié)果（唯一） ：V0、 V1、 V4、 V3、 V2V2頂點(diǎn)出

31、發(fā)遍歷結(jié)果（唯一）頂點(diǎn)出發(fā)遍歷結(jié)果（唯一） ：V2、 V3、 V1、 V4、 V0V0V1V2V3V4無向圖：無向圖：鄰接表存儲(chǔ)結(jié)構(gòu)：鄰接表存儲(chǔ)結(jié)構(gòu)：V0V1V2V3V4012341403312403設(shè)計(jì)程序創(chuàng)建鄰接表存儲(chǔ)的無向圖，并用設(shè)計(jì)程序創(chuàng)建鄰接表存儲(chǔ)的無向圖，并用bfsbfs圖中頂圖中頂點(diǎn)信息并輸出：點(diǎn)信息并輸出：宏定義及數(shù)據(jù)類型：宏定義及數(shù)據(jù)類型：#include #include Queue.h /*循環(huán)隊(duì)列相關(guān)操作的定義文件循環(huán)隊(duì)列相關(guān)操作的定義文件*/#define MAX 20 /*圖頂點(diǎn)最多不超過圖頂點(diǎn)最多不超過20*/typedef int vextype; /*圖頂點(diǎn)為

32、圖頂點(diǎn)為int型型*/typedef struct arcnode int adjvex; struct arcnode *next; ArcNode; /*表結(jié)點(diǎn)類型表結(jié)點(diǎn)類型*/typedef struct vexnode vextype vertex;ArcNode *firstarc; VexNode; /*頂點(diǎn)結(jié)點(diǎn)類型頂點(diǎn)結(jié)點(diǎn)類型*/typedef struct VexNode adjlistMAX; /*頂點(diǎn)結(jié)點(diǎn)所在數(shù)組頂點(diǎn)結(jié)點(diǎn)所在數(shù)組*/ int vn, en; ALGraph; /*鄰接表存儲(chǔ)的圖類型鄰接表存儲(chǔ)的圖類型*/int visitedMAX; /*訪問標(biāo)記數(shù)組訪問標(biāo)記

33、數(shù)組*/函數(shù)定義：函數(shù)定義：void CreateGraph(ALGraph *g) /*創(chuàng)建圖創(chuàng)建圖*/ void visit(MGraph *g, int v) /*訪問圖中某個(gè)頂點(diǎn)訪問圖中某個(gè)頂點(diǎn)*/ void bfs(MGraph *g, int v) /*bfs遍歷圖遍歷圖*/ main() /*主函數(shù)主函數(shù)*/ ALGraph alg; /*mg為鄰接表圖結(jié)構(gòu)變量為鄰接表圖結(jié)構(gòu)變量/ int i, start; /*start開始頂點(diǎn)序號(hào)開始頂點(diǎn)序號(hào)*/ CreateGraph(&alg); for(i=0; ialg.vn; i+) /*訪問標(biāo)記數(shù)組置初值訪問標(biāo)記數(shù)組置初值0*/

34、 visitedi=0; scanf(%d, &start); bfs(&alg, start);l關(guān)于遍歷小結(jié)：關(guān)于遍歷小結(jié)：若圖是連通的或強(qiáng)連通的，則從圖中某一個(gè)若圖是連通的或強(qiáng)連通的，則從圖中某一個(gè)頂點(diǎn)出發(fā)可以訪問到圖中所有頂點(diǎn)；頂點(diǎn)出發(fā)可以訪問到圖中所有頂點(diǎn)；若圖是非連通的或非強(qiáng)連通圖，則需從圖中若圖是非連通的或非強(qiáng)連通圖，則需從圖中多個(gè)頂點(diǎn)出發(fā)搜索訪問，而每一次從一個(gè)新多個(gè)頂點(diǎn)出發(fā)搜索訪問，而每一次從一個(gè)新的起始點(diǎn)出發(fā)進(jìn)行搜索過程中得到的頂點(diǎn)訪的起始點(diǎn)出發(fā)進(jìn)行搜索過程中得到的頂點(diǎn)訪問序列恰為每個(gè)連通分量中的頂點(diǎn)集。問序列恰為每個(gè)連通分量中的頂點(diǎn)集。問題：如何通過遍歷算法，求一個(gè)非連通

35、圖的連問題：如何通過遍歷算法，求一個(gè)非連通圖的連同分量個(gè)數(shù)？同分量個(gè)數(shù)？int count (MGraph *g) int i, m=0; for(i=0; ivn; i+) if(visitedi=0) m+; dfs(g, i); return m; 生成樹定義生成樹定義l圖的遍歷過程中經(jīng)過的圖的遍歷過程中經(jīng)過的n個(gè)頂點(diǎn)個(gè)頂點(diǎn)n-1條邊條邊即為一即為一棵生成樹。棵生成樹。8.4 圖的應(yīng)用圖的應(yīng)用8.4.1 連通圖的最小生成樹連通圖的最小生成樹無向圖的應(yīng)用無向圖的應(yīng)用在無向連通圖在無向連通圖G G中，其一個(gè)極小連通子圖中，其一個(gè)極小連通子圖( (無回?zé)o回路路) )是是G G的生成樹，它含有圖

36、中全部的生成樹，它含有圖中全部n n個(gè)頂點(diǎn)個(gè)頂點(diǎn)，但，但只有只有n-1n-1條邊條邊，且不唯一。，且不唯一。深度優(yōu)先生成樹：按深度優(yōu)先遍歷生成的深度優(yōu)先生成樹：按深度優(yōu)先遍歷生成的生成樹生成樹c0c1c3c2c4c5例例c0c1c3c2c4c5c0c1c3c2c4c5c0c1c3c2c4c5廣度優(yōu)先生成樹：按廣度優(yōu)先遍歷生成的廣度優(yōu)先生成樹：按廣度優(yōu)先遍歷生成的生成樹生成樹非連通圖的生成森林非連通圖的生成森林V0V1V3V4V2V6V8V7V5V9（a）不連通的無向圖）不連通的無向圖G12V0V1V3V4V2V8V7V9V6V5（c）圖）圖G12的一個(gè)的一個(gè)BFS生成森林生成森林V0V1V3V

37、4V2V6V8V7V5V9（b）圖）圖G12的一個(gè)的一個(gè)DFS生成森林生成森林 要在要在 n 個(gè)城市間建立個(gè)城市間建立通訊網(wǎng)，如何在保證通訊網(wǎng)，如何在保證 n 個(gè)城市連通的前題下最節(jié)個(gè)城市連通的前題下最節(jié)省經(jīng)費(fèi)省經(jīng)費(fèi)? ABCDEF101015121287665無向網(wǎng)無向網(wǎng)G1ABCDEF10101276花費(fèi)：花費(fèi)：45ABCDEF1512865花費(fèi)：花費(fèi)：465ABCDEF107610花費(fèi)：花費(fèi)：38 要在要在 n 個(gè)城市間建立個(gè)城市間建立通訊網(wǎng)，如何在保證通訊網(wǎng)，如何在保證 n 個(gè)城市連通的前題下最節(jié)個(gè)城市連通的前題下最節(jié)省經(jīng)費(fèi)省經(jīng)費(fèi)? ABCDEF101015121287665這個(gè)問題實(shí)

38、際上是連通圖的最小生成樹問這個(gè)問題實(shí)際上是連通圖的最小生成樹問題。題。ABCDEF1010151212876655ABCDEF107610最小生成樹的定義最小生成樹的定義若圖若圖G G是帶權(quán)的無向連通圖（連通網(wǎng)），生成樹上各是帶權(quán)的無向連通圖（連通網(wǎng)），生成樹上各邊權(quán)值之和稱為生成樹的代價(jià)，邊權(quán)值之和稱為生成樹的代價(jià)，代價(jià)最小的生成樹代價(jià)最小的生成樹稱為最小生成樹；稱為最小生成樹；ln n個(gè)頂點(diǎn)、個(gè)頂點(diǎn)、n n-1-1條邊、權(quán)值之和最小。條邊、權(quán)值之和最小。1654327131791812752410連通網(wǎng)：連通網(wǎng)：1654321397510生成樹生成樹1：1654327139724生成樹生成

39、樹2：代價(jià)：代價(jià)：44代價(jià)：代價(jià)：60最小生成樹最小生成樹最小生成樹的應(yīng)用最小生成樹的應(yīng)用l集成電路布線集成電路布線l通訊線路布線通訊線路布線如何快速有效地構(gòu)造如何快速有效地構(gòu)造最小生成樹最小生成樹 構(gòu)造最小生成樹的準(zhǔn)則：構(gòu)造最小生成樹的準(zhǔn)則：l必須只使用該網(wǎng)絡(luò)中的邊來構(gòu)造最小生成樹；必須只使用該網(wǎng)絡(luò)中的邊來構(gòu)造最小生成樹；l必須使用且僅使用必須使用且僅使用n-1條邊來聯(lián)接網(wǎng)絡(luò)中的條邊來聯(lián)接網(wǎng)絡(luò)中的n個(gè)頂點(diǎn)個(gè)頂點(diǎn)一、一、Prim(普里姆普里姆)算法算法 1 1、算法思想、算法思想 設(shè)原連通網(wǎng)設(shè)原連通網(wǎng)G=(V, E)G=(V, E)，生成的最小生成樹，生成的最小生成樹T=(U, T=(U, T

40、E)TE)，則算法步驟如下：，則算法步驟如下：(1)(1)任選一個(gè)頂點(diǎn)任選一個(gè)頂點(diǎn)u u0 0放入放入U(xiǎn) U中，即初始中，即初始U=uU=u0 0 ，TE= TE= (2)(2)找連接找連接U U與與V-UV-U集合的一條權(quán)值最小的邊集合的一條權(quán)值最小的邊即找即找頂點(diǎn)頂點(diǎn)uU,uU,頂點(diǎn)頂點(diǎn)vV-UvV-U的權(quán)值最小的一條邊的權(quán)值最小的一條邊(u,v)E(u,v)E；并把頂點(diǎn)并把頂點(diǎn)v v加入到加入到U U中，邊中，邊(u,v) (u,v) 加入到加入到TETE中，中，即修改即修改U=U+v,TE=TE+(u,v)U=U+v,TE=TE+(u,v)(3)(3)轉(zhuǎn)到（轉(zhuǎn)到（2 2）重復(fù)執(zhí)行，直到

41、）重復(fù)執(zhí)行，直到U=VU=V結(jié)束結(jié)束ABCDEF101015121287665（a）無向網(wǎng)）無向網(wǎng)G1算法演示算法演示:Prim算法求解最小生成樹算法求解最小生成樹BCE101512（b）求解過程）求解過程67ABCDEF1010151212865（a）無向網(wǎng)）無向網(wǎng)G1算法演示算法演示:Prim算法求解最小生成樹算法求解最小生成樹CDEF101512765（b）求解過程）求解過程ABCDEF101015121287665 （a）無向網(wǎng)）無向網(wǎng)G1算法演示算法演示:Prim算法求解最小生成樹算法求解最小生成樹CDEF1015765（b）求解過程）求解過程6ABCDEF1010151212876

42、5 （a）無向網(wǎng)）無向網(wǎng)G1算法演示算法演示:Prim算法求解最小生成樹算法求解最小生成樹CEF1015765（b）求解過程）求解過程6ABCDEF10101512128765 （a）無向網(wǎng)）無向網(wǎng)G1算法演示算法演示:Prim算法求解最小生成樹算法求解最小生成樹CEF10157665（b）求解過程）求解過程ABCDEF101015121287665 （a）無向網(wǎng)）無向網(wǎng)G1算法演示算法演示:Prim算法求解最小生成樹算法求解最小生成樹CE1015765（b）求解過程）求解過程ABCDEF101015121287665 （a）無向網(wǎng)）無向網(wǎng)G1算法演示算法演示:Prim算法求解最小生成樹算法求

43、解最小生成樹CE1015765（b）求解過程）求解過程86ABCDEF101015121287665 （a）無向網(wǎng)）無向網(wǎng)G1算法演示算法演示:Prim算法求解最小生成樹算法求解最小生成樹CE10101575（b）求解過程）求解過程6ABCDEF101015121287665 （a）無向網(wǎng)）無向網(wǎng)G1算法演示算法演示:Prim算法求解最小生成樹算法求解最小生成樹E101075（b）求解過程）求解過程1567ABCDEF101015121287665 （a）無向網(wǎng)）無向網(wǎng)G1算法演示算法演示:Prim算法求解最小生成樹算法求解最小生成樹E1010125（b）求解過程）求解過程67ABCDEF10

44、1015121287665 （a）無向網(wǎng)）無向網(wǎng)G1算法演示算法演示:Prim算法求解最小生成樹算法求解最小生成樹最小生成樹最小生成樹E10105例1654326513566425131163141643142116432142516543214253Prim算法最小生成樹生成過程事例算法最小生成樹生成過程事例(從從1號(hào)頂點(diǎn)開始號(hào)頂點(diǎn)開始) 課堂練習(xí)：寫出如下連通網(wǎng)的最小生成樹過程課堂練習(xí)：寫出如下連通網(wǎng)的最小生成樹過程165432496102014510106165432495106最小生成樹最小生成樹1165432495106最小生成樹最小生成樹2最小生成樹最小生成樹不唯一！不唯一！i01

45、2345di.adj000000di.dist 01 58 定義一個(gè)結(jié)構(gòu)數(shù)組：定義一個(gè)結(jié)構(gòu)數(shù)組：struct cost int adj; int dist;d20;2 2、算法實(shí)現(xiàn)、算法實(shí)現(xiàn) 02315451839762說明：說明：i i數(shù)組下標(biāo)，又是圖中對應(yīng)數(shù)組下標(biāo)，又是圖中對應(yīng)頂點(diǎn)的序號(hào)頂點(diǎn)的序號(hào)di.adjdi.adj表示表示i i號(hào)頂點(diǎn)號(hào)頂點(diǎn)與生成樹中頂點(diǎn)集合與生成樹中頂點(diǎn)集合U U距離距離最小最小的的頂點(diǎn)頂點(diǎn)號(hào)（號(hào)（u u）di.distdi.dist表示表示i i號(hào)頂點(diǎn)號(hào)頂點(diǎn)與生成樹中與生成樹中adjadj頂點(diǎn)（頂點(diǎn)（u u號(hào)頂點(diǎn)號(hào)頂點(diǎn)）的）的距距離離，當(dāng)，當(dāng)dist=0dist=

46、0時(shí)表示時(shí)表示i i號(hào)頂點(diǎn)已到生成樹中。號(hào)頂點(diǎn)已到生成樹中。生成樹初始生成樹初始 選選0號(hào)頂點(diǎn)號(hào)頂點(diǎn)2 2、算法實(shí)現(xiàn)、算法實(shí)現(xiàn) i012345di.adj000000di.dist 01 58 02315451839762(1)(1)取取d d數(shù)組中數(shù)組中distdist0的最小值，則把的最小值，則把u=0, v=1,w=1送入生成樹，送入生成樹，其頂點(diǎn)集為：其頂點(diǎn)集為：0,1，并修改數(shù)組，并修改數(shù)組d的內(nèi)容的內(nèi)容i012345di.adj011000di.dist 002 58 生成樹初始生成樹初始 選選0號(hào)頂點(diǎn)號(hào)頂點(diǎn)uvw(2)(2)取取d d數(shù)組中數(shù)組中distdist0的最小值，則把的

47、最小值，則把u=1, v=2,w=2送入生成樹送入生成樹，其頂點(diǎn)集為：其頂點(diǎn)集為：0,1,20,1,2，并修改數(shù)組并修改數(shù)組d的內(nèi)容的內(nèi)容i012345di.adj011000di.dist 002 58 i012345di.adj012202di.dist 0007 56 i012345di.adj012202di.dist 0007 56 (3)(3)取取d d數(shù)組中數(shù)組中distdist0的最小值，則把的最小值，則把u=0, v=4,w=5送入生成樹送入生成樹，其頂點(diǎn)集為：其頂點(diǎn)集為：0,1,2,40,1,2,4，并修改數(shù)組并修改數(shù)組d的內(nèi)容的內(nèi)容i012345di.adj012442d

48、i.dist 0003 06 (4)(4)取取d d數(shù)組中數(shù)組中distdist0的最小值，則把的最小值，則把u=4, v=3,w=3送入生成樹送入生成樹，其頂點(diǎn)集為：其頂點(diǎn)集為：0,1,2,4,30,1,2,4,3，并修改數(shù)組并修改數(shù)組d的內(nèi)容的內(nèi)容i012345di.adj012442di.dist 0003 06 i012345di.adj012342di.dist 0000 06 i012345di.adj012342di.dist 0000 06 (5)(5)取取d d數(shù)組中數(shù)組中distdist0的最小值，則把的最小值，則把u=2, v=5,w=6送入生成樹送入生成樹，其頂點(diǎn)集為：

49、其頂點(diǎn)集為：0,1,2,4,3,50,1,2,4,3,5，并修改數(shù)組并修改數(shù)組d的內(nèi)容的內(nèi)容i012345di.adj012345di.dist 0000 00 無向網(wǎng)的建立：無向網(wǎng)的建立： #include #define INF 32767typedef struct int u, v, w; Tree; /*最小生成樹順序存儲(chǔ)元素類型最小生成樹順序存儲(chǔ)元素類型*/void CreateGraph(MGraph *g) int i, j, w, e; FILE *fp; /*文件指針文件指針fp*/ fp=fopen(graph.dat, r); /*打開數(shù)據(jù)文件打開數(shù)據(jù)文件*/ /*圖的

50、頂點(diǎn)數(shù)和邊數(shù)、頂點(diǎn)數(shù)據(jù)和邊的信息從文件獲取圖的頂點(diǎn)數(shù)和邊數(shù)、頂點(diǎn)數(shù)據(jù)和邊的信息從文件獲取*/ fscanf(fp,%d %d, &g-vn, &g-en); for(i=0;ivn;i+) /*鄰接矩陣初始化鄰接矩陣初始化*/ for(j=0;jvn;j+) /*對角線為對角線為0，其余為，其余為*/ if(i=j) g-arcij=0; else g-arcij=INF;02315451839762無向網(wǎng)的建立（續(xù)）：無向網(wǎng)的建立（續(xù)）： for(i=0;ivn;i+) g-vexi=A+i; /*頂點(diǎn)數(shù)據(jù)為頂點(diǎn)數(shù)據(jù)為A、B、C*/ for(e=0;een;e+) /*從文件讀取對應(yīng)邊信息，

51、即有邊的頂點(diǎn)序號(hào)及權(quán)值從文件讀取對應(yīng)邊信息，即有邊的頂點(diǎn)序號(hào)及權(quán)值*/ fscanf(fp, %d %d %d, &i,&j,&w)； g-arcij=w; g-arcji=w; fclose(fp); /*關(guān)閉文件關(guān)閉文件*/ /*結(jié)束函數(shù)結(jié)束函數(shù)*/0968035930767022018510文件文件graph.dat中中的內(nèi)容為：的內(nèi)容為：6 80 1 10 4 50 5 81 2 22 3 72 5 63 4 33 5 9無向網(wǎng)鄰接距陣的輸出：無向網(wǎng)鄰接距陣的輸出： void OutGraph(MGraph *g) int i, j; printf(n-Graph-n); printf

52、(n vn=%d t en=%d, g-vn, g-en); for(i=0;ivn;i+) for(j=0;jvn;j+) printf(%dt,g-arcij); printf(n); 0968035930767022018510輸出：輸出：-Graph-6 8primprim算法實(shí)現(xiàn)：算法實(shí)現(xiàn)： void Prim(MGraph *g, int v0, Tree E) int i,j, k, min; struct cost int adj; int dist; d20; for(i=0;ivn;i+) /*d數(shù)組初始化數(shù)組初始化*/ di.adj=v0; di.dist=g-arcv0

53、i; for(k=0; kvn-1; k+) /*求求vn-1條生成樹的邊條生成樹的邊*/ min=INF; j=-1; for(i=0; ivn; i+) /*找權(quán)值最小的邊找權(quán)值最小的邊*/ if(di.dist!=0 & di.distmin) j=i; min=di.dist; Ek.u=dj.adj; Ek.v=j; Ek.w=min; /*送入生成樹送入生成樹*/ dj.adj=j; dj.dist=0; /*修改新送入生成樹頂點(diǎn)的信息修改新送入生成樹頂點(diǎn)的信息*/primprim算法實(shí)現(xiàn)（續(xù)）：算法實(shí)現(xiàn)（續(xù)）： for(i=0; ivn; i+) /*修改數(shù)組修改數(shù)組d中數(shù)組中數(shù)

54、組*/ /*新加入到生成樹的新加入到生成樹的j頂點(diǎn)與頂點(diǎn)與i頂點(diǎn)邊的權(quán)值更小，則修改頂點(diǎn)邊的權(quán)值更小，則修改*/ if(di.dist!=0 & g-arcjiarcji; /*結(jié)束求生成樹的結(jié)束求生成樹的for */ /*結(jié)束函數(shù)結(jié)束函數(shù) */最小生成樹的輸出：最小生成樹的輸出： void OutTree(Tree E, int k) int i; printf(n spaning treen); for(i=0; ik; i+) /*生成樹生成樹E數(shù)組中有數(shù)組中有k條邊條邊*/ printf(n%c-%c-%d, Ei.u, Ei.v, Ei.w ); 輸出：輸出：spaning tree

55、0-1-1 1-2-2 0-4-5 4-3-32-5-6主函數(shù)：主函數(shù)： main( ) MGraph G; Tree E20; CreateGraph(&G); OutGraph(&G); Prim(&G,0,E); OutTree( E, G.vn-1 ); 二、二、 Kruskal（克魯斯卡爾）算法（克魯斯卡爾）算法 1 1、算法思想、算法思想 把圖的所有邊按其權(quán)值從小到大排成升序把圖的所有邊按其權(quán)值從小到大排成升序先把權(quán)值最小的邊加入生成樹先把權(quán)值最小的邊加入生成樹依次選取后面的邊，如該邊加到生成樹中，使生成依次選取后面的邊，如該邊加到生成樹中，使生成樹構(gòu)成回路，則舍棄該邊，否則該邊加

56、入到生成樹樹構(gòu)成回路，則舍棄該邊，否則該邊加入到生成樹中。中。重復(fù)上述過程，直到生成樹中包含重復(fù)上述過程，直到生成樹中包含n n 1 1條邊為止，條邊為止，此時(shí)即為最小生成樹。此時(shí)即為最小生成樹。例AFEDCB6314566425AFEDCB13254Kruskal算法最算法最小生成樹生成過程事例：小生成樹生成過程事例： AC10DF21AD32CF43BE44CD55BC56AB67CE68EF69KruskalKruskal算法練習(xí)算法練習(xí): :abcdegf195141827168213ae12dcbgf71485316217121819abcdegf195141827168213ae12dcbgf7148531621最小生成樹代價(jià)= 14+8+3+5+16+21 = 67 PrimPrim算法練習(xí)算法練習(xí): :8.4.2 拓?fù)渑判蛲負(fù)渑判蛴邢驘o環(huán)圖及其應(yīng)用有向無環(huán)圖及其應(yīng)用1、AOV網(wǎng)概念網(wǎng)概念在一個(gè)有向圖中，若用頂點(diǎn)表示活動(dòng)，有向邊表示活動(dòng)間在一個(gè)有向圖中，若用頂點(diǎn)表示活動(dòng)，有向邊表示活動(dòng)間先后關(guān)系，稱該有向圖叫做頂點(diǎn)活動(dòng)網(wǎng)絡(luò)，簡稱為先后關(guān)系，稱該有向圖叫做頂點(diǎn)活動(dòng)網(wǎng)絡(luò)，簡稱為AOV