自考數(shù)據(jù)結(jié)構(gòu)02142-第五章

1、第五章第五章 圖圖 5.1 5.1 圖的基本概念圖的基本概念 5.2 5.2 圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu) 5.3 5.3 圖的遍歷圖的遍歷 5.4 5.4 圖的應(yīng)用圖的應(yīng)用一、圖的定義一、圖的定義圖圖G G 是由集合是由集合V V和和E E組成，記成組成，記成G=G=（V V，E E） 其中：其中： V V 頂點(diǎn)集頂點(diǎn)集（非空）；（非空）； E E 邊集邊集（可空）。（可空）。 邊是頂點(diǎn)的有序?qū)驘o(wú)序?qū)?。邊是頂點(diǎn)的有序?qū)驘o(wú)序?qū)Α?（邊反映了兩頂點(diǎn)之間的關(guān)系）（邊反映了兩頂點(diǎn)之間的關(guān)系）有向圖有向圖：邊是頂點(diǎn)的有序?qū)Φ膱D。：邊是頂點(diǎn)的有序?qū)Φ膱D。 （圖中每條邊都用箭頭指明了方向）（圖中每條邊都用

2、箭頭指明了方向）無(wú)向圖無(wú)向圖：邊是頂點(diǎn)的無(wú)序?qū)Φ膱D。：邊是頂點(diǎn)的無(wú)序?qū)Φ膱D。 5.1 5.1 圖的基本概念圖的基本概念例：例：V(G1)= 1，2，3，4 E(G1)= (1,2)，(1,3)，(1,4)，(2,3)， (2,4)，(3,4) （圖（圖G1）（無(wú)向圖）（無(wú)向圖）V(G2)= 1，2，3，4 ，5，6，7 E(G2)= (1,2)，(1,3)，(2,4)，(2,5)， (3,6)，(3,7) （圖（圖G2）V(G3)= 1，2，3 E(G3)= ， （圖（圖G3）（有向圖）（有向圖）注：注：1 1）邊集可空；）邊集可空； 2 2）邊集中不允許出現(xiàn)相同的邊。）邊集中不允許出現(xiàn)相同的

3、邊。二、圖的基本術(shù)語(yǔ)二、圖的基本術(shù)語(yǔ)頂點(diǎn)頂點(diǎn)(Vertex)(Vertex)圖中的數(shù)據(jù)元素；圖中的數(shù)據(jù)元素；V 有向圖中有向圖中, ,頂點(diǎn)頂點(diǎn)V Vi i到到 頂點(diǎn)頂點(diǎn)V Vj j的邊的邊, ,也稱也稱弧?。换』?頭頭（終端點(diǎn)）：箭頭端；（終端點(diǎn)）：箭頭端；弧弧 尾尾（初始點(diǎn)）：無(wú)箭頭端；（初始點(diǎn)）：無(wú)箭頭端；完全圖完全圖無(wú)向完全圖：無(wú)向完全圖：邊數(shù)邊數(shù)=n=n* *(n-1)/2(n-1)/2的無(wú)向圖；的無(wú)向圖；有向完全圖：有向完全圖：邊數(shù)邊數(shù)=n=n* *(n-1)(n-1)的有向圖；的有向圖；( (頂點(diǎn)數(shù)頂點(diǎn)數(shù)n)n)權(quán)權(quán)圖的邊附帶的數(shù)值圖的邊附帶的數(shù)值（可表示從一個(gè)頂點(diǎn)到另一（可表示從

4、一個(gè)頂點(diǎn)到另一 頂點(diǎn)的距離、代價(jià)等）頂點(diǎn)的距離、代價(jià)等）子圖子圖圖圖G G和和G,G,若有若有V(G)V(G) V(G)V(G)和和 E(G) E(G) E(G),(G), 則稱則稱 GG為圖為圖G G的子圖。的子圖。 （圖（圖G1） （圖（圖G2） （圖（圖G3）鄰接鄰接若若(V(Vi i,V,Vj j)E(G)E(G)，則稱，則稱V Vi i和和V Vj j互為鄰接互為鄰接點(diǎn)點(diǎn); ;關(guān)聯(lián)關(guān)聯(lián)若若(V(Vi i,V,Vj j)E(G)E(G)，則稱邊，則稱邊(V(Vi i,V,Vj j) )關(guān)聯(lián)于關(guān)聯(lián)于頂頂 點(diǎn)點(diǎn)V Vi i和和V Vj j; ; 注：注：1 1）鄰接是指頂點(diǎn)之間的關(guān)系，而關(guān)

5、聯(lián)是指邊）鄰接是指頂點(diǎn)之間的關(guān)系，而關(guān)聯(lián)是指邊與與 頂點(diǎn)間的關(guān)系。頂點(diǎn)間的關(guān)系。 2 2）若?。┤艋E(G)E(G)，則稱，則稱V Vj j是是V Vi i的鄰接點(diǎn)的鄰接點(diǎn)度度無(wú)向圖：頂點(diǎn)無(wú)向圖：頂點(diǎn)V Vi i的度為與的度為與V Vi i相關(guān)聯(lián)的邊的個(gè)數(shù)；相關(guān)聯(lián)的邊的個(gè)數(shù)；D(VD(Vi i) )有向圖有向圖出度出度: :頂點(diǎn)頂點(diǎn)V Vi i的出度為以的出度為以V Vi i為尾的出邊數(shù)；為尾的出邊數(shù)；OD(VOD(Vi i) )入度入度: :頂點(diǎn)頂點(diǎn)V Vi i的入度為以的入度為以V Vi i為頭的入邊為頭的入邊數(shù)；數(shù)；ID(VID(Vi i) )度度: :有向圖的度有向圖的度= =入度入

6、度+ +出度；出度；D(VD(Vi i) ) D(V D(Vi i)= OD(V)= OD(Vi i)+ID(V)+ID(Vi i) )注：注：圖中邊數(shù)圖中邊數(shù)e e與頂點(diǎn)的度的關(guān)系與頂點(diǎn)的度的關(guān)系 e=e=2 21 1ni=1i=1D（Vi）（一邊帶二度，兩度組成一邊）（一邊帶二度，兩度組成一邊）路徑路徑圖中，頂點(diǎn)圖中，頂點(diǎn)VpVp至頂點(diǎn)至頂點(diǎn)VqVq的路徑是頂點(diǎn)序列的路徑是頂點(diǎn)序列 Vp,V Vp,Vi1i1,V,Vi2i2, ,V,Vinin,Vq ,Vq 且且 對(duì)無(wú)向圖，邊對(duì)無(wú)向圖，邊(Vp,V(Vp,Vi1i1),(V),(Vi1i1,V,Vi2i2),),(V,(Vinin,Vq)

7、VR(G);,Vq)VR(G); 對(duì)有向圖，弧對(duì)有向圖，弧Vp,V,V,VR(G);,VqVR(G);路徑長(zhǎng)度路徑長(zhǎng)度路徑上邊或弧的數(shù)目；路徑上邊或弧的數(shù)目；簡(jiǎn)單路徑簡(jiǎn)單路徑序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑；序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑；回路回路第一個(gè)和最后一個(gè)頂點(diǎn)相同的路徑，也稱環(huán)；第一個(gè)和最后一個(gè)頂點(diǎn)相同的路徑，也稱環(huán)；簡(jiǎn)單回路簡(jiǎn)單回路除第一個(gè)和最后一個(gè)外，其余各頂除第一個(gè)和最后一個(gè)外，其余各頂 點(diǎn)均不相同的回路；點(diǎn)均不相同的回路；注：回路中可以有多個(gè)圈，而簡(jiǎn)單回路只能有一個(gè)圈。注：回路中可以有多個(gè)圈，而簡(jiǎn)單回路只能有一個(gè)圈。連通連通無(wú)向圖中，若從頂點(diǎn)無(wú)向圖中，若從頂點(diǎn)V Vi i到到V Vj j

8、頂點(diǎn)有路頂點(diǎn)有路徑，則稱徑，則稱V Vi i和和V Vj j是連通的。是連通的。連通圖連通圖和和連通分量連通分量針對(duì)無(wú)向圖而言針對(duì)無(wú)向圖而言 定定 義義例例 無(wú)無(wú) 向向 圖圖連通連通圖圖 連連通通 分分量量 圖中圖中每對(duì)每對(duì)頂頂點(diǎn)點(diǎn) 間都連通間都連通; ; V Vi iV Vj j圖中圖中極大極大的連的連通子圖（再擴(kuò)通子圖（再擴(kuò)大一點(diǎn)就不連大一點(diǎn)就不連通）通） (G1) (G2) （G3不是連通 圖，但它有兩 個(gè)連通分量） (G3 ) 有有向向圖圖強(qiáng)連強(qiáng)連通圖通圖 強(qiáng)連強(qiáng)連通分通分量量圖中任意一對(duì)頂點(diǎn)圖中任意一對(duì)頂點(diǎn)ViVi和和VjVj都有頂點(diǎn)都有頂點(diǎn)ViVi到頂?shù)巾旤c(diǎn)點(diǎn)VjVj的路徑，也有從

9、的路徑，也有從vjvj到到vivi的路徑，兩個(gè)的路徑，兩個(gè)頂點(diǎn)間雙向連通。頂點(diǎn)間雙向連通。有向圖的有向圖的極大極大強(qiáng)連通子圖。強(qiáng)連通子圖。 (G4) 圖圖G4G4的兩個(gè)強(qiáng)連通的兩個(gè)強(qiáng)連通分量分量l生成樹生成樹含有該連通圖的全部頂點(diǎn)的一含有該連通圖的全部頂點(diǎn)的一個(gè)極個(gè)極 小連通子圖小連通子圖 若連通圖若連通圖G G的頂點(diǎn)個(gè)數(shù)為的頂點(diǎn)個(gè)數(shù)為n n，則，則G G的生成的生成樹的邊數(shù)為樹的邊數(shù)為n-1n-1。G G的子圖的子圖GG邊數(shù)大于邊數(shù)大于n-1,n-1,則則GG中一定中一定有環(huán)有環(huán)。G G的子圖的子圖GG邊數(shù)小于邊數(shù)小于n-1,n-1,則則GG中一定中一定不連通。不連通。l生成森林生成森林在非

10、連通圖中，每個(gè)連通分在非連通圖中，每個(gè)連通分量都可得到一個(gè)極小連通子圖，也就是生量都可得到一個(gè)極小連通子圖，也就是生成樹。這些生成樹就組成了一個(gè)非連通圖成樹。這些生成樹就組成了一個(gè)非連通圖的生成森林。的生成森林。圖的基本運(yùn)算圖的基本運(yùn)算 建立圖建立圖GreateGraph(G,V,E)GreateGraph(G,V,E) 取頂點(diǎn)信息取頂點(diǎn)信息Getvex(G,u)Getvex(G,u) 取邊信息取邊信息Getarc(G,u,v)Getarc(G,u,v) 查詢第一個(gè)鄰接點(diǎn)查詢第一個(gè)鄰接點(diǎn)FirstVex(G,u)FirstVex(G,u) 查詢下一個(gè)鄰接點(diǎn)查詢下一個(gè)鄰接點(diǎn)NextVex(G,u

11、,v)NextVex(G,u,v) 插入頂點(diǎn)插入頂點(diǎn)InsertVex(G,v)InsertVex(G,v) 刪除頂點(diǎn)刪除頂點(diǎn)DeleteVex(G,v)DeleteVex(G,v) 插入邊插入邊InsertArc(G,v,w)InsertArc(G,v,w) 刪除邊刪除邊DeleteArc(G,v,w)DeleteArc(G,v,w) 遍歷圖遍歷圖Travers(G,tag)Travers(G,tag)5.2.1 5.2.1 鄰接矩陣表示法鄰接矩陣表示法 5.2 5.2 圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu)1 1、圖的鄰接矩陣、圖的鄰接矩陣 表示圖的各頂點(diǎn)之間關(guān)系的矩陣。表示圖的各頂點(diǎn)之間關(guān)系的矩陣。定

12、義定義 設(shè)設(shè)G=(V,E)G=(V,E)是是n n個(gè)頂點(diǎn)的圖，則個(gè)頂點(diǎn)的圖，則G G的的 鄰接矩陣為下列鄰接矩陣為下列n n階方陣：階方陣： Aij=1 若若 (V(Vi i,V,Vj j) )或或 VE(G) E(G) 0 否則否則 G1=0 1 1 1 1 0 1 01 1 0 1 1 0 1 0（圖（圖G1） （圖（圖G2）0 1 0 1 0 10 0 0 G2= 例：例：結(jié)論：結(jié)論： （1 1）無(wú)向圖的鄰接矩陣是對(duì)稱的；）無(wú)向圖的鄰接矩陣是對(duì)稱的； （(V(Vi i,V,Vj j)E(G)E(G)，則，則(V(Vj j,V,Vi i)E(G) )E(G) ） （2 2）從鄰接矩陣容易判

13、斷任意兩頂點(diǎn)間是否有邊相聯(lián)；）從鄰接矩陣容易判斷任意兩頂點(diǎn)間是否有邊相聯(lián)； 容易求出各頂點(diǎn)的度；容易求出各頂點(diǎn)的度； 無(wú)向圖：無(wú)向圖：頂點(diǎn)頂點(diǎn)V Vi i的度的度D(VD(Vi i)=)=矩陣中第矩陣中第i i行的行的1 1總和總和 有向圖：有向圖：OD(VOD(Vi i)=)=矩陣中第矩陣中第i i行的行的1 1總和總和 ID(VID(Vi i)=)=矩陣中第矩陣中第i i列的列的1 1總和總和2 2、 帶權(quán)圖帶權(quán)圖( (網(wǎng)網(wǎng)) )的鄰接矩陣的鄰接矩陣 Aij= Aij=w wijij 若若 (V(Vi i,V,Vj j) )或或 VE(G) E(G) V Vi i、V Vj j間無(wú)邊或弧間

14、無(wú)邊或弧（W Wijij為邊或弧的權(quán)為邊或弧的權(quán)）3 3、鄰接矩陣的類型定義、鄰接矩陣的類型定義 const int vnum=20; const int vnum=20; const int MAX_INT=32767; const int MAX_INT=32767; Typedef struct gp Typedef struct gp VertexType vexsvnum; VertexType vexsvnum; /頂點(diǎn)信息頂點(diǎn)信息 WeightType arcsvnumvnum; WeightType arcsvnumvnum; /帶權(quán)鄰帶權(quán)鄰接矩陣接矩陣 int vexnum,

15、arcnum; int vexnum,arcnum; /頂點(diǎn)數(shù)，邊數(shù)頂點(diǎn)數(shù)，邊數(shù) WGraph; WGraph; 將矩陣將矩陣A A的每個(gè)元素都初始化為最大值。的每個(gè)元素都初始化為最大值。 然后讀入邊和權(quán)值（然后讀入邊和權(quán)值（i i，j j，w wijij），將），將A A的相應(yīng)元素的相應(yīng)元素設(shè)為設(shè)為w wijij。算法如下：。算法如下：4 4、建立無(wú)向帶權(quán)鄰接矩陣：、建立無(wú)向帶權(quán)鄰接矩陣：Void CreatGraph(Graph *g) int i,j,n,e,w; char ch; scanf(“%d %d”,&n,&e); g-vexnum=n; g-arcnum=e; for (i=

16、0;ivexnum;i+) scanf(“%c”,&ch); g-vexsi=ch; for (i=0;ivexnum;i+) for (j=0;jvexnum;j+) g-arcsij=MAX_INT; for (k=0;karcnum;k+) scanf(“%d %d %d”,&i, &j,&w); g-arcsij=w; g-arcsji=w; 1.定義：定義：對(duì)圖對(duì)圖G G中每個(gè)頂點(diǎn)都建立一個(gè)單鏈表，第中每個(gè)頂點(diǎn)都建立一個(gè)單鏈表，第i i個(gè)個(gè) 單鏈表（稱單鏈表（稱邊表邊表）鏈接圖中與頂點(diǎn)鏈接圖中與頂點(diǎn)V Vi i相鄰接的所有頂點(diǎn)。相鄰接的所有頂點(diǎn)。結(jié)點(diǎn)形式：結(jié)點(diǎn)形式：鄰接點(diǎn)域鄰接點(diǎn)域（

17、頂點(diǎn)域）：（頂點(diǎn)域）：存放與頂點(diǎn)存放與頂點(diǎn)V Vi i相鄰接相鄰接頂點(diǎn)頂點(diǎn)V Vj j的序號(hào)的序號(hào)j j；鏈域鏈域：指向：指向V Vi i的下一個(gè)鄰接點(diǎn)；的下一個(gè)鄰接點(diǎn)；每個(gè)鏈表均設(shè)一表頭結(jié)點(diǎn)（以向量存儲(chǔ)，稱每個(gè)鏈表均設(shè)一表頭結(jié)點(diǎn)（以向量存儲(chǔ)，稱頂點(diǎn)表頂點(diǎn)表）表頭結(jié)點(diǎn)：表頭結(jié)點(diǎn)：vertexfirstarcViVi第第i i個(gè)鏈表的表頭結(jié)點(diǎn)；個(gè)鏈表的表頭結(jié)點(diǎn)；Vi.vertex Vi.vertex 存放頂點(diǎn)存放頂點(diǎn)V Vi i的信息；的信息；Vi.Vi.firstarc 指向指向V Vi i的鄰接鏈表的第一個(gè)結(jié)點(diǎn)。的鄰接鏈表的第一個(gè)結(jié)點(diǎn)。5.2.2 5.2.2 鄰接表表示法鄰接表表示法 adj

18、vexnextarc3. 結(jié)論：結(jié)論： 1 1）n n個(gè)頂點(diǎn)個(gè)頂點(diǎn)、e e條邊條邊的無(wú)向圖，則其鄰接表的表頭的無(wú)向圖，則其鄰接表的表頭結(jié)點(diǎn)數(shù)為結(jié)點(diǎn)數(shù)為n n，鏈表結(jié)點(diǎn)總數(shù)為鏈表結(jié)點(diǎn)總數(shù)為2e2e； 2 2）對(duì)于）對(duì)于無(wú)向圖，第無(wú)向圖，第i i個(gè)鏈表的結(jié)點(diǎn)數(shù)為頂點(diǎn)個(gè)鏈表的結(jié)點(diǎn)數(shù)為頂點(diǎn)V Vi i的度的度； 對(duì)于對(duì)于有向圖，第有向圖，第i i個(gè)鏈表的結(jié)點(diǎn)數(shù)為頂點(diǎn)個(gè)鏈表的結(jié)點(diǎn)數(shù)為頂點(diǎn)V Vi i的出的出度；度； 3 3）在邊稀疏時(shí)，鄰接表比鄰接矩陣省單元；）在邊稀疏時(shí)，鄰接表比鄰接矩陣省單元； 4 4）鄰接表表示在檢測(cè)邊數(shù)方面比鄰接矩陣表示效）鄰接表表示在檢測(cè)邊數(shù)方面比鄰接矩陣表示效率率 要高。要高

19、。2. 例：例：（P136圖圖5-10中中G2的鄰接表）的鄰接表） （P137圖圖5-11中中G1的鄰接表）的鄰接表）V1V2V3V4V50 01 12 23 34 4130241341212表頭向量表頭向量 adjlistadjlistV V1 1V V2 2V V3 3V V4 4V V5 5 例：例： V1V2V30 01 12 2表頭向量表頭向量 adjlistadjlist1024. 4. 鄰接表的類型定義：鄰接表的類型定義：#define vnum 20Typedef struct arcnode int adjvex; /下一條邊的頂點(diǎn)編號(hào)下一條邊的頂點(diǎn)編號(hào) WeightType

20、 weight; /帶權(quán)圖的權(quán)值域帶權(quán)圖的權(quán)值域 struct arcnode *nextarc；/指向下一條邊的指針指向下一條邊的指針 ArcNode;Typedef struct vexnode int vertex; /頂點(diǎn)編號(hào)頂點(diǎn)編號(hào) ArcNode *firstarc; /指向第一條邊的指針指向第一條邊的指針 AdjListvnum;Typedef struct gp AdjList adjlist; int vexnum,arcnum; /頂點(diǎn)和邊的個(gè)數(shù)頂點(diǎn)和邊的個(gè)數(shù) Graph; 對(duì)于對(duì)于無(wú)向圖，第無(wú)向圖，第i i個(gè)鏈表的結(jié)點(diǎn)數(shù)為頂點(diǎn)個(gè)鏈表的結(jié)點(diǎn)數(shù)為頂點(diǎn)V Vi i的度的度； 對(duì)

21、于對(duì)于有向圖，第有向圖，第i i個(gè)鏈表的結(jié)點(diǎn)數(shù)只為頂點(diǎn)個(gè)鏈表的結(jié)點(diǎn)數(shù)只為頂點(diǎn)V Vi i的出度；的出度；若要求入度，必須遍歷整個(gè)鄰接表。在單鏈表中，其若要求入度，必須遍歷整個(gè)鄰接表。在單鏈表中，其鄰接點(diǎn)域的值為鄰接點(diǎn)域的值為i i的結(jié)點(diǎn)個(gè)數(shù)是頂點(diǎn)的結(jié)點(diǎn)個(gè)數(shù)是頂點(diǎn)V Vi i的入度。的入度。 對(duì)于有向圖，有時(shí)候就要建立一個(gè)逆鄰接表。即對(duì)每對(duì)于有向圖，有時(shí)候就要建立一個(gè)逆鄰接表。即對(duì)每個(gè)頂點(diǎn)個(gè)頂點(diǎn)V Vi i建立一個(gè)以建立一個(gè)以V Vi i為弧頭的鄰接點(diǎn)的鏈表。這樣，為弧頭的鄰接點(diǎn)的鏈表。這樣，逆鄰接表第逆鄰接表第i i個(gè)單鏈表中的結(jié)點(diǎn)個(gè)數(shù)就是個(gè)單鏈表中的結(jié)點(diǎn)個(gè)數(shù)就是V Vi i的入度。的入度。5

22、. 5. 計(jì)算計(jì)算圖的度圖的度例：圖例：圖5-2中中G1的鄰接表和逆鄰接表見的鄰接表和逆鄰接表見P137圖圖5-11結(jié)點(diǎn)形式：結(jié)點(diǎn)形式：6. 6. 帶權(quán)圖鄰接表帶權(quán)圖鄰接表adjvex weight nextarc權(quán)值域：用于存儲(chǔ)邊的權(quán)值權(quán)值域：用于存儲(chǔ)邊的權(quán)值畫出畫出圖圖5-1a5-1a無(wú)向帶權(quán)圖的鄰接表。無(wú)向帶權(quán)圖的鄰接表。 圖圖5-8a5-8a有向帶權(quán)圖的鄰接表、逆鄰接表。有向帶權(quán)圖的鄰接表、逆鄰接表。建立有向圖的鄰接表的方法：建立有向圖的鄰接表的方法：l將鄰接表表頭數(shù)組初始化將鄰接表表頭數(shù)組初始化; ;l第第i i個(gè)表頭的個(gè)表頭的vertexvertex域初始化為域初始化為i i；lf

23、irstfirst域初始化為域初始化為NULL;NULL;l讀入頂點(diǎn)對(duì)讀入頂點(diǎn)對(duì),產(chǎn)生一個(gè)表結(jié)點(diǎn)；產(chǎn)生一個(gè)表結(jié)點(diǎn)；l將將j j放入到該結(jié)點(diǎn)的放入到該結(jié)點(diǎn)的adjvexadjvex域；域；l將該結(jié)點(diǎn)鏈到鄰接表的表頭數(shù)組的第將該結(jié)點(diǎn)鏈到鄰接表的表頭數(shù)組的第i i個(gè)元素的個(gè)元素的firstfirst域上。域上。建立有向圖的鄰接表算法見P1385.3 5.3 圖的遍歷圖的遍歷遍歷的含義及方法：遍歷的含義及方法：圖的遍歷圖的遍歷從圖從圖G中某一頂點(diǎn)中某一頂點(diǎn)v出發(fā)，出發(fā)，順順 序訪問各頂點(diǎn)一次。序訪問各頂點(diǎn)一次。方法：方法：深度優(yōu)先搜索法深度優(yōu)先搜索法廣度優(yōu)先搜索法廣度優(yōu)先搜索法為克服頂點(diǎn)的重復(fù)訪問，設(shè)

24、立輔助數(shù)組為克服頂點(diǎn)的重復(fù)訪問，設(shè)立輔助數(shù)組visitedn。1 頂點(diǎn)頂點(diǎn)i已被訪問過已被訪問過0 頂點(diǎn)頂點(diǎn)i未被訪問過未被訪問過visitedi=遍歷方法遍歷方法5.3.1 5.3.1 深度優(yōu)先搜索法（深度優(yōu)先搜索法（DFSDFS）一、過程一、過程 從圖從圖G(V,E)G(V,E)中任一頂點(diǎn)中任一頂點(diǎn)V Vi i開始，首先訪問開始，首先訪問V Vi i，然后訪，然后訪問問V Vi i的的任任一未訪問過的鄰接點(diǎn)一未訪問過的鄰接點(diǎn)V Vj j，再以，再以V Vj j為新的出發(fā)點(diǎn)繼續(xù)為新的出發(fā)點(diǎn)繼續(xù)進(jìn)行深度優(yōu)先搜索，直到所有頂點(diǎn)都被訪問過。進(jìn)行深度優(yōu)先搜索，直到所有頂點(diǎn)都被訪問過。二、例：二、例：

25、三、算法：三、算法： 分析：分析： a、為克服頂點(diǎn)的重復(fù)訪問，設(shè)立一標(biāo)志向量、為克服頂點(diǎn)的重復(fù)訪問，設(shè)立一標(biāo)志向量 visited n; b、圖可用鄰接矩陣或鄰接表表示；、圖可用鄰接矩陣或鄰接表表示； 從從V V1 1出發(fā)出發(fā), DFS:V1，V2， V4， V5， V3，V6V V4 4V V1 1V V2 2V V3 3V V5 5V V6 6注意：注意： 搜索到達(dá)某個(gè)頂點(diǎn)時(shí)搜索到達(dá)某個(gè)頂點(diǎn)時(shí)( (圖中仍有頂點(diǎn)未被訪問圖中仍有頂點(diǎn)未被訪問) )，如果，如果這個(gè)頂點(diǎn)的所有鄰接點(diǎn)都被訪問過，那么搜索就要回這個(gè)頂點(diǎn)的所有鄰接點(diǎn)都被訪問過，那么搜索就要回到前一個(gè)被訪問過的頂點(diǎn)，再?gòu)脑擁旤c(diǎn)的下一未被

26、訪到前一個(gè)被訪問過的頂點(diǎn)，再?gòu)脑擁旤c(diǎn)的下一未被訪問的鄰接點(diǎn)開始深度優(yōu)先搜索。；問的鄰接點(diǎn)開始深度優(yōu)先搜索。； 深度搜索的頂點(diǎn)的訪問序列深度搜索的頂點(diǎn)的訪問序列不是唯一的不是唯一的。連通圖的深度優(yōu)先搜索的算法連通圖的深度優(yōu)先搜索的算法: :Dfs (Graph g, int v) 訪問訪問 v； visitedv=1; / visitedv初值都為初值都為0，頂點(diǎn)，頂點(diǎn)v已被訪問，就置為已被訪問，就置為1 找出找出g中中v的第一個(gè)鄰接點(diǎn)的第一個(gè)鄰接點(diǎn)w； while (w存在存在) if w 未被訪問未被訪問Dfs(g,w); w=g中中v的下一個(gè)鄰接點(diǎn)；的下一個(gè)鄰接點(diǎn)； 深度優(yōu)先搜索法算法：深

27、度優(yōu)先搜索法算法：對(duì)圖按深度優(yōu)先遍歷的遞歸算法（對(duì)圖按深度優(yōu)先遍歷的遞歸算法（鄰接表鄰接表）：）： int visitedN=0 ; /*對(duì)訪問標(biāo)記對(duì)訪問標(biāo)記visited數(shù)組初始化數(shù)組初始化*/ Dfs ( Graph g , int v ) /從第從第v個(gè)頂點(diǎn)出發(fā)遞歸地深度優(yōu)先遍歷圖個(gè)頂點(diǎn)出發(fā)遞歸地深度優(yōu)先遍歷圖g，圖以鄰接表作為，圖以鄰接表作為存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu) ArcNode *p ; printf ( “%d”,v ) ; /* 訪問起始頂點(diǎn)訪問起始頂點(diǎn)v*/ visited v = 1; /* 置置“已訪問已訪問”標(biāo)記標(biāo)記*/ p = g.adjlistv.firstarc ; /*

28、 取頂點(diǎn)表中取頂點(diǎn)表中v的邊表頭指針的邊表頭指針*/ while ( p != NULL ) /* 依次搜索依次搜索v的鄰接點(diǎn)的鄰接點(diǎn)*/ if ( ! visitedp-adjvex ) /*v的一個(gè)鄰接點(diǎn)未被訪問的一個(gè)鄰接點(diǎn)未被訪問*/ Dfs ( g,p-adjvex ) ; /*沿此沿此鄰接點(diǎn)出發(fā)繼續(xù)鄰接點(diǎn)出發(fā)繼續(xù)DFS*/ p = p-nextarc ; /* 取取v的下一個(gè)鄰接點(diǎn)的下一個(gè)鄰接點(diǎn)*/ V V0 0V V1 1V V2 2V V3 3V V4 4V V5 5V V6 6V V7 7V0V1V2V3V4V5V6V70 01 12 23 34 45 56 67 712034

29、0561717262534表頭向量表頭向量 adjlistadjlist從從V V0 0出發(fā)出發(fā),深度優(yōu)先搜索深度優(yōu)先搜索: V V0 0，V V1 1，深度優(yōu)先搜索法算法：深度優(yōu)先搜索法算法：對(duì)圖按深度優(yōu)先遍歷的遞歸算法對(duì)圖按深度優(yōu)先遍歷的遞歸算法（鄰接矩陣鄰接矩陣）：）： int visitedN=0 ; /*對(duì)訪問標(biāo)記對(duì)訪問標(biāo)記visited數(shù)組初始化數(shù)組初始化*/ Dfs ( Graph g , int v ) /從第從第v個(gè)頂點(diǎn)出發(fā)遞歸地深度優(yōu)先遍歷圖個(gè)頂點(diǎn)出發(fā)遞歸地深度優(yōu)先遍歷圖g，圖以鄰接矩陣作為存，圖以鄰接矩陣作為存儲(chǔ)結(jié)構(gòu)儲(chǔ)結(jié)構(gòu) int j ; printf ( “%d”,v

30、) ; /* 訪問起始頂點(diǎn)訪問起始頂點(diǎn)v*/ visited v = 1; /* 置置“已訪問已訪問”標(biāo)記標(biāo)記*/ for (j=0;jarcsvj; /*順序訪問矩陣的第順序訪問矩陣的第v行結(jié)點(diǎn)行結(jié)點(diǎn)*/ if （m&!visitedj） /*如果如果v與與j鄰接，且鄰接，且j未被訪問未被訪問*/ Dfs ( g,j ) ; /*遞歸訪問遞歸訪問j*/ 5.3.2 廣度優(yōu)先搜索法（廣度優(yōu)先搜索法（BFS）一、過程一、過程 從圖從圖G(V,E)中某一點(diǎn)中某一點(diǎn)Vi出發(fā)，首先訪問出發(fā)，首先訪問Vi的的所有鄰接點(diǎn)（所有鄰接點(diǎn)（w1，w2，wt），然后再順序訪），然后再順序訪問問w1，w2，wt的的

31、 所有未被訪問過的鄰接所有未被訪問過的鄰接點(diǎn)點(diǎn)., 重復(fù)此過程直到所有頂點(diǎn)都被訪問過。重復(fù)此過程直到所有頂點(diǎn)都被訪問過。二、例：二、例：三、算法：三、算法： 分析：分析： a、為克服頂點(diǎn)的重復(fù)訪問，設(shè)立一標(biāo)志、為克服頂點(diǎn)的重復(fù)訪問，設(shè)立一標(biāo)志向量向量 visited n; b、圖可用鄰接矩陣或鄰接表表示；、圖可用鄰接矩陣或鄰接表表示； c、頂點(diǎn)的處理次序、頂點(diǎn)的處理次序先進(jìn)先出，故先進(jìn)先出，故需需用到用到 一隊(duì)列一隊(duì)列從從V V1 1出發(fā)出發(fā), BFS:V1，V2， V3，V4， V5，V6V V4 4V V1 1V V2 2V V3 3V V5 5V V6 6廣度優(yōu)先遍歷算法基本思想：廣度優(yōu)

32、先遍歷算法基本思想：1.1.所有結(jié)點(diǎn)標(biāo)記置為所有結(jié)點(diǎn)標(biāo)記置為“未被訪問未被訪問”標(biāo)志；標(biāo)志；2.2.訪問起始頂點(diǎn)，同時(shí)置起始頂點(diǎn)訪問起始頂點(diǎn)，同時(shí)置起始頂點(diǎn)“已訪問已訪問”標(biāo)記標(biāo)記; ;3.3.將起始頂點(diǎn)進(jìn)隊(duì)列；將起始頂點(diǎn)進(jìn)隊(duì)列；4.4.當(dāng)隊(duì)列不為空時(shí)重復(fù)執(zhí)行以下步驟；當(dāng)隊(duì)列不為空時(shí)重復(fù)執(zhí)行以下步驟； 1 1）取當(dāng)前隊(duì)頭頂點(diǎn)；）取當(dāng)前隊(duì)頭頂點(diǎn)； 2 2）對(duì)與隊(duì)頭頂點(diǎn)相鄰接的所有未被訪問過）對(duì)與隊(duì)頭頂點(diǎn)相鄰接的所有未被訪問過 的頂點(diǎn)依次做：的頂點(diǎn)依次做： (a)(a)訪問該頂點(diǎn)；訪問該頂點(diǎn)； (b)(b)置該頂點(diǎn)為置該頂點(diǎn)為“已訪問已訪問”標(biāo)記標(biāo)記, ,并將它進(jìn)隊(duì)列；并將它進(jìn)隊(duì)列； 3 3）當(dāng)前

33、隊(duì)頭元素頂點(diǎn)出隊(duì)；）當(dāng)前隊(duì)頭元素頂點(diǎn)出隊(duì)； 4) 4) 重復(fù)進(jìn)行，直到隊(duì)空時(shí)結(jié)束。重復(fù)進(jìn)行，直到隊(duì)空時(shí)結(jié)束。 廣度優(yōu)先遍歷算法廣度優(yōu)先遍歷算法： int visitedN=0 ; /*對(duì)訪問標(biāo)記對(duì)訪問標(biāo)記visited數(shù)組初始化數(shù)組初始化*/ int queueN ; /*隊(duì)列隊(duì)列queue存放已訪問過的頂點(diǎn)存放已訪問過的頂點(diǎn)*/ 對(duì)圖按廣度優(yōu)先遍歷的算法：對(duì)圖按廣度優(yōu)先遍歷的算法：bfs (Graph g , int vbfs (Graph g , int v ) ) / / 從頂點(diǎn)從頂點(diǎn)v v出發(fā)，按廣度優(yōu)先遍歷圖出發(fā)，按廣度優(yōu)先遍歷圖g g，圖用，圖用鄰接表鄰接表表示表示 printf(

34、“%d”,vprintf(“%d”,v );); visited visited v = 1;v = 1; / /* *訪問初始頂點(diǎn)訪問初始頂點(diǎn)v vi i* */ / rear=1; front=0; rear=1; front=0; queuerear=v ; queuerear=v ; / /* * 起始頂點(diǎn)（序號(hào)）入隊(duì)起始頂點(diǎn)（序號(hào)）入隊(duì)* */ / while ( front!=rear ) while ( front!=rear ) / /* *隊(duì)列不空，則循環(huán)隊(duì)列不空，則循環(huán)* */ / front=(front+1)%N ; front=(front+1)%N ; / /* *

35、置隊(duì)頭置隊(duì)頭* */ / v=queuefront; v=queuefront; / /* * 隊(duì)頭元素出隊(duì)隊(duì)頭元素出隊(duì)* */ / p=g.adjlistv.firstarc; p=g.adjlistv.firstarc; / /* *取剛出隊(duì)頂點(diǎn)取剛出隊(duì)頂點(diǎn)v v的邊表的的邊表的頭指針頭指針* */ / while ( p!=NULL ) while ( p!=NULL ) / /* * 依次搜索依次搜索v v的鄰接點(diǎn)的鄰接點(diǎn)* */ / if (! visitedp-adjvex) if (! visitedp-adjvex) / /* *v v的一個(gè)鄰接點(diǎn)的一個(gè)鄰接點(diǎn)未被訪問未被訪問*

36、 */ / printf (“%d”,p-adjvex) printf (“%d”,p-adjvex) / /* *訪問此鄰接點(diǎn)訪問此鄰接點(diǎn)* */ / visitedp-adjvex = 1 ; visitedp-adjvex = 1 ; rear=(rear+1)%N ; rear=(rear+1)%N ; / /* *隊(duì)尾指針增隊(duì)尾指針增1 1* */ / queuerear=p-adjvex; queuerear=p-adjvex; / /* *訪問過的頂點(diǎn)入隊(duì)訪問過的頂點(diǎn)入隊(duì)* */ / p=p-nextarc; p=p-nextarc; / /* * 找找v v的下一個(gè)鄰接點(diǎn)的下一

37、個(gè)鄰接點(diǎn)* */ / / /* *bfsbfs* */ /V V0 0V V1 1V V2 2V V3 3V V4 4V V5 5V V6 6V V7 7V0V1V2V3V4V5V6V70 01 12 23 34 45 56 67 7120340561717262534表頭向量表頭向量 adjlistadjlist從從V V0 0出發(fā)出發(fā),廣度優(yōu)先搜索廣度優(yōu)先搜索: V V0 0，Bfs (Graph g, int v) LkQue Q; /Q為鏈隊(duì)列 int j; InitQueue(&Q); printf(“%d”,v); /v為訪問的起始結(jié)點(diǎn) visitedv=1; /訪問過的標(biāo)志 En

38、Queue(&Q,v); while ( !EmptyQueue(Q) /判隊(duì)列是否為空 v=Gethead(&Q); OutQueue(&Q); /出隊(duì)列 for (j=0;jarcsvj; if (m & !visitedj) /判斷是否鄰接點(diǎn)，且未被訪問 printf(“%d”,j); visitedj=1; /置被訪問標(biāo)志 EnQueue(&Q,j); /鄰接點(diǎn)入隊(duì)列 1 1、判斷圖的連通性、判斷圖的連通性 對(duì)圖對(duì)圖G G調(diào)用一次調(diào)用一次DFSDFS或或BFSBFS，得到一頂點(diǎn)，得到一頂點(diǎn)集合，然后將之與集合，然后將之與V(G)V(G)比較，若兩集合相等，比較，若兩集合相等，則圖則圖G

39、 G是連通圖，否則就說明有未訪問過的是連通圖，否則就說明有未訪問過的頂點(diǎn)，因此圖不連通。頂點(diǎn)，因此圖不連通。 5.3.3 求圖的連通分求圖的連通分量量2 2、求圖的連通分量、求圖的連通分量 從無(wú)向圖的從無(wú)向圖的每個(gè)連通分量每個(gè)連通分量的一個(gè)頂點(diǎn)出發(fā)遍的一個(gè)頂點(diǎn)出發(fā)遍歷，則可求得無(wú)向圖的所有連通分量。歷，則可求得無(wú)向圖的所有連通分量。圖遍歷的一種應(yīng)用圖遍歷的一種應(yīng)用算法：算法： void trace( Graph G ) void trace( Graph G ) / /* *G G為用鄰接矩陣或鄰接表表示的有為用鄰接矩陣或鄰接表表示的有n n個(gè)頂點(diǎn)的無(wú)向個(gè)頂點(diǎn)的無(wú)向圖，求該圖的連通分量圖，求該

40、圖的連通分量* */ / int i; int i; for ( i=0; iN; +i )for ( i=0; iN; +i ) if (!flagi)if (!flagi) dfs(i); dfs(i); / /* *調(diào)用調(diào)用DFSDFS算法的次數(shù)僅決定于連通分量個(gè)數(shù)算法的次數(shù)僅決定于連通分量個(gè)數(shù)* */ / OUTPUT OUTPUT ；/ /* *輸出訪問到的頂點(diǎn)和依附于這輸出訪問到的頂點(diǎn)和依附于這* */ / / /* *些頂點(diǎn)的邊，就得到一個(gè)連通分量些頂點(diǎn)的邊，就得到一個(gè)連通分量* */ / / /* *tracetrace* */ / 一、生成樹一、生成樹1 1、生成樹定義生成樹

41、定義：連通圖：連通圖G=(V,E)G=(V,E)，從任一頂點(diǎn)，從任一頂點(diǎn) 遍歷，則圖中邊分成兩部分：遍歷，則圖中邊分成兩部分：遍歷通過的邊遍歷通過的邊 剩下的邊剩下的邊( (即遍歷時(shí)未通過的邊）即遍歷時(shí)未通過的邊）E(G) = T(G)+ B(G)E(G) = T(G)+ B(G)則則G(VG(V，T)T)為為G G的子圖，稱之為的子圖，稱之為G G的一棵生成樹。的一棵生成樹。深度優(yōu)先生成樹：深度優(yōu)先生成樹：按深度優(yōu)先遍歷而得的生成樹按深度優(yōu)先遍歷而得的生成樹廣度優(yōu)先生成樹：廣度優(yōu)先生成樹：按廣度優(yōu)先遍歷而得的生成樹按廣度優(yōu)先遍歷而得的生成樹5.4 5.4 圖的應(yīng)用圖的應(yīng)用2 2、例：、例：

42、其深度優(yōu)先生成樹為：其深度優(yōu)先生成樹為：其廣度優(yōu)先生成樹為：其廣度優(yōu)先生成樹為：圖的生成樹不是惟一的。圖的生成樹不是惟一的。1 1、問題的提出：、問題的提出： 通訊網(wǎng)：通訊網(wǎng)：網(wǎng)中網(wǎng)中n n個(gè)頂點(diǎn)個(gè)頂點(diǎn)n n個(gè)城市個(gè)城市兩頂點(diǎn)間的邊兩頂點(diǎn)間的邊兩城市間線路兩城市間線路邊的權(quán)邊的權(quán)架設(shè)相應(yīng)線路的費(fèi)用架設(shè)相應(yīng)線路的費(fèi)用問題問題1 1：n n個(gè)城市間的通訊網(wǎng)，個(gè)城市間的通訊網(wǎng)，至少至少要多少條線路？要多少條線路？（n-1n-1）n n個(gè)城市間最少的可行的通訊線路就是個(gè)城市間最少的可行的通訊線路就是一棵生成樹一棵生成樹問題問題2 2：選擇怎樣的：選擇怎樣的n-1n-1條線路，使總費(fèi)用最少？條線路，使總

43、費(fèi)用最少？網(wǎng)上問題：取網(wǎng)上問題：取n-1n-1條邊，并使邊權(quán)總和為最少。條邊，并使邊權(quán)總和為最少。最小生成樹問題最小生成樹問題二、最小生成樹二、最小生成樹2 2、最小生成樹定義、最小生成樹定義 給定一個(gè)帶權(quán)圖，構(gòu)造帶權(quán)圖的一棵生給定一個(gè)帶權(quán)圖，構(gòu)造帶權(quán)圖的一棵生成樹，使樹中所有邊的權(quán)總和為最小。成樹，使樹中所有邊的權(quán)總和為最小。3、最小生成樹的構(gòu)造算法、最小生成樹的構(gòu)造算法Prim算法和算法和kruskal算法算法基本思想：基本思想： 假設(shè)假設(shè)G=(V,E)G=(V,E)是一個(gè)無(wú)向帶權(quán)圖，生成的最小生成樹為是一個(gè)無(wú)向帶權(quán)圖，生成的最小生成樹為MinT=(V,T),MinT=(V,T),其中其中

44、V V為頂點(diǎn)的集合，為頂點(diǎn)的集合，T T為邊的集合。求為邊的集合。求T T的步驟如下：的步驟如下：1.1.初始化初始化U=uU=u0 0 ，T= T= ；其中；其中U U為一個(gè)新設(shè)置的頂點(diǎn)的集合，初始為一個(gè)新設(shè)置的頂點(diǎn)的集合，初始U U中只含有頂點(diǎn)中只含有頂點(diǎn)u u0 0，這里假設(shè)在構(gòu)造最小生成樹時(shí)，從頂點(diǎn)，這里假設(shè)在構(gòu)造最小生成樹時(shí)，從頂點(diǎn)u u0 0出發(fā)；出發(fā)；2.2.對(duì)所有對(duì)所有uUuU，vV-U(vV-U(其中其中u u，v v表示頂點(diǎn)表示頂點(diǎn)) )的邊的邊(u,v)(u,v)中，找一條權(quán)中，找一條權(quán)最小的邊最小的邊(u,v)(u,v)，將這條邊加入到集合，將這條邊加入到集合T T中，

45、將頂點(diǎn)中，將頂點(diǎn)vv加入到加入到集合集合U U中；中；3.3.如果如果U=VU=V，則算法結(jié)束；否則重復(fù)，則算法結(jié)束；否則重復(fù)2 2、3 3步。步。最后得到最小生成樹最后得到最小生成樹MinT=,其中其中T為最小生成樹為最小生成樹的邊的集合的邊的集合三、最小生成樹的構(gòu)造方法（三、最小生成樹的構(gòu)造方法（Prim法）法）初態(tài)初態(tài) 5 5 0,1,2,3,4 0,1,2,3,4 1 1 5, 3 0, 1, 2, 4 2 2 5, 3, 2 0, 1, 4 3 3 5, 3, 2, 0 1, 4 4 4 5, 3, 2, 0, 1 4 5 5 5, 3, 2, 0, 1, 4 （6 6個(gè)頂點(diǎn)，個(gè)頂點(diǎn)

46、，5 5條邊）條邊） 0132452513546656 步驟步驟 已選頂點(diǎn)集已選頂點(diǎn)集U U 剩余頂點(diǎn)集剩余頂點(diǎn)集V-UV-U 已選已選集集TETE35201431524 例：對(duì)下圖用例：對(duì)下圖用Prim法構(gòu)造最小生成樹法構(gòu)造最小生成樹 最小生成樹的構(gòu)造方法（最小生成樹的構(gòu)造方法（PrimPrim法）法） 適合于求邊稠密的帶權(quán)圖的最小生成樹。適合于求邊稠密的帶權(quán)圖的最小生成樹。 設(shè)設(shè)G=G=（V V，E E）是個(gè)無(wú)向帶權(quán)圖，）是個(gè)無(wú)向帶權(quán)圖，U U是最小生成樹的頂是最小生成樹的頂點(diǎn)集合，點(diǎn)集合，T T是最小生成樹的邊集合，則是最小生成樹的邊集合，則PrimPrim算法描述如算法描述如下：下：

47、Prim ( Graph G ) Prim ( Graph G ) / /* *構(gòu)造圖構(gòu)造圖G G的最小生成樹的最小生成樹* */ / 從從G G中任選一頂點(diǎn)中任選一頂點(diǎn)pV pV ； U= p U= p ； T= T= ； while ( UV while ( UV ） 在在pUpU，qV-UqV-U中找一條權(quán)最小的邊（中找一條權(quán)最小的邊（p,qp,q）；）； U=U+ q ;U=U+ q ; T=T+ T=T+（p,qp,q）; ; / /* *PrimPrim* */ /具體類C語(yǔ)言算法見課本P146-P147基本思想：基本思想：1.1.設(shè)設(shè)G=(V,E),G=(V,E),令最小生成樹初

48、始狀態(tài)為只有令最小生成樹初始狀態(tài)為只有n n個(gè)頂點(diǎn)個(gè)頂點(diǎn)而無(wú)邊的非聯(lián)通圖而無(wú)邊的非聯(lián)通圖T=T=（V V， ），每個(gè)頂點(diǎn)自成一），每個(gè)頂點(diǎn)自成一個(gè)連通分量；個(gè)連通分量；2.2.在在E E中選取權(quán)值最小的邊，若該邊依附的頂點(diǎn)落在中選取權(quán)值最小的邊，若該邊依附的頂點(diǎn)落在T T中不同的連通分量上，則將此邊加入到中不同的連通分量上，則將此邊加入到T T中，否則，中，否則，舍去此邊，選取下一條權(quán)值最小的邊；舍去此邊，選取下一條權(quán)值最小的邊；3.3.以此類推，重復(fù)以此類推，重復(fù)2 2，直至，直至T T中所有頂點(diǎn)都在同一連中所有頂點(diǎn)都在同一連通分量上為止。通分量上為止。四、最小生成樹的構(gòu)造方法四、最小生成樹

49、的構(gòu)造方法（ KruskalKruskal克魯斯卡爾法克魯斯卡爾法 ） 初態(tài)初態(tài) 1 1 （2 2，3 3） 5 5 接收接收 2 2 （2 2，4 4） 6 6 接收接收 3 3 （3 3，4 4） 6 6 不接收不接收 4 4 （2 2，6 6） 11 11 接收接收 5 5 （6 6，4 4） 14 14 不接收不接收（構(gòu)成回路）（構(gòu)成回路） 6 6 （1 1，2 2） 16 16 接收接收 7 7 （5 5，4 4） 18 18 接收接收 （6 6個(gè)頂點(diǎn)，個(gè)頂點(diǎn)，5 5條邊）條邊） 步驟步驟 最小權(quán)邊及權(quán)最小權(quán)邊及權(quán) 動(dòng)作動(dòng)作 最小生成樹最小生成樹 例：對(duì)下圖用例：對(duì)下圖用Kruska

50、l法法構(gòu)造最小生成樹構(gòu)造最小生成樹6132546165192114111833661325461651118注：注：用用KruskalKruskal方法構(gòu)造的最小生成樹不方法構(gòu)造的最小生成樹不唯一，但權(quán)和相同。唯一，但權(quán)和相同。 最小生成樹的構(gòu)造方法（最小生成樹的構(gòu)造方法（KruskalKruskal法）法） 適合于求邊稀疏的網(wǎng)的最小生成樹。適合于求邊稀疏的網(wǎng)的最小生成樹。原則：原則：按權(quán)值遞增次序構(gòu)造按權(quán)值遞增次序構(gòu)造T Tminmin ； 即每次選權(quán)最小且不構(gòu)成回路的邊即每次選權(quán)最小且不構(gòu)成回路的邊, ,直至直至n-1n-1條。條。 KruskalKruskal方法形式描述：方法形式描述：

51、 Kruskal Kruskal （ Graph G ) Graph G ) / /* *構(gòu)造圖構(gòu)造圖G G的最小生成樹的最小生成樹* */ / n=G n=G的頂點(diǎn)數(shù)的頂點(diǎn)數(shù) ; ; V(T)=V(G); E(T)= ; V(T)=V(G); E(T)= ;/ /* *T T初始化為初始化為n n個(gè)頂點(diǎn)而無(wú)邊的圖個(gè)頂點(diǎn)而無(wú)邊的圖* */ / while ( E(T) while ( E(T)中邊數(shù)中邊數(shù) n-1 n-1 ） 從從E(G)E(G)中選擇最小權(quán)的邊（中選擇最小權(quán)的邊（v,wv,w）；）； 從從E(G)E(G)中刪去邊（中刪去邊（v,wv,w）；）； ifif（v,wv,w）加到）

52、加到T T中不形成回路中不形成回路 ） 則將邊（則將邊（v,wv,w）加入）加入T T中；中； / /* *KruskalKruskal* */ /一、問題的提出一、問題的提出 圖可以描述一個(gè)工程或系統(tǒng)的進(jìn)行過程。圖可以描述一個(gè)工程或系統(tǒng)的進(jìn)行過程。 所有活動(dòng)完成整個(gè)工程完所有活動(dòng)完成整個(gè)工程完成成活動(dòng)間有一定的先后關(guān)活動(dòng)間有一定的先后關(guān)系系工工程程子工程子工程1 1（活動(dòng)（活動(dòng)1 1）子工程子工程2 2（活動(dòng)（活動(dòng)2 2） . . . .子工程子工程m m（活動(dòng)（活動(dòng)m m）分分5.5 5.5 拓?fù)渑判蛲負(fù)渑判蚶杭俣ǔ绦蛟O(shè)計(jì)專業(yè)的學(xué)員要學(xué)例：假定程序設(shè)計(jì)專業(yè)的學(xué)員要學(xué)5 5門課程。門課程。 完成完成5 5門課的學(xué)習(xí)門課的學(xué)習(xí)這里這里 工工程程學(xué)習(xí)一門課程學(xué)習(xí)一門課程 子工子工程程課程編號(hào)課程編號(hào)課程名稱課程名稱先決條件先決條件C C1 1 程序設(shè)計(jì)基礎(chǔ)程序設(shè)計(jì)基礎(chǔ) None NoneC C2 2 離散數(shù)學(xué)離散數(shù)學(xué) C C1 1C C3 3 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) C C1 1,C,C2 2C C4 4 匯編語(yǔ)言匯編語(yǔ)言 C C1 1 C C5 5 高