C語言數(shù)據(jù)結(jié)構(gòu)第06講課件

1、C語言數(shù)據(jù)結(jié)構(gòu)第06講第第7 7章章 圖圖C語言數(shù)據(jù)結(jié)構(gòu)第06講知 識 點(diǎn)圖的邏輯結(jié)構(gòu)及基本術(shù)語圖的邏輯結(jié)構(gòu)及基本術(shù)語鄰接矩陣和鄰接表的存儲結(jié)構(gòu)和特點(diǎn)鄰接矩陣和鄰接表的存儲結(jié)構(gòu)和特點(diǎn)深度優(yōu)先搜索和廣度優(yōu)先搜索兩種遍歷算法深度優(yōu)先搜索和廣度優(yōu)先搜索兩種遍歷算法圖的連通性和生成樹的概念圖的連通性和生成樹的概念最短路徑的含義及求最短路徑的算法最短路徑的含義及求最短路徑的算法C語言數(shù)據(jù)結(jié)構(gòu)第06講難難 點(diǎn)點(diǎn)圖的遍歷圖的遍歷 最小生成樹最小生成樹 最短路徑最短路徑要要 求求熟練掌握以下內(nèi)容：熟練掌握以下內(nèi)容： 圖的存儲結(jié)構(gòu)圖的存儲結(jié)構(gòu) 圖的遍歷算法圖的遍歷算法了解以下內(nèi)容：了解以下內(nèi)容： 圖的最小生成樹

2、和求最小生成樹算法圖的最小生成樹和求最小生成樹算法 帶權(quán)有向圖的最短路徑問題帶權(quán)有向圖的最短路徑問題C語言數(shù)據(jù)結(jié)構(gòu)第06講7-1 7-1 圖的定義和術(shù)語圖的定義和術(shù)語7-2 7-2 圖的存儲表示圖的存儲表示7-3 7-3 圖的遍歷圖的遍歷7-4 7-4 圖的連通性圖的連通性7-5 7-5 最短路徑最短路徑小小 結(jié)結(jié)實(shí)驗實(shí)驗7 7 圖子系統(tǒng)圖子系統(tǒng)習(xí)題習(xí)題7 7C語言數(shù)據(jù)結(jié)構(gòu)第06講 圖（圖（GraphGraph）是一種比樹形結(jié)構(gòu)更復(fù)雜的非線性結(jié)構(gòu)。在）是一種比樹形結(jié)構(gòu)更復(fù)雜的非線性結(jié)構(gòu)。在圖形結(jié)構(gòu)中，每個結(jié)點(diǎn)都可以有多個直接前驅(qū)和多個直接后圖形結(jié)構(gòu)中，每個結(jié)點(diǎn)都可以有多個直接前驅(qū)和多個直接后繼

3、。繼。7-1 7-1 圖的定義和術(shù)語圖的定義和術(shù)語7-1-1 7-1-1 圖的定義圖的定義 圖（圖（GraphGraph）是由非空的頂點(diǎn)（）是由非空的頂點(diǎn)（VerticesVertices）集合和一個描）集合和一個描述頂點(diǎn)之間關(guān)系述頂點(diǎn)之間關(guān)系邊（邊（EdgesEdges）的有限集合組成的一種數(shù)據(jù)）的有限集合組成的一種數(shù)據(jù)結(jié)構(gòu)。可以用二元組定義為：結(jié)構(gòu)?？梢杂枚M定義為： G G（V V，E E） 其中，其中，G G表示一個圖，表示一個圖，V V是圖是圖G G中頂點(diǎn)的集合，中頂點(diǎn)的集合，E E是圖是圖G G中邊中邊的集合。的集合。C語言數(shù)據(jù)結(jié)構(gòu)第06講 圖圖7-1 無向圖無向圖G1 圖圖7-

4、2 有向圖有向圖G G2 2 V1V3V2V4V5V1V3V2V4 G1=（V，E） Vv1,v2,v3,v4,v5； E(v1,v2),(v1,v4),(v2,v3),(v3,v4), (v3,v5),(v2,v5)。(v(vi i,v,vj j) )表示頂點(diǎn)表示頂點(diǎn)v vi i和頂點(diǎn)和頂點(diǎn)v vj j之間有一之間有一條無向直接連線，也稱為邊。條無向直接連線，也稱為邊。G2=(V,E)V=v1,v2,v3,v4E=, 表示頂點(diǎn)表示頂點(diǎn)vi和頂點(diǎn)和頂點(diǎn)vj之間有一條之間有一條有向直接連線，也稱為弧。其中有向直接連線，也稱為弧。其中vi稱稱為弧尾，為弧尾，vj稱為弧頭。稱為弧頭。C語言數(shù)據(jù)結(jié)構(gòu)第

5、06講7-1-2 7-1-2 圖的相關(guān)術(shù)語圖的相關(guān)術(shù)語（1 1）無向圖（）無向圖（UndigraphUndigraph） 在一個圖中，如果每條邊都沒有方向（如圖在一個圖中，如果每條邊都沒有方向（如圖7-17-1），），則稱該圖為無向圖。則稱該圖為無向圖。（2 2）有向圖（）有向圖（DigraphDigraph） 在一個圖中，如果每條邊都有方向（如圖在一個圖中，如果每條邊都有方向（如圖7-27-2），則），則稱該圖為有向圖。稱該圖為有向圖。（3 3）無向完全圖）無向完全圖 在一個無向圖中，如果任意兩頂點(diǎn)都有一條直接邊相在一個無向圖中，如果任意兩頂點(diǎn)都有一條直接邊相連接，則稱該圖為無向完全圖?？梢?/p>

6、證明，在一個含有連接，則稱該圖為無向完全圖?？梢宰C明，在一個含有n n個頂點(diǎn)的無向完全圖中，有個頂點(diǎn)的無向完全圖中，有n (n-1)/2n (n-1)/2條邊。條邊。 C語言數(shù)據(jù)結(jié)構(gòu)第06講（4 4）有向完全圖）有向完全圖 在一個有向圖中，如果任意兩頂點(diǎn)之間都有方向互為在一個有向圖中，如果任意兩頂點(diǎn)之間都有方向互為相反的兩條弧相連接，則稱該圖為有向完全圖。在一個含相反的兩條弧相連接，則稱該圖為有向完全圖。在一個含有有n n個頂點(diǎn)的有向完全圖中，有個頂點(diǎn)的有向完全圖中，有n (n-1) n (n-1) 條弧。條弧。（5 5）稠密圖、稀疏圖）稠密圖、稀疏圖 我們稱邊數(shù)很多的圖為稠密圖；稱邊數(shù)很少的

7、圖為稀我們稱邊數(shù)很多的圖為稠密圖；稱邊數(shù)很少的圖為稀疏圖。疏圖。（6 6）頂點(diǎn)的度）頂點(diǎn)的度 在無在無向向圖中：一個頂點(diǎn)擁有的邊數(shù)，稱為該頂點(diǎn)的度。圖中：一個頂點(diǎn)擁有的邊數(shù)，稱為該頂點(diǎn)的度。記為記為TD (v)TD (v)。C語言數(shù)據(jù)結(jié)構(gòu)第06講 在有向圖中：在有向圖中： (a) 一個頂點(diǎn)擁有的弧頭的數(shù)目，稱為該頂點(diǎn)的入度，一個頂點(diǎn)擁有的弧頭的數(shù)目，稱為該頂點(diǎn)的入度， 記為記為ID (v)； (b) 一個頂點(diǎn)擁有的弧尾的數(shù)目，稱為該頂點(diǎn)的出度，一個頂點(diǎn)擁有的弧尾的數(shù)目，稱為該頂點(diǎn)的出度， 記為記為OD (v)； (c) 一個頂點(diǎn)度等于頂點(diǎn)的入度一個頂點(diǎn)度等于頂點(diǎn)的入度+出度，出度， 即：即：T

8、D (v)=ID (v)OD (v)。 在圖在圖7-1的的G1中有：中有： TD(v1)=2 TD(v2)=3 TD(v3)=3 TD(v4)=2 TD(v5)=2 在圖在圖7-2的的G2中有：中有： ID(v1)=1 OD(v1)=2 TD(v1)=3 ID(v2)=1 OD(v2)=0 TD(v2)=1 ID(v3)=1 OD(v3)=1 TD(v3)=2 ID(v4)=1 OD(v4)=1 TD(v4)=2C語言數(shù)據(jù)結(jié)構(gòu)第06講 可以證明，對于具有可以證明，對于具有n n個頂點(diǎn)、個頂點(diǎn)、e e條邊的圖，頂點(diǎn)條邊的圖，頂點(diǎn)v vi i的的度度TD (vTD (vi i) )與頂點(diǎn)的個數(shù)以及

9、邊的數(shù)目滿足關(guān)系：與頂點(diǎn)的個數(shù)以及邊的數(shù)目滿足關(guān)系：（7 7）權(quán)）權(quán) 圖的邊或弧有時具有與它有關(guān)的數(shù)據(jù)信息，這個數(shù)據(jù)圖的邊或弧有時具有與它有關(guān)的數(shù)據(jù)信息，這個數(shù)據(jù)信息就稱為權(quán)（信息就稱為權(quán)（WeightWeight）。）。21niViTDeACBD58697（8 8）網(wǎng)）網(wǎng)邊（或?。┥蠋?quán)邊（或?。┥蠋?quán)的圖稱為網(wǎng)（的圖稱為網(wǎng)（NetworkNetwork）。）。 如圖如圖7-37-3所示，就是一個無所示，就是一個無向網(wǎng)。如果邊是有方向的帶權(quán)向網(wǎng)。如果邊是有方向的帶權(quán)圖，則就是一個有向網(wǎng)。圖，則就是一個有向網(wǎng)。圖圖7-3 一個無向網(wǎng)示意一個無向網(wǎng)示意圖圖7-3 一個無向網(wǎng)示意一個無向網(wǎng)示意C語

10、言數(shù)據(jù)結(jié)構(gòu)第06講（9 9）路徑、路徑長度）路徑、路徑長度 頂點(diǎn)頂點(diǎn)v vi i到頂點(diǎn)到頂點(diǎn)v vj j之間的路徑是指頂點(diǎn)序列之間的路徑是指頂點(diǎn)序列v vi i,v,vi1i1,v,vi2i2, , , v , vimim,v,vj.j.。其中，（。其中，（v vi i,v,vi1i1），），(v(vi1i1,v,vi2i2) )，,(v(vimim,.v,.vj j) )分別為圖中的邊。路徑上邊的數(shù)目稱為路徑長度。分別為圖中的邊。路徑上邊的數(shù)目稱為路徑長度。 在圖在圖7-17-1的無向圖的無向圖G1G1中，中，v v1 1vv4 4vv3 3vv5 5與與v v1 1vv2 2vv5 5是是

11、從頂點(diǎn)從頂點(diǎn)v v1 1 到頂點(diǎn)到頂點(diǎn)v v5 5 的兩條路徑，路徑長度分別為的兩條路徑，路徑長度分別為3 3和和2 2。（1010）回路、簡單路徑、簡單回路）回路、簡單路徑、簡單回路 在一條路徑中，如果其起始點(diǎn)和終止點(diǎn)是同一頂點(diǎn)，則在一條路徑中，如果其起始點(diǎn)和終止點(diǎn)是同一頂點(diǎn)，則稱其為回路或者環(huán)。如果一條路徑上所有頂點(diǎn)除起始點(diǎn)和終稱其為回路或者環(huán)。如果一條路徑上所有頂點(diǎn)除起始點(diǎn)和終止點(diǎn)外彼此都是不同的，則稱該路徑為簡單路徑。止點(diǎn)外彼此都是不同的，則稱該路徑為簡單路徑。 在圖在圖7-17-1中，前面提到的中，前面提到的v v1 1到到v v5 5的兩條路徑都為簡單路的兩條路徑都為簡單路徑。除起

12、始點(diǎn)和終止點(diǎn)外，其他頂點(diǎn)不重復(fù)出現(xiàn)的回路稱為徑。除起始點(diǎn)和終止點(diǎn)外，其他頂點(diǎn)不重復(fù)出現(xiàn)的回路稱為簡單回路，或者簡單環(huán)。如圖簡單回路，或者簡單環(huán)。如圖7-27-2中的中的v v1 1vv3 3vv4 4vv1 1。C語言數(shù)據(jù)結(jié)構(gòu)第06講（1111）子圖）子圖 對于圖對于圖G=G=（V V，E E），），G=G=（VV，EE），若存在），若存在VV是是V V的子集的子集 ，EE是是E E的子集的子集 ，則稱圖，則稱圖GG是是G G的一個子圖。的一個子圖。 圖圖7-47-4示出了示出了G G1 1和和G G2 2的子圖。的子圖。 圖圖7-4 圖圖G1和和G2的兩個子圖示意的兩個子圖示意 (a) G1

13、的子圖的子圖 (b) G2的子圖的子圖 V1V3V2V1V3V2V4V5V1V3V2V4V5 圖圖7-1 無向圖無向圖G1C語言數(shù)據(jù)結(jié)構(gòu)第06講（1212）連通圖、連通分量）連通圖、連通分量 在無向圖中，如果從一個頂點(diǎn)在無向圖中，如果從一個頂點(diǎn)v vi i到另一個頂點(diǎn)到另一個頂點(diǎn)v vj j(ij)(ij)有路徑，則稱頂點(diǎn)有路徑，則稱頂點(diǎn)v vi i和和v vj j是連通的。任意兩頂點(diǎn)都是連通的是連通的。任意兩頂點(diǎn)都是連通的圖稱為連通圖。無向圖的極大連通子圖稱為連通分量。圖圖稱為連通圖。無向圖的極大連通子圖稱為連通分量。圖7-5 (a)7-5 (a)中有兩個連通分量，如圖中有兩個連通分量，如圖

14、7-5 (b)7-5 (b)所示。所示。AEBFCDAEBFCD (a) 無向圖無向圖G3 (b) G3的兩個連通分量的兩個連通分量 圖圖7-5 無向圖及連通分量示意無向圖及連通分量示意C語言數(shù)據(jù)結(jié)構(gòu)第06講（13）強(qiáng)連通圖、強(qiáng)連通分量）強(qiáng)連通圖、強(qiáng)連通分量 對于有向圖來說，若圖中任意一對對于有向圖來說，若圖中任意一對頂點(diǎn)頂點(diǎn)vi 和和vj(ij)均有從一個頂點(diǎn)均有從一個頂點(diǎn)vi到另一到另一個頂點(diǎn)個頂點(diǎn)vj有路徑，也有從有路徑，也有從vj到到vi的路徑，的路徑，則稱該有向圖是強(qiáng)連通圖。有向圖的極則稱該有向圖是強(qiáng)連通圖。有向圖的極大強(qiáng)連通子圖稱為強(qiáng)連通分量。大強(qiáng)連通子圖稱為強(qiáng)連通分量。 圖圖7-

15、2中有兩個強(qiáng)連通分量，分別是中有兩個強(qiáng)連通分量，分別是v1,v2,v3和和v4，如圖，如圖7-6所示。所示。（14）生成樹）生成樹 連通圖連通圖G的一個子圖如果是一棵包含的一個子圖如果是一棵包含G的所有頂點(diǎn)的樹，的所有頂點(diǎn)的樹，則該子圖稱為則該子圖稱為G的生成樹（的生成樹（Spanning Tree）。在生成樹中添）。在生成樹中添加任意一條屬于原圖中的邊必定會產(chǎn)生回路，因為新添加的加任意一條屬于原圖中的邊必定會產(chǎn)生回路，因為新添加的邊使其所依附的兩個頂點(diǎn)之間有了第二條路徑。若生成樹中邊使其所依附的兩個頂點(diǎn)之間有了第二條路徑。若生成樹中減少任意一條邊，則必然成為非連通的。減少任意一條邊，則必然成

16、為非連通的。n個頂點(diǎn)的生成樹具個頂點(diǎn)的生成樹具有有n-1條邊。條邊。V1V3V2V4圖圖7-6 有向圖有向圖G2的兩個的兩個 強(qiáng)連通分量示意強(qiáng)連通分量示意C語言數(shù)據(jù)結(jié)構(gòu)第06講7-1-3 圖的基本操作圖的基本操作 圖的基本操作有：圖的基本操作有：（1）CreatGraph（G）輸入圖）輸入圖G的頂點(diǎn)和邊，建立圖的頂點(diǎn)和邊，建立圖G的存儲。的存儲。（2）DFSTraverse（G，v）在圖）在圖G中，從頂點(diǎn)中，從頂點(diǎn)v出發(fā)深度出發(fā)深度優(yōu)先遍歷圖優(yōu)先遍歷圖G。（3）BFSTtaverse（G，v）在圖）在圖G中，從頂點(diǎn)中，從頂點(diǎn)v出發(fā)廣度出發(fā)廣度優(yōu)先遍歷圖優(yōu)先遍歷圖G。 圖的存儲結(jié)構(gòu)比較多。對于圖

17、的存儲結(jié)構(gòu)的選擇取決圖的存儲結(jié)構(gòu)比較多。對于圖的存儲結(jié)構(gòu)的選擇取決于具體的應(yīng)用和需要進(jìn)行的運(yùn)算。于具體的應(yīng)用和需要進(jìn)行的運(yùn)算。 下面介紹幾種常用的圖的存儲結(jié)構(gòu)。下面介紹幾種常用的圖的存儲結(jié)構(gòu)。C語言數(shù)據(jù)結(jié)構(gòu)第06講 鄰接矩陣是表示頂點(diǎn)之間相鄰關(guān)系的矩陣。鄰接矩陣是表示頂點(diǎn)之間相鄰關(guān)系的矩陣。 假設(shè)圖假設(shè)圖G（V，E）有）有n個頂點(diǎn)，即個頂點(diǎn)，即Vv0,v1,vn-1，則，則G的鄰接矩陣是具有如下性質(zhì)的的鄰接矩陣是具有如下性質(zhì)的n階方陣：階方陣： 1 若若(vi,vj)或或是是E(G)中的邊中的邊 Aij= 0 若若(vi,vj)或或不是不是E(G)中的邊中的邊 若若G是網(wǎng)，則鄰接矩陣可定義為：

18、是網(wǎng)，則鄰接矩陣可定義為： wij 若若(vi,vj)或或是是E(G)中的邊中的邊 Aij= 0或或 若若(vi,vj)或或不是不是E(G)中的邊中的邊 其中，其中，wij表示邊表示邊(vi,vj)或或上的權(quán)值（如圖上的權(quán)值（如圖7-3）；）；表示一個計算機(jī)允許的、大于所有邊上權(quán)值的數(shù)。表示一個計算機(jī)允許的、大于所有邊上權(quán)值的數(shù)。C語言數(shù)據(jù)結(jié)構(gòu)第06講 用鄰接矩陣表示法如圖用鄰接矩陣表示法如圖7-77-7所示；用鄰接矩陣表示法所示；用鄰接矩陣表示法如圖如圖7-87-8所示。所示。C語言數(shù)據(jù)結(jié)構(gòu)第06講 圖的鄰接矩陣具有以下性質(zhì)：圖的鄰接矩陣具有以下性質(zhì)：（1 1）無向圖的鄰接矩陣一定是一個對稱

19、矩陣。因此，在具體）無向圖的鄰接矩陣一定是一個對稱矩陣。因此，在具體存放鄰接矩陣時只需存放上（或下）三角矩陣的元素即可。存放鄰接矩陣時只需存放上（或下）三角矩陣的元素即可。（2 2）對于無向圖，鄰接矩陣的第）對于無向圖，鄰接矩陣的第i i行（或第行（或第i i列）非零元素列）非零元素（或非（或非元素）的個數(shù)正好是第元素）的個數(shù)正好是第i i個頂點(diǎn)的度個頂點(diǎn)的度TD(vTD(vi i) )。（3 3）對于有向圖，鄰接矩陣的第）對于有向圖，鄰接矩陣的第i i行（或第行（或第i i列）非零元素列）非零元素（或非（或非元素）的個數(shù)正好是第元素）的個數(shù)正好是第i i個頂點(diǎn)的出度個頂點(diǎn)的出度OD(vOD(

20、vi i) )（或入（或入度度ID(vID(vi i) )）。）。（4 4）用鄰接矩陣方法存儲圖，很容易確定圖中任意兩個頂點(diǎn)）用鄰接矩陣方法存儲圖，很容易確定圖中任意兩個頂點(diǎn)之間是否有邊相連；但是，要確定圖中有多少條邊，則必須之間是否有邊相連；但是，要確定圖中有多少條邊，則必須按行、按列對每個元素進(jìn)行檢測，所花費(fèi)的時間代價很大。按行、按列對每個元素進(jìn)行檢測，所花費(fèi)的時間代價很大。這是用鄰接矩陣存儲圖的局限性。這是用鄰接矩陣存儲圖的局限性。C語言數(shù)據(jù)結(jié)構(gòu)第06講 圖的鄰接矩陣存儲的描述如下：圖的鄰接矩陣存儲的描述如下：#define MAXLEN 10typedef struct char ve

21、xsMAXLEN; int edgesMAXLENMAXLEN; int n,e; MGraph; C語言數(shù)據(jù)結(jié)構(gòu)第06講 建立一個圖的鄰接矩陣存儲的算法如下：建立一個圖的鄰接矩陣存儲的算法如下：void CreateMGraph(MGraph *G) int i,j,k; char ch1,ch2; printf(請輸入頂點(diǎn)數(shù)和邊數(shù)請輸入頂點(diǎn)數(shù)和邊數(shù)(輸入格式為輸入格式為:頂點(diǎn)數(shù)頂點(diǎn)數(shù),邊數(shù)邊數(shù)):n); scanf(%d,%d,&(G-n),&(G-e); printf(請輸入頂點(diǎn)信息請輸入頂點(diǎn)信息(頂點(diǎn)號頂點(diǎn)號)每個頂點(diǎn)以回車作為結(jié)束每個頂點(diǎn)以回車作為結(jié)束:n); for

22、(i=0;in;i+) getchar(); scanf (%c,&(G-vexsi); for(i=0;in;i+) for(j=0;jn;j+) G-edgesij=0;C語言數(shù)據(jù)結(jié)構(gòu)第06講printf (請輸入每條邊對應(yīng)的兩個頂點(diǎn)的序號請輸入每條邊對應(yīng)的兩個頂點(diǎn)的序號(輸入格式為輸入格式為:i,j):n); for(k=0;ke;k+) getchar(); printf (請輸入第請輸入第%d條邊的頂點(diǎn)序號：條邊的頂點(diǎn)序號：,k+1); scanf (%c,%c,&ch1,&ch2); for (i=0;ch1!=G-vexsi;i+); for (j=0;c

23、h2!=G-vexsj;j+);G-edgesij=1; C語言數(shù)據(jù)結(jié)構(gòu)第06講7-2-2 7-2-2 鄰接表鄰接表 鄰接表鄰接表(Adjacency List)是圖的一種順序存儲與鏈?zhǔn)酱媸菆D的一種順序存儲與鏈?zhǔn)酱鎯Y(jié)合的存儲方法。鄰接表表示法類似于樹的孩子鏈表表儲結(jié)合的存儲方法。鄰接表表示法類似于樹的孩子鏈表表示法。就是對于圖示法。就是對于圖G中的每個頂點(diǎn)中的每個頂點(diǎn)vi，該方法將所有鄰接，該方法將所有鄰接于于vi的頂點(diǎn)的頂點(diǎn)vj鏈成一個單鏈表，這個單鏈表就稱為頂點(diǎn)鏈成一個單鏈表，這個單鏈表就稱為頂點(diǎn)vi的鄰接表。再將所有點(diǎn)的鄰接表表頭放到數(shù)組中，就構(gòu)成的鄰接表。再將所有點(diǎn)的鄰接表表頭放到數(shù)

24、組中，就構(gòu)成了圖的鄰接表。了圖的鄰接表。 在鄰接表表示中有兩種結(jié)點(diǎn)結(jié)構(gòu)，如圖在鄰接表表示中有兩種結(jié)點(diǎn)結(jié)構(gòu)，如圖7-9所示。所示。 頂點(diǎn)域頂點(diǎn)域 邊表頭指針邊表頭指針 鄰接點(diǎn)域鄰接點(diǎn)域 指針域指針域 頂點(diǎn)表頂點(diǎn)表 邊表邊表 圖圖7-9 鄰接矩陣表示的結(jié)點(diǎn)結(jié)構(gòu)鄰接矩陣表示的結(jié)點(diǎn)結(jié)構(gòu)vertexfirstedgeadjvexnextC語言數(shù)據(jù)結(jié)構(gòu)第06講 一種是頂點(diǎn)表的結(jié)點(diǎn)結(jié)構(gòu)，它由頂點(diǎn)域（一種是頂點(diǎn)表的結(jié)點(diǎn)結(jié)構(gòu)，它由頂點(diǎn)域（vertex）和）和指向第一條鄰接邊的指針域（指向第一條鄰接邊的指針域（firstedge）構(gòu)成，另一種是）構(gòu)成，另一種是邊表結(jié)點(diǎn)，它由鄰接點(diǎn)域邊表結(jié)點(diǎn)，它由鄰接點(diǎn)域(adjv

25、ex)和指向下一條鄰接邊的和指向下一條鄰接邊的指針域指針域(next)構(gòu)成。對于網(wǎng)的邊表需再增設(shè)一個存儲邊上構(gòu)成。對于網(wǎng)的邊表需再增設(shè)一個存儲邊上信息（如權(quán)值等）的域（信息（如權(quán)值等）的域（info），網(wǎng)的邊表結(jié)構(gòu)如圖），網(wǎng)的邊表結(jié)構(gòu)如圖7-10所示。所示。 鄰接點(diǎn)域鄰接點(diǎn)域 邊上信息邊上信息 指針域指針域 圖圖7-10 網(wǎng)的邊表結(jié)構(gòu)網(wǎng)的邊表結(jié)構(gòu)adjvex infonextC語言數(shù)據(jù)結(jié)構(gòu)第06講 圖圖7-11給出無向圖給出無向圖7-7對應(yīng)的鄰接表表示。對應(yīng)的鄰接表表示。 鄰接表表示形式描述如下：鄰接表表示形式描述如下：C語言數(shù)據(jù)結(jié)構(gòu)第06講define MAXLEN 10 / 最大頂點(diǎn)數(shù)為最

26、大頂點(diǎn)數(shù)為10typedef struct node / 邊表結(jié)點(diǎn)邊表結(jié)點(diǎn) int adjvex; / 鄰接點(diǎn)域鄰接點(diǎn)域 struct node * next; / 指向下一個鄰接點(diǎn)的指針域指向下一個鄰接點(diǎn)的指針域 /若要表示邊上信息，則應(yīng)增加一個數(shù)據(jù)域若要表示邊上信息，則應(yīng)增加一個數(shù)據(jù)域info EdgeNode; typedef struct vnode / 頂點(diǎn)表結(jié)點(diǎn)頂點(diǎn)表結(jié)點(diǎn) VertexType vertex; / 頂點(diǎn)域頂點(diǎn)域 EdgeNode * firstedge; / 邊表頭指針邊表頭指針 VertexNode; typedef VertexNode AdjListMAXLE

27、N; / AdjList是鄰接表類型是鄰接表類型typedef struct AdjList adjlist; / 接表接表 int n,e; / 頂點(diǎn)數(shù)和邊數(shù)頂點(diǎn)數(shù)和邊數(shù) ALGraph; / ALGraph是以鄰接表方式存儲的圖類型是以鄰接表方式存儲的圖類型C語言數(shù)據(jù)結(jié)構(gòu)第06講 建立一個有向圖的鄰接表存儲的算法如下：建立一個有向圖的鄰接表存儲的算法如下： void CreateGraphAL (ALGraph *G) int i,j,k; EdgeNode * s; printf(“請輸入頂點(diǎn)數(shù)和邊數(shù)請輸入頂點(diǎn)數(shù)和邊數(shù)(輸入格式為輸入格式為:頂點(diǎn)數(shù)頂點(diǎn)數(shù),邊數(shù)邊數(shù)) ：n); scanf

28、(%d,%d,&(G-n),&(G-e); / 讀入頂點(diǎn)數(shù)和邊數(shù)讀入頂點(diǎn)數(shù)和邊數(shù) printf(請輸入頂點(diǎn)請輸入頂點(diǎn)(格式為格式為:頂點(diǎn)號頂點(diǎn)號)以回車作為結(jié)束以回車作為結(jié)束:n); for (i=0;in;i+) / 立有立有n個頂點(diǎn)的頂點(diǎn)表個頂點(diǎn)的頂點(diǎn)表 scanf(n%c,&(G-adjlisti.vertex); / 讀入頂點(diǎn)信息讀入頂點(diǎn)信息 G-adjlisti.firstedge=NULL; / 點(diǎn)的邊表頭指針設(shè)為空點(diǎn)的邊表頭指針設(shè)為空 printf(請輸入邊的信息請輸入邊的信息(輸入格式為輸入格式為:i,j)：n); for (k=0;ke;k+) / 建

29、立邊表建立邊表 scanf(“n%d,%d”,&i,&j); / 讀入邊讀入邊的頂點(diǎn)對應(yīng)序號的頂點(diǎn)對應(yīng)序號 s=new EdgeNode; / 生成新邊表結(jié)點(diǎn)生成新邊表結(jié)點(diǎn)s s-adjvex=j; / 鄰接點(diǎn)序號為鄰接點(diǎn)序號為j s-next=G-adjlisti.firstedge; / 新邊表插入到頂點(diǎn)邊表頭部新邊表插入到頂點(diǎn)邊表頭部 G-adjlisti.firstedge=s; C語言數(shù)據(jù)結(jié)構(gòu)第06講 若無向圖中有若無向圖中有n 個頂點(diǎn)、個頂點(diǎn)、e條邊，則它的鄰接表需條邊，則它的鄰接表需n個頭個頭結(jié)點(diǎn)和結(jié)點(diǎn)和2e個表結(jié)點(diǎn)。顯然，在邊稀疏個表結(jié)點(diǎn)。顯然，在邊稀疏(en(

30、n-1)/2)的情況下，的情況下，用鄰接表表示圖比鄰接矩陣節(jié)省存儲空間，當(dāng)和邊相關(guān)的信用鄰接表表示圖比鄰接矩陣節(jié)省存儲空間，當(dāng)和邊相關(guān)的信息較多時更是如此。息較多時更是如此。 在無向圖的鄰接表中，頂點(diǎn)在無向圖的鄰接表中，頂點(diǎn)vi的度恰為第的度恰為第i個鏈表中的結(jié)個鏈表中的結(jié)點(diǎn)數(shù)；但在有向圖中，第點(diǎn)數(shù)；但在有向圖中，第i個鏈表中的結(jié)點(diǎn)個數(shù)只是頂點(diǎn)個鏈表中的結(jié)點(diǎn)個數(shù)只是頂點(diǎn)vi的的出度。如果要求入度，則必須遍歷整個鄰接表才能得到結(jié)果。出度。如果要求入度，則必須遍歷整個鄰接表才能得到結(jié)果。有時，為了便于確定頂點(diǎn)的入度或以頂點(diǎn)有時，為了便于確定頂點(diǎn)的入度或以頂點(diǎn)vi為頭的弧，可以為頭的弧，可以建立一個

31、有向圖的逆鄰接表，即對每個頂點(diǎn)建立一個有向圖的逆鄰接表，即對每個頂點(diǎn)vi 建立一個鏈接，建立一個鏈接，以以vi為弧頭的弧的鏈表。例如圖為弧頭的弧的鏈表。例如圖7-12所示為有向圖所示為有向圖G2（圖（圖7-2）的鄰接表和逆鄰接表。）的鄰接表和逆鄰接表。C語言數(shù)據(jù)結(jié)構(gòu)第06講 在建立鄰接表或逆鄰接表時，若輸入的頂點(diǎn)信息即為在建立鄰接表或逆鄰接表時，若輸入的頂點(diǎn)信息即為頂點(diǎn)的編號，則建立鄰接表的復(fù)雜度為頂點(diǎn)的編號，則建立鄰接表的復(fù)雜度為O（n+e），否則，），否則，需要通過查找才能得到頂點(diǎn)在圖中位置，則時間復(fù)雜度為需要通過查找才能得到頂點(diǎn)在圖中位置，則時間復(fù)雜度為O（n*e）。）。 C語言數(shù)據(jù)結(jié)構(gòu)

32、第06講 圖的遍歷（圖的遍歷（traversing graph）是指從圖中的某一頂點(diǎn)出）是指從圖中的某一頂點(diǎn)出發(fā)，對圖中的所有頂點(diǎn)訪問一次，而且僅訪問一次。圖的遍發(fā)，對圖中的所有頂點(diǎn)訪問一次，而且僅訪問一次。圖的遍歷是圖的一種基本操作。由于圖結(jié)構(gòu)本身的復(fù)雜性，所以圖歷是圖的一種基本操作。由于圖結(jié)構(gòu)本身的復(fù)雜性，所以圖的遍歷操作也較復(fù)雜，主要表現(xiàn)在以下四個方面：的遍歷操作也較復(fù)雜，主要表現(xiàn)在以下四個方面：（1）在圖結(jié)構(gòu)中，每一個結(jié)點(diǎn)的地位都是相同的，沒有一）在圖結(jié)構(gòu)中，每一個結(jié)點(diǎn)的地位都是相同的，沒有一個個“自然自然”的首結(jié)點(diǎn)，圖中任意一個頂點(diǎn)都可作為訪問的起的首結(jié)點(diǎn)，圖中任意一個頂點(diǎn)都可作為訪

33、問的起始結(jié)點(diǎn)。始結(jié)點(diǎn)。（2）在非連通圖中，從一個頂點(diǎn)出發(fā)，只能夠訪問它所在）在非連通圖中，從一個頂點(diǎn)出發(fā)，只能夠訪問它所在的連通分量上的所有頂點(diǎn)，因此，還需考慮如何訪問圖中其的連通分量上的所有頂點(diǎn)，因此，還需考慮如何訪問圖中其余的連通分量。余的連通分量。（3）在圖結(jié)構(gòu)中，如果有回路存在，那么一個頂點(diǎn)被訪問）在圖結(jié)構(gòu)中，如果有回路存在，那么一個頂點(diǎn)被訪問之后，有可能沿回路又回到該頂點(diǎn)。之后，有可能沿回路又回到該頂點(diǎn)。（4）在圖中，一個頂點(diǎn)可以和其它多個頂點(diǎn)相連，當(dāng)這個）在圖中，一個頂點(diǎn)可以和其它多個頂點(diǎn)相連，當(dāng)這個頂點(diǎn)訪問過后，就要考慮如何選取下一個要訪問的頂點(diǎn)。頂點(diǎn)訪問過后，就要考慮如何選取下

34、一個要訪問的頂點(diǎn)。C語言數(shù)據(jù)結(jié)構(gòu)第06講7-3-1 深度優(yōu)先搜索深度優(yōu)先搜索 深度優(yōu)先搜索（深度優(yōu)先搜索（Depth-Fisrst Search）遍歷類似于樹的先）遍歷類似于樹的先根遍歷，是樹的先根遍歷的推廣。根遍歷，是樹的先根遍歷的推廣。 假設(shè)初始狀態(tài)是圖中所有頂點(diǎn)未曾被訪問，則深度優(yōu)先假設(shè)初始狀態(tài)是圖中所有頂點(diǎn)未曾被訪問，則深度優(yōu)先搜索可從圖中某個頂點(diǎn)發(fā)搜索可從圖中某個頂點(diǎn)發(fā)v出發(fā)，首先訪問此頂點(diǎn)，然后任出發(fā)，首先訪問此頂點(diǎn)，然后任選一個選一個v的未被訪問的鄰接點(diǎn)的未被訪問的鄰接點(diǎn)w出發(fā)，繼續(xù)進(jìn)行深度優(yōu)先搜出發(fā)，繼續(xù)進(jìn)行深度優(yōu)先搜索，直到圖中所有和索，直到圖中所有和v路徑相通的頂點(diǎn)都被訪問

35、到；若此時路徑相通的頂點(diǎn)都被訪問到；若此時圖中還有頂點(diǎn)未被訪問到，則另選一個未被訪問的頂點(diǎn)作為圖中還有頂點(diǎn)未被訪問到，則另選一個未被訪問的頂點(diǎn)作為起始點(diǎn)，重復(fù)上面的做法，直至圖中所有的頂點(diǎn)都被訪問。起始點(diǎn)，重復(fù)上面的做法，直至圖中所有的頂點(diǎn)都被訪問。V1V5V2V4V8V3V6V7圖圖7-13 無向圖無向圖G5 以圖以圖7-13的無向圖的無向圖G5為例，為例，其深度優(yōu)先搜索得到的頂點(diǎn)訪問其深度優(yōu)先搜索得到的頂點(diǎn)訪問序列為：序列為： v1 v2 v4 v8 v5 v3 v6 、 v7C語言數(shù)據(jù)結(jié)構(gòu)第06講 顯然，以上方法是一個遞歸的過程。為了在遍歷過程中顯然，以上方法是一個遞歸的過程。為了在遍歷

36、過程中便于區(qū)分頂點(diǎn)是否已被訪問，需附設(shè)訪問標(biāo)志數(shù)組便于區(qū)分頂點(diǎn)是否已被訪問，需附設(shè)訪問標(biāo)志數(shù)組visited0:n-1, ，其初值為，其初值為FALSE ，一旦某個頂點(diǎn)被訪問，一旦某個頂點(diǎn)被訪問，則其相應(yīng)的分量置為則其相應(yīng)的分量置為TRUE。 從圖的某一點(diǎn)從圖的某一點(diǎn)v出發(fā)，遞歸地進(jìn)行深度優(yōu)先遍歷的過程如出發(fā)，遞歸地進(jìn)行深度優(yōu)先遍歷的過程如下面算法所示。下面算法所示。 void DFSTraverseM(MGraph *G) int i; for(i=0;in;i+) visitedi=FALSE; / FALSE在在c語言中定義為語言中定義為0，以下同，以下同 for(i=0;in;i+)

37、if (!visitedi) DFSM(G,i); C語言數(shù)據(jù)結(jié)構(gòu)第06講void DFSM(MGraph *G,int i) int j; printf (tt深度優(yōu)先遍歷結(jié)點(diǎn)深度優(yōu)先遍歷結(jié)點(diǎn): 結(jié)點(diǎn)結(jié)點(diǎn)%cn,G-vexsi); visitedi=TRUE; / TRUE在在c語言中定義為語言中定義為1，以下同，以下同 for (j=0;jn;j+) if (G-edgesij=1&!visitedj)DFSM(G,j); 在遍歷時，對圖中每個頂點(diǎn)至多調(diào)用一次在遍歷時，對圖中每個頂點(diǎn)至多調(diào)用一次DFSM 函數(shù)，函數(shù)，因為一旦某個頂點(diǎn)被標(biāo)志成已被訪問，就不再從它出發(fā)進(jìn)行因為一旦某個頂

38、點(diǎn)被標(biāo)志成已被訪問，就不再從它出發(fā)進(jìn)行搜索。因此，遍歷圖的過程實(shí)質(zhì)上是對每個頂點(diǎn)查找其鄰接搜索。因此，遍歷圖的過程實(shí)質(zhì)上是對每個頂點(diǎn)查找其鄰接點(diǎn)的過程。其耗費(fèi)的時間則取決于所采用的存儲結(jié)構(gòu)。當(dāng)用點(diǎn)的過程。其耗費(fèi)的時間則取決于所采用的存儲結(jié)構(gòu)。當(dāng)用二維數(shù)組表示鄰接矩陣圖的存儲結(jié)構(gòu)時，查找每個頂點(diǎn)的鄰二維數(shù)組表示鄰接矩陣圖的存儲結(jié)構(gòu)時，查找每個頂點(diǎn)的鄰接點(diǎn)所需時間為接點(diǎn)所需時間為O(n2) ，其中，其中n為圖中頂點(diǎn)數(shù)。為圖中頂點(diǎn)數(shù)。C語言數(shù)據(jù)結(jié)構(gòu)第06講 當(dāng)以鄰接表作圖的存儲結(jié)構(gòu)時，找鄰接點(diǎn)所需時間為當(dāng)以鄰接表作圖的存儲結(jié)構(gòu)時，找鄰接點(diǎn)所需時間為O(e)，其中，其中e為無向圖中邊的數(shù)或有向圖中弧的

39、數(shù)。由此，為無向圖中邊的數(shù)或有向圖中弧的數(shù)。由此，當(dāng)以鄰接表作存儲結(jié)構(gòu)時，深度優(yōu)先搜索遍歷圖的時間復(fù)雜當(dāng)以鄰接表作存儲結(jié)構(gòu)時，深度優(yōu)先搜索遍歷圖的時間復(fù)雜度為度為O(n+e) 。 7-3-2廣度優(yōu)先搜索廣度優(yōu)先搜索 廣度優(yōu)先搜索廣度優(yōu)先搜索 遍歷類似于樹的按層次遍歷。遍歷類似于樹的按層次遍歷。 假設(shè)從圖中某頂點(diǎn)假設(shè)從圖中某頂點(diǎn)v出發(fā)，在訪問了出發(fā)，在訪問了v之后依次訪問之后依次訪問v的各的各個未曾訪問過的鄰接點(diǎn)，然后分別從這些鄰接點(diǎn)出發(fā)依次訪個未曾訪問過的鄰接點(diǎn)，然后分別從這些鄰接點(diǎn)出發(fā)依次訪問它們的鄰接點(diǎn)，并使問它們的鄰接點(diǎn)，并使“先被訪問的頂點(diǎn)的鄰接點(diǎn)先被訪問的頂點(diǎn)的鄰接點(diǎn)”先于先于“后被

40、訪問的頂點(diǎn)的鄰接點(diǎn)后被訪問的頂點(diǎn)的鄰接點(diǎn)”被訪問，直至圖中所有已被訪被訪問，直至圖中所有已被訪問的頂點(diǎn)的鄰接點(diǎn)都被訪問到。若此時圖中尚有頂點(diǎn)未被訪問的頂點(diǎn)的鄰接點(diǎn)都被訪問到。若此時圖中尚有頂點(diǎn)未被訪問，則另選圖中一個未曾被訪問的頂點(diǎn)作起始點(diǎn)，重復(fù)上述問，則另選圖中一個未曾被訪問的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問到為止。換句話說，廣度過程，直至圖中所有頂點(diǎn)都被訪問到為止。換句話說，廣度優(yōu)先搜索遍歷圖的過程中以優(yōu)先搜索遍歷圖的過程中以v為起始點(diǎn)，由近至遠(yuǎn)，依次訪為起始點(diǎn)，由近至遠(yuǎn)，依次訪問和問和v有路徑相通且路徑長度為有路徑相通且路徑長度為1,2,的頂點(diǎn)。的頂點(diǎn)。C語言數(shù)據(jù)結(jié)構(gòu)

41、第06講 對圖對圖7-13無向圖無向圖G5 進(jìn)行廣度優(yōu)先進(jìn)行廣度優(yōu)先搜索遍歷，首先訪問搜索遍歷，首先訪問v1 和和v1的鄰接點(diǎn)的鄰接點(diǎn)v2和和v3，然后依次訪問，然后依次訪問v2 的鄰接點(diǎn)的鄰接點(diǎn)v4 和和v5 及及v3 的鄰接點(diǎn)的鄰接點(diǎn)v6和和v7，最后訪問，最后訪問v4 的鄰接點(diǎn)的鄰接點(diǎn)v8。由于這些頂點(diǎn)的鄰接。由于這些頂點(diǎn)的鄰接點(diǎn)均已被訪問，并且圖中所有頂點(diǎn)都點(diǎn)均已被訪問，并且圖中所有頂點(diǎn)都被訪問，由些完成了圖的遍歷。得到被訪問，由些完成了圖的遍歷。得到的頂點(diǎn)訪問序列為：的頂點(diǎn)訪問序列為： v1v2 v3 v4 v5 v6 v7 v8 和深度優(yōu)先搜索類似，在遍歷的過程中也需要一個訪和深度

42、優(yōu)先搜索類似，在遍歷的過程中也需要一個訪問標(biāo)志數(shù)組。并且，為了順次訪問路徑長度為問標(biāo)志數(shù)組。并且，為了順次訪問路徑長度為2、3、的的頂點(diǎn)，需附設(shè)隊列以存儲已被訪問的路徑長度為頂點(diǎn)，需附設(shè)隊列以存儲已被訪問的路徑長度為1、2、 的頂點(diǎn)。的頂點(diǎn)。V1V5V2V4V8V3V6V7圖圖7-13 無向圖無向圖G5 C語言數(shù)據(jù)結(jié)構(gòu)第06講 從圖的某一點(diǎn)從圖的某一點(diǎn)v出發(fā)，遞歸地進(jìn)行廣度優(yōu)先遍歷的過程如出發(fā)，遞歸地進(jìn)行廣度優(yōu)先遍歷的過程如下面的算法所示。下面的算法所示。 void BFSTraverseM(MGraph *G) int i; for (i=0;in;i+) visitedi=FALSE; f

43、or (i=0;in;i+) if (!visitedi) BFSM(G,i);C語言數(shù)據(jù)結(jié)構(gòu)第06講 void BFSM(MGraph *G,int k)int i,j; CirQueue Q; InitQueue(&Q); printf (廣度優(yōu)先遍歷結(jié)點(diǎn)廣度優(yōu)先遍歷結(jié)點(diǎn): 結(jié)點(diǎn)結(jié)點(diǎn)%cn,G-vexsk); visitedk=TRUE; EnQueue(&Q,k); while (!QueueEmpty(&Q) i=DeQueue(&Q); for (j=0;jn;j+) if (G-edgesij=1&!visitedj) printf (廣度優(yōu)

44、先遍歷結(jié)點(diǎn)廣度優(yōu)先遍歷結(jié)點(diǎn):%cn,G-vexsj); visitedj=TRUE; EnQueue(&Q,j); C語言數(shù)據(jù)結(jié)構(gòu)第06講 分析上述算法，每個頂點(diǎn)至多進(jìn)一次隊列。遍歷圖的分析上述算法，每個頂點(diǎn)至多進(jìn)一次隊列。遍歷圖的過程實(shí)質(zhì)是通過邊或弧找鄰接點(diǎn)的過程，因此廣度優(yōu)先搜過程實(shí)質(zhì)是通過邊或弧找鄰接點(diǎn)的過程，因此廣度優(yōu)先搜索遍歷圖和深度優(yōu)先搜索遍歷的時間復(fù)雜度是相同的，兩索遍歷圖和深度優(yōu)先搜索遍歷的時間復(fù)雜度是相同的，兩者不同之處僅僅在于對頂點(diǎn)訪問的順序不同。者不同之處僅僅在于對頂點(diǎn)訪問的順序不同。 判定一個圖的連通性是圖的一個應(yīng)用問題，我們可以判定一個圖的連通性是圖的一個應(yīng)用

45、問題，我們可以利用圖的遍歷算法來求解這一問題。本節(jié)將討論無向圖利用圖的遍歷算法來求解這一問題。本節(jié)將討論無向圖的連通性問題，并討論最小代價生成樹等問題。的連通性問題，并討論最小代價生成樹等問題。C語言數(shù)據(jù)結(jié)構(gòu)第06講7-4-1 7-4-1 無向圖的連通分量和生成樹無向圖的連通分量和生成樹 在對無向圖進(jìn)行遍歷時，對于連通圖，僅需從圖中任在對無向圖進(jìn)行遍歷時，對于連通圖，僅需從圖中任一頂點(diǎn)出發(fā)，進(jìn)行深度優(yōu)先搜索或廣度優(yōu)先搜索，便可訪一頂點(diǎn)出發(fā)，進(jìn)行深度優(yōu)先搜索或廣度優(yōu)先搜索，便可訪問到圖中所有頂點(diǎn)。對非連通圖，則需從多個頂點(diǎn)出發(fā)進(jìn)問到圖中所有頂點(diǎn)。對非連通圖，則需從多個頂點(diǎn)出發(fā)進(jìn)行搜索，而每一次從

46、一個新的起始點(diǎn)出發(fā)進(jìn)行搜索過程中行搜索，而每一次從一個新的起始點(diǎn)出發(fā)進(jìn)行搜索過程中得到的頂點(diǎn)訪問序列恰為其各個連通分量中的頂點(diǎn)集。得到的頂點(diǎn)訪問序列恰為其各個連通分量中的頂點(diǎn)集。 例如，圖例如，圖7-14 (a)是一個非連通圖是一個非連通圖G6，按照圖，按照圖7-14 (b) 所示所示G3 的鄰接表進(jìn)行深度優(yōu)先搜索遍歷的鄰接表進(jìn)行深度優(yōu)先搜索遍歷AEBFCD 圖圖7-14(a) 非連通圖非連通圖 圖圖7-14(b) G6的鄰接表的鄰接表C語言數(shù)據(jù)結(jié)構(gòu)第06講 兩次調(diào)用兩次調(diào)用DFS過程（即分別從頂點(diǎn)過程（即分別從頂點(diǎn)A 和和D出發(fā)），得到出發(fā)），得到的頂點(diǎn)訪問序列為：的頂點(diǎn)訪問序列為： A B

47、 F E C E 這兩個頂點(diǎn)集分別加上所有依附于這些頂點(diǎn)的邊，便這兩個頂點(diǎn)集分別加上所有依附于這些頂點(diǎn)的邊，便構(gòu)成了非連通圖構(gòu)成了非連通圖G3的兩個連通分量。的兩個連通分量。 因此，要想判定一個無向圖是否為連通圖，或有幾個連因此，要想判定一個無向圖是否為連通圖，或有幾個連通分量，就可設(shè)一個計數(shù)變量通分量，就可設(shè)一個計數(shù)變量count，初始時取值為，初始時取值為0，在，在深度優(yōu)先搜索算法循環(huán)中，每調(diào)用一次深度優(yōu)先搜索算法循環(huán)中，每調(diào)用一次DFS，就給，就給count增增1。這樣，當(dāng)整個算法結(jié)束時，依據(jù)。這樣，當(dāng)整個算法結(jié)束時，依據(jù)count 的值，就可確定的值，就可確定圖的連通性了。圖的連通性了

48、。 設(shè)設(shè)E(G)E(G)為連通圖為連通圖G G中所有邊的集合，則從圖中任一頂點(diǎn)中所有邊的集合，則從圖中任一頂點(diǎn)出發(fā)遍歷圖時，必定將出發(fā)遍歷圖時，必定將E(G)E(G)分成兩個集合分成兩個集合T(G)T(G)和和B(G)B(G)，其，其中中T(G)T(G)是遍歷圖過程中歷經(jīng)的邊的集合；是遍歷圖過程中歷經(jīng)的邊的集合；B(G)B(G)是剩余的邊是剩余的邊的集合。顯然，的集合。顯然，T(G)T(G)和圖和圖G G中所有頂點(diǎn)一起構(gòu)成連通圖中所有頂點(diǎn)一起構(gòu)成連通圖G G的的極小連通子圖。極小連通子圖。C語言數(shù)據(jù)結(jié)構(gòu)第06講 按照按照7-1-27-1-2節(jié)的定義，它是連通圖的一棵生成樹，并且由節(jié)的定義，它是

49、連通圖的一棵生成樹，并且由深度優(yōu)先搜索得到的為深度優(yōu)先生成樹；由廣度優(yōu)先搜索得深度優(yōu)先搜索得到的為深度優(yōu)先生成樹；由廣度優(yōu)先搜索得到的為廣度優(yōu)先生成樹。例如，圖到的為廣度優(yōu)先生成樹。例如，圖7-15(a)7-15(a)和和(b)(b)所示分別為所示分別為圖圖7-137-13連通圖連通圖G5G5的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。圖中的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。圖中虛線為集合虛線為集合B(G) B(G) 中的邊，實(shí)線為集合中的邊，實(shí)線為集合T(G)T(G)中的邊。中的邊。圖圖7-15(a) G5的深度優(yōu)先生成樹的深度優(yōu)先生成樹圖圖7-15(b) G5的廣度優(yōu)先生成樹的廣度優(yōu)先生成樹V1V5V

50、2V4V8V3V6V7V1V5V2V4V8V3V6V7C語言數(shù)據(jù)結(jié)構(gòu)第06講 對于非連通圖，通過這樣的遍歷，將得到的是生對于非連通圖，通過這樣的遍歷，將得到的是生成森林。例如，圖成森林。例如，圖7-16 (b) 7-16 (b) 所示為圖所示為圖7-16 (a)7-16 (a)的深的深度優(yōu)先生成森林，它由三棵深度優(yōu)先生成樹組成。度優(yōu)先生成森林，它由三棵深度優(yōu)先生成樹組成。圖圖7-16(a) 非連通無向圖非連通無向圖G7圖圖7-16(b) G7的深度優(yōu)先生成樹林的深度優(yōu)先生成樹林JHKLMAICFGBDEJHKLMAICFGBDEC語言數(shù)據(jù)結(jié)構(gòu)第06講7-4-2 7-4-2 最小生成樹最小生成樹

51、1 1最小生成樹的基本概念最小生成樹的基本概念 由生成樹的定義可知，無向連通圖的生成樹不一定由生成樹的定義可知，無向連通圖的生成樹不一定是唯一的。連通圖的一次遍歷所經(jīng)過的邊的集合及圖中是唯一的。連通圖的一次遍歷所經(jīng)過的邊的集合及圖中所有頂點(diǎn)的集合就構(gòu)成了該圖的一棵生成樹，對連通圖所有頂點(diǎn)的集合就構(gòu)成了該圖的一棵生成樹，對連通圖的不同遍歷，就可能得到不同的生成樹。圖的不同遍歷，就可能得到不同的生成樹。圖7-17 (a)、(b)和和(c)所示的均為圖所示的均為圖7-13的無向連通圖的無向連通圖G5的生成樹。的生成樹。V1V5V2V4V8V3V6V7V1V5V2V4V8V3V6V7V1V5V2V4V

52、8V3V6V7 圖圖7-17 7-17 無向連通圖無向連通圖G5G5的三棵生成樹的三棵生成樹（a）（b）（c）C語言數(shù)據(jù)結(jié)構(gòu)第06講 可以證明，對于有可以證明，對于有n個頂點(diǎn)的無向連通圖，無論其生成個頂點(diǎn)的無向連通圖，無論其生成樹的形態(tài)如何，所有生成樹中都有且僅有樹的形態(tài)如何，所有生成樹中都有且僅有n-1條邊。條邊。 如果無向連通圖是一個網(wǎng)，那么，它的所有生成樹中必如果無向連通圖是一個網(wǎng)，那么，它的所有生成樹中必有一棵邊的權(quán)值之和為最小的生成樹，簡稱為最小生成樹。有一棵邊的權(quán)值之和為最小的生成樹，簡稱為最小生成樹。 最小生成樹的概念可以應(yīng)用到許多實(shí)際問題中。例如有最小生成樹的概念可以應(yīng)用到許多

53、實(shí)際問題中。例如有這樣一個問題：以盡可能抵的總造價建造城市間的通訊網(wǎng)絡(luò)，這樣一個問題：以盡可能抵的總造價建造城市間的通訊網(wǎng)絡(luò)，把十個城市聯(lián)系在一起。在這十個城市中，任意兩個城市之把十個城市聯(lián)系在一起。在這十個城市中，任意兩個城市之間都可以建造通訊線路，通訊線路的造價依據(jù)城市間的距離間都可以建造通訊線路，通訊線路的造價依據(jù)城市間的距離不同而有不同的造價，可以構(gòu)造一個通訊線路造價網(wǎng)絡(luò)，在不同而有不同的造價，可以構(gòu)造一個通訊線路造價網(wǎng)絡(luò)，在網(wǎng)絡(luò)中，每個頂點(diǎn)表示城市，頂點(diǎn)之間的邊表示城市之間可網(wǎng)絡(luò)中，每個頂點(diǎn)表示城市，頂點(diǎn)之間的邊表示城市之間可構(gòu)造通訊線路，每條邊的權(quán)值表示該條通訊線路的造價，要構(gòu)造通

54、訊線路，每條邊的權(quán)值表示該條通訊線路的造價，要想使總的造價最低，實(shí)際上就是尋找該網(wǎng)絡(luò)的最小生成樹。想使總的造價最低，實(shí)際上就是尋找該網(wǎng)絡(luò)的最小生成樹。C語言數(shù)據(jù)結(jié)構(gòu)第06講2常用的構(gòu)造最小生成樹的方法常用的構(gòu)造最小生成樹的方法（1 1）構(gòu)造最小生成樹的）構(gòu)造最小生成樹的PrimPrim算法算法 假設(shè)假設(shè)G（V，E）為一連通網(wǎng)，頂點(diǎn)集）為一連通網(wǎng)，頂點(diǎn)集V=v1，v2，vn，E為網(wǎng)中所有帶權(quán)邊的集合。設(shè)置兩個新的集合為網(wǎng)中所有帶權(quán)邊的集合。設(shè)置兩個新的集合U和和T，其中集合其中集合U用于存放用于存放G的最小生成樹中的頂點(diǎn)，集合的最小生成樹中的頂點(diǎn)，集合T存放存放G的最小生成樹中的邊。令集合的最小

55、生成樹中的邊。令集合U的初值為的初值為Uv1（假設(shè)構(gòu)造（假設(shè)構(gòu)造最小生成樹時，從頂點(diǎn)最小生成樹時，從頂點(diǎn)v1出發(fā)），集合出發(fā)），集合T的初值為的初值為T。 Prim算法的基本思想：從所有算法的基本思想：從所有uU，vVU的邊中，的邊中，選取具有最小權(quán)值的邊（選取具有最小權(quán)值的邊（u，v），將頂點(diǎn)），將頂點(diǎn)v加入集合加入集合U中，將中，將邊（邊（u，v）加入集合）加入集合T中，如此不斷重復(fù)，直到中，如此不斷重復(fù)，直到UV時，最時，最小生成樹構(gòu)造完畢，這時集合小生成樹構(gòu)造完畢，這時集合T中包含了最小生成樹的所有中包含了最小生成樹的所有邊。邊。 圖圖7-18 (a)所示的一個網(wǎng)，按照所示的一個網(wǎng)，按

56、照Prim方法，從頂點(diǎn)方法，從頂點(diǎn)A出發(fā)，出發(fā)，該網(wǎng)的最小生成樹的產(chǎn)生過程如圖該網(wǎng)的最小生成樹的產(chǎn)生過程如圖7-18 (b)、(c)、(d)、(e)、(f)所示。所示。C語言數(shù)據(jù)結(jié)構(gòu)第06講圖圖7-18 Prim 算法構(gòu)造最小生成樹的過程示意圖算法構(gòu)造最小生成樹的過程示意圖 AEBFCDAEBFCDAEBFCDAEBFCDAEBFCDAEBFCD(a)(b)(c)(d)(e)(f)6812141617515666668888812121214145C語言數(shù)據(jù)結(jié)構(gòu)第06講（2 2）構(gòu)造最小生成樹的）構(gòu)造最小生成樹的KruskalKruskal算法算法 KruskalKruskal算法是一種按照網(wǎng)

57、中邊的權(quán)值遞增的算法是一種按照網(wǎng)中邊的權(quán)值遞增的順序構(gòu)造最小生成樹的方法。其基本思想是：首先順序構(gòu)造最小生成樹的方法。其基本思想是：首先選取全部的選取全部的n n個頂點(diǎn)，將其看成個頂點(diǎn)，將其看成n n個連通分量；然后個連通分量；然后按照網(wǎng)中邊的權(quán)值由小到大的順序，不斷選取當(dāng)前按照網(wǎng)中邊的權(quán)值由小到大的順序，不斷選取當(dāng)前未被選取的邊集中權(quán)值最小的邊。依據(jù)生成樹的概未被選取的邊集中權(quán)值最小的邊。依據(jù)生成樹的概念，念，n n個結(jié)點(diǎn)的生成樹，有個結(jié)點(diǎn)的生成樹，有n-1n-1條邊，故反復(fù)上述過條邊，故反復(fù)上述過程，直到選取了程，直到選取了n-1n-1條邊為止，就構(gòu)成了一棵最小條邊為止，就構(gòu)成了一棵最小生

58、成樹。生成樹。C語言數(shù)據(jù)結(jié)構(gòu)第06講圖圖7-19 Kruskal 算法構(gòu)造最小生成樹的過程示意圖算法構(gòu)造最小生成樹的過程示意圖 AEBFCDAEBFCDAEBFCDAEBFCDAEBFCDAEBFCD(a)(b)(c)(d)(e)(f)68121416175155666688885121255145返 回C語言數(shù)據(jù)結(jié)構(gòu)第06講 最短路徑問題是圖的又一個比較典型的應(yīng)用問題。例如，最短路徑問題是圖的又一個比較典型的應(yīng)用問題。例如，某一地區(qū)的一個交通網(wǎng)，給定了該網(wǎng)內(nèi)的某一地區(qū)的一個交通網(wǎng)，給定了該網(wǎng)內(nèi)的n個城市以及這些城個城市以及這些城市之間的相通公路的距離，問題是如何在城市市之間的相通公路的距離，

59、問題是如何在城市A和城市和城市B之間之間找一條最近的通路。如果將城市用頂點(diǎn)表示，城市間的公路找一條最近的通路。如果將城市用頂點(diǎn)表示，城市間的公路用邊表示，公路的長度則作為邊的權(quán)值，那么，這個問題就用邊表示，公路的長度則作為邊的權(quán)值，那么，這個問題就可歸結(jié)為在網(wǎng)中，求點(diǎn)可歸結(jié)為在網(wǎng)中，求點(diǎn)A到點(diǎn)到點(diǎn)B的所有路徑中，邊的權(quán)值之和的所有路徑中，邊的權(quán)值之和最短的那一條路徑。這條路徑就稱為兩點(diǎn)之間的最短路徑，最短的那一條路徑。這條路徑就稱為兩點(diǎn)之間的最短路徑，并稱路徑上的第一個頂點(diǎn)為源點(diǎn)（并稱路徑上的第一個頂點(diǎn)為源點(diǎn)（Sourse），最后一個頂點(diǎn)），最后一個頂點(diǎn)為終點(diǎn)（為終點(diǎn)（Destination）

60、。在不帶權(quán)的圖中，最短路徑是指兩）。在不帶權(quán)的圖中，最短路徑是指兩點(diǎn)之間經(jīng)歷的邊數(shù)最少的路徑。點(diǎn)之間經(jīng)歷的邊數(shù)最少的路徑。 例如在圖例如在圖7-20中，設(shè)中，設(shè)V1為源點(diǎn)，則從為源點(diǎn)，則從V1出發(fā)的路徑有出發(fā)的路徑有（括號里為路徑長度）：（括號里為路徑長度）：C語言數(shù)據(jù)結(jié)構(gòu)第06講V V1 1到到V V2 2的路徑有條：的路徑有條：V V1 1VV2 2(20)(20)V V1 1到到V V3 3的路徑有條：的路徑有條：V V1 1VV3 3(15),V(15),V1 1VV2 2VV3 3(55)(55)V V1 1到到V V4 4的路徑有條：的路徑有條：V V1 1VV2 2VV4 4(30),V(30),V1 1VV3 3VV4 4(45),V(45),V1 1VV2 2VV3 3VV4 4(85)(85)V