數(shù)據(jù)結(jié)構(gòu)-圖的基本知識(shí)點(diǎn)

第8章圖8.1圖的基本概念8.2圖的基本存儲(chǔ)結(jié)構(gòu)8.2.1鄰接距陣及其實(shí)現(xiàn)8.2.2鄰接表及其實(shí)現(xiàn)8.3圖的遍歷8.3.1深度優(yōu)先搜索遍歷8.3.2廣度優(yōu)先搜索遍歷8.4圖的應(yīng)用8.4.1連通圖的最小生成樹(shù)8.4.2拓?fù)渑判驍?shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第1頁(yè)。一、現(xiàn)實(shí)中的圖8.1圖的基本概念

圖最常見(jiàn)的應(yīng)用是在交通運(yùn)輸和通信網(wǎng)絡(luò)中找出造價(jià)最低的方案。通信網(wǎng)絡(luò)示例如下圖所示：數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第2頁(yè)。

圖G是由一個(gè)頂點(diǎn)集V和一個(gè)邊集E構(gòu)成的數(shù)據(jù)結(jié)構(gòu)。記為二元組形式：G=(V,E)其中:

V是由頂點(diǎn)構(gòu)成的非空有限集合，記為：V＝{V0,V1,V2,…Vn-1}

E是由V中頂點(diǎn)的對(duì)偶構(gòu)成的有限集合，記為：E={(V0,V2),(V3,V4),…}，若E為空，則圖中只有頂點(diǎn)而沒(méi)有邊。其中對(duì)偶可以表示成：

(Vi,Vj)—無(wú)序的對(duì)偶稱(chēng)為邊，即(Vi,Vj)=(Vj,Vi)，其圖稱(chēng)為無(wú)向圖

<Vi,Vj>—有序的對(duì)偶稱(chēng)為弧，即<Vi,Vj>≠<Vj,Vi>，則稱(chēng)Vi為弧尾，稱(chēng)Vj為弧頭，該圖稱(chēng)為有向圖二、圖的定義數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第3頁(yè)。有向圖和無(wú)向圖示例：無(wú)向圖G1的二元組表示：V(G1)={V1,V2,V3,V4}E(G1)={(V1,V2)，(V1,V3)，(V1,V4)，(V2,V3)，(V2,V4)，(V3,V4)}有向圖G3的二元組表示：

V(G3)={V1,V2,V3}E(G3)={<V1,V2>，<V1,V3>，<V2,V3>，<V3,V2>}數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第4頁(yè)。在無(wú)向圖中，若存在一條邊（Vi,Vj），則稱(chēng)Vi和Vj互為鄰接點(diǎn)（Adjacent）在有向圖中，若存在一條弧<Vi,Vj>，則稱(chēng)Vi為此弧的起點(diǎn)，稱(chēng)Vj為此弧的終點(diǎn)，稱(chēng)Vi鄰接到Vj，Vj鄰接自Vi，Vi和Vj互為鄰接點(diǎn)。1．鄰接點(diǎn)

數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第5頁(yè)。2．頂點(diǎn)的度、入度和出度在無(wú)向圖中，與頂點(diǎn)v相鄰接的邊數(shù)稱(chēng)為該頂點(diǎn)的度，記為D(v)。在有向圖中，頂點(diǎn)v的度又分為入度和出度兩種：以頂點(diǎn)v為終點(diǎn)(弧頭)的弧的數(shù)目稱(chēng)為頂點(diǎn)v的入度，記為ID(v)；以頂點(diǎn)v為起點(diǎn)(弧尾)的弧的數(shù)目稱(chēng)為頂點(diǎn)v的出度，記為OD(v)；有向圖頂點(diǎn)v的度為該頂點(diǎn)的入度和出度之和，即

D(v)=ID(v)+OD(v)

數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第6頁(yè)。無(wú)論是有向圖還是無(wú)向圖，一個(gè)圖的頂點(diǎn)數(shù)n、邊(弧)數(shù)e和每個(gè)頂點(diǎn)的度di之間滿足以下的關(guān)系式：即在有向圖或無(wú)向圖中：所有頂點(diǎn)度數(shù)之和：邊數(shù)=2：1數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第7頁(yè)。3．完全圖、稠密圖和稀疏圖在圖G中：若G為無(wú)向圖，任意兩個(gè)頂點(diǎn)之間都有一條邊，稱(chēng)G為無(wú)向完全圖。頂點(diǎn)數(shù)為n，無(wú)向完全圖的邊數(shù)：

e=Cn2=n(n1)/2若G為有向圖，任意兩個(gè)頂點(diǎn)Vi,Vj之間都有弧<Vi,Vj>、<Vj,Vi>

，稱(chēng)G為有向完全圖。如頂點(diǎn)數(shù)為n，有向完全圖的弧數(shù)：

e=Pn2=n(n1)例如，無(wú)向圖G1就是4個(gè)頂點(diǎn)無(wú)向完全圖。若一個(gè)圖接近完全圖，則稱(chēng)其為稠密圖；反之，若一個(gè)圖含有很少條邊或?。磂＜＜n2），則稱(chēng)其為稀疏圖。數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第8頁(yè)。4．子圖若有圖G=(V,E)和G′=(V′,E′)且V′

是V的子集，即V′

V，E′是E的子集，即

E′

E則稱(chēng)圖G′為圖G的子圖。數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第9頁(yè)。5．路徑、回路和路徑長(zhǎng)度在無(wú)向圖G中，若存在一個(gè)頂點(diǎn)序列(Vp

,Vi1,Vi2,…,Vin

,Vq)，使(Vp,Vi1)，(Vi1,Vi2)，…，(Vin,Vq)均為圖G的邊，則該稱(chēng)頂點(diǎn)的序列為頂點(diǎn)Vp到頂點(diǎn)Vq的路徑。若G是有向圖，則路徑是有向的。路徑長(zhǎng)度定義為路徑上的邊數(shù)或者弧的數(shù)目。若一條路徑中不出現(xiàn)重復(fù)頂點(diǎn)，則稱(chēng)此路徑為簡(jiǎn)單路徑。若一條路徑的起點(diǎn)和終點(diǎn)相同（Vp=Vq）稱(chēng)為回路或環(huán)。除了起點(diǎn)和終點(diǎn)相同外，其余頂點(diǎn)不相同的回路，稱(chēng)為簡(jiǎn)單回路或簡(jiǎn)單環(huán)。數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第10頁(yè)。例如，在無(wú)向圖G1中：頂點(diǎn)序列（V1,V2,V3,V4）是一條從頂點(diǎn)V1到頂點(diǎn)V4，長(zhǎng)度為3的簡(jiǎn)單路徑；頂點(diǎn)序列（V1,V2,V4,V1,V3）是一條從頂點(diǎn)V1到頂點(diǎn)V3，長(zhǎng)度為4的路徑，但不是簡(jiǎn)單路徑；頂點(diǎn)序列（V1,V2,V3,V1）是一條長(zhǎng)度為3的簡(jiǎn)單回路。在有向圖G3中：頂點(diǎn)序列（V2,V3,V2）是一個(gè)長(zhǎng)度為2的有向簡(jiǎn)單環(huán)。數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第11頁(yè)。6．連通、連通分量和連通圖、生成樹(shù)在無(wú)向圖G中：如果從頂點(diǎn)Vi

到頂點(diǎn)Vj至少有一條路徑，則稱(chēng)Vi與Vj是連通的。如果圖中任意兩個(gè)頂點(diǎn)都連通，則稱(chēng)G為連通圖，否則稱(chēng)為非連通圖。在非連通圖G中，任何一個(gè)極大連通子圖稱(chēng)為G的連通分量。任何連通圖的連通分量只有一個(gè)，即其自身，而非連通圖有多個(gè)連通分量。在一個(gè)連通圖中，含有全部頂點(diǎn)的極小(邊數(shù)最少)連通子圖，稱(chēng)為該連通圖的生成樹(shù)。(包含圖的所有n個(gè)結(jié)點(diǎn)，但只含圖的n-1條邊。在生成樹(shù)中添加一條邊之后，必定會(huì)形成回路或環(huán))數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第12頁(yè)。非連通圖G4ABCDEFGIJKABCDEIJKFG圖G1和G2為連通圖非連通圖G4的三個(gè)連通分量連通圖G5ABCD連通圖G5的兩棵生成樹(shù)ABCDABCD數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第13頁(yè)。7．強(qiáng)連通、強(qiáng)連通分量和強(qiáng)連通圖在有向圖G中：存在從頂點(diǎn)Vi

到頂點(diǎn)Vj的路徑，也存在從頂點(diǎn)Vj

到頂點(diǎn)Vi的路徑，則稱(chēng)Vi與Vj是強(qiáng)連通的。如果圖中任意兩個(gè)頂點(diǎn)都是強(qiáng)連通，則稱(chēng)G為強(qiáng)連通圖，否則稱(chēng)為非強(qiáng)連通圖。在非強(qiáng)連通圖G中，任何一個(gè)極大強(qiáng)連通子圖稱(chēng)為G的強(qiáng)連通分量。任何強(qiáng)連通圖的強(qiáng)連通分量只有一個(gè)，即其自身，而非強(qiáng)連通圖有多個(gè)強(qiáng)連通分量。數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第14頁(yè)。有向圖G和強(qiáng)連通分量示例：數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第15頁(yè)。

8．權(quán)、帶權(quán)圖、有向網(wǎng)和無(wú)向網(wǎng)在一個(gè)圖中，各邊(或弧)上可以帶一個(gè)數(shù)值，這個(gè)數(shù)值稱(chēng)為權(quán)。這種每條邊都帶權(quán)的圖稱(chēng)為帶權(quán)圖或網(wǎng)有向網(wǎng)：帶權(quán)有向圖無(wú)向網(wǎng)：帶權(quán)無(wú)向圖數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第16頁(yè)。8.2圖的基本存儲(chǔ)結(jié)構(gòu)圖需存儲(chǔ)的信息：各頂點(diǎn)的數(shù)據(jù)各個(gè)邊（?。┑男畔?，包括：哪兩個(gè)頂點(diǎn)有邊（?。┤粲袡?quán)要表示出來(lái)頂點(diǎn)數(shù)、邊（?。?shù)

V0

V4

V3

V1

V2

V0

V1

V2

V3數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第17頁(yè)。a

[i][j]={0vi與vj無(wú)邊1vi與vj有邊8.2.1鄰接矩陣及其實(shí)現(xiàn)頂點(diǎn)數(shù)據(jù)存儲(chǔ)：一維數(shù)組（順序存儲(chǔ)）邊（弧）信息的存儲(chǔ)：鄰接矩陣：圖中n個(gè)頂點(diǎn)之間相鄰關(guān)系的n階方陣（即二維數(shù)組a[n][n]）鄰接矩陣中元素值情況（規(guī)定自身無(wú)邊、無(wú)?。簾o(wú)向圖a

[i][j]={0vi到vj無(wú)弧1vi到vj有弧有向圖a

[i][j]={∞或0vi與vj無(wú)邊（或vi到vj無(wú)弧）wvi與vj有邊（或vi到vj有?。┚W(wǎng)W表示邊上的權(quán)值；0表示vi與vj是同一個(gè)頂點(diǎn)∞表示一個(gè)計(jì)算機(jī)允許的、大于所有邊上權(quán)值的數(shù)。數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第18頁(yè)。1、舉例無(wú)向圖鄰接矩陣表示010101

0101010111010001100V1V2

V4

V5

V3

特點(diǎn)：對(duì)稱(chēng)行或列方向的非零元素（或1）的個(gè)數(shù)為此頂點(diǎn)的度無(wú)向網(wǎng)V1V2

V4

V5

V3

254311鄰接矩陣表示02∞4∞

2

01∞5∞

10314∞30∞∞51∞0V1V2V3V4V5V1V2V3V4V5V1V2V3V4V5V1V2V3V4V5數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第19頁(yè)。1、舉例有向圖V1V2

V3

V4

0110000000011000鄰接矩陣表示特點(diǎn)：不一定對(duì)稱(chēng)行方向的非零元素（或1）的個(gè)數(shù)為此頂點(diǎn)的出度列方向的非零元素（或1）的個(gè)數(shù)為此頂點(diǎn)的入度V1V2V3V4V1V2V3V4數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第20頁(yè)。

容易實(shí)現(xiàn)圖的操作，如：求某頂點(diǎn)的度、判斷頂點(diǎn)之間是否有邊（?。⒄翼旤c(diǎn)的鄰接點(diǎn)等等。

n個(gè)頂點(diǎn)需要n*n個(gè)單元存儲(chǔ)邊(弧);空間效率為O(n2)。對(duì)稀疏圖而言尤其浪費(fèi)空間。鄰接矩陣法優(yōu)點(diǎn)：鄰接矩陣法缺點(diǎn)：2、鄰接矩陣法特點(diǎn)數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第21頁(yè)。3、鄰接矩陣存儲(chǔ)的圖類(lèi)型定義#defineMAX100/*MAX為圖中頂點(diǎn)最多個(gè)數(shù)*/typedefintvextype;/*vextype為頂點(diǎn)的數(shù)據(jù)類(lèi)型*/typedefstruct{vextypevex[MAX];/*一維數(shù)組存儲(chǔ)頂點(diǎn)信息*/intarc[MAX][MAX];/*鄰接矩陣存儲(chǔ)邊（?。┬畔?/intvn,en;/*vn頂點(diǎn)數(shù)和en邊數(shù)*/}MGraph;/*圖類(lèi)型*/注：MGraph

既可以表示有向圖、無(wú)向圖，也可以表示有整型權(quán)的網(wǎng)數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第22頁(yè)。分析：各頂點(diǎn)信息：鍵盤(pán)輸入各邊信息：鄰接矩陣，頂點(diǎn)間有邊值為1，無(wú)邊值為0頂點(diǎn)數(shù)、邊數(shù)：鍵盤(pán)輸入例：建一個(gè)如圖所示的無(wú)向圖013424、建圖運(yùn)算建圖——就是完成圖類(lèi)型變量中各個(gè)成員值的創(chuàng)建過(guò)程。執(zhí)行時(shí)輸入數(shù)據(jù)：5601234010312142324010101

0101010111010001100數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第23頁(yè)。算法實(shí)現(xiàn)（無(wú)向圖）voidCreateGraph(MGraph*g){inti,j,v,e;scanf("%d%d",&g->vn,&g->en);/*輸入頂點(diǎn)數(shù)和邊數(shù)*/for(v=0;v<g->vn;v++)scanf("%d",&g->vex[v]);/*頂點(diǎn)數(shù)據(jù)輸入*/for(i=0;i<g->vn;i++)for(j=0;j<g->vn;j++)g->arc[i][j]=0;/*鄰接矩陣的初始值都為0*/for(e=0;e<g->en;e++)/*共有g(shù)->en條邊*/{scanf("%d%d",&i,&j);/*指明有邊的兩個(gè)頂點(diǎn)的序號(hào)*/g->arc[i][j]=1;/*有邊賦值為1*/g->arc[j][i]=1;/*建有向圖時(shí)此句不要*/}}數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第24頁(yè)。8.2.2鄰接表及其實(shí)現(xiàn)是順序與鏈接相結(jié)合的圖的存儲(chǔ)方式所有頂點(diǎn)組成一個(gè)數(shù)組，為每個(gè)頂點(diǎn)建立一個(gè)單鏈表有兩部分組成：表頭——頂點(diǎn)數(shù)組（存放頂點(diǎn)信息）表體——單鏈表（存放與頂點(diǎn)相關(guān)的邊或弧的信息）數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第25頁(yè)。1、舉例無(wú)向圖鄰接表表示V1V2

V4

V5

V3

頂點(diǎn)的度：該頂點(diǎn)所在單鏈表中表結(jié)點(diǎn)個(gè)數(shù)無(wú)向網(wǎng)V1V2

V4

V5

V3

254311鄰接表表示V1V2V3V4V50123413∧04∧202∧12∧14∧3V1V2V3V4V501234123∧4024∧521114∧133042∧3152∧1與頂點(diǎn)V1相鄰接的頂點(diǎn)在數(shù)組中的下標(biāo)權(quán)值數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第26頁(yè)。1、舉例有向圖V1V2

V3

V4

鄰接表表示12∧V1V2∧V3V401233∧0∧以頂點(diǎn)V1為始點(diǎn)的弧的終點(diǎn)頂點(diǎn)在數(shù)組中的下標(biāo)頂點(diǎn)的出度該頂點(diǎn)所在單鏈表中表結(jié)點(diǎn)個(gè)數(shù)頂點(diǎn)的入度查詢整個(gè)鄰接表中的表結(jié)點(diǎn)，與該頂點(diǎn)的序號(hào)（數(shù)組下標(biāo)）一致的表結(jié)點(diǎn)個(gè)數(shù)數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第27頁(yè)。鄰接表的缺點(diǎn)：鄰接表的優(yōu)點(diǎn)：空間效率高；容易尋找頂點(diǎn)的鄰接點(diǎn)；判斷任意兩頂點(diǎn)間是否有邊或弧，需搜索兩結(jié)點(diǎn)對(duì)應(yīng)的單鏈表，沒(méi)有鄰接矩陣方便。2、鄰接表法特點(diǎn)數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第28頁(yè)。3、鄰接表存儲(chǔ)的圖類(lèi)型定義（1）表(邊)結(jié)點(diǎn)——表示邊(或弧)信息的鏈表中結(jié)點(diǎn)adjvexnext表結(jié)點(diǎn)：adjvexnextw鄰接點(diǎn)序號(hào)(下標(biāo))下一個(gè)鄰接點(diǎn)地址權(quán)值typedefstructarcnode{intadjvex;structarcnode*next;}ArcNode,*Arc;表結(jié)點(diǎn)類(lèi)型數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第29頁(yè)。3、鄰接表存儲(chǔ)的圖類(lèi)型定義（2）頂點(diǎn)結(jié)點(diǎn)類(lèi)型vertexfirstarc頂點(diǎn)結(jié)點(diǎn)：頂點(diǎn)信息鏈表頭指針(指向第一個(gè)表結(jié)點(diǎn))typedefstructvexnode{vextypevertex;ArcNode*firstarc;}VexNode;頂點(diǎn)結(jié)點(diǎn)類(lèi)型（3）圖的鄰接表類(lèi)型typedefstruct{VexNodeadjlist[MAX];/*頂點(diǎn)結(jié)點(diǎn)所在數(shù)組*/intvn,en;}ALGraph;數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第30頁(yè)。分析：各頂點(diǎn)信息：頂點(diǎn)數(shù)據(jù)鍵盤(pán)輸入各鏈表：若頂點(diǎn)有出度弧，創(chuàng)建表結(jié)點(diǎn)，頭插入鏈表頂點(diǎn)數(shù)、邊數(shù)：鍵盤(pán)輸入例：建一個(gè)如圖所示的有向圖4、建圖運(yùn)算建圖——就是完成圖類(lèi)型變量中各個(gè)成員值的創(chuàng)建過(guò)程。執(zhí)行時(shí)輸入數(shù)據(jù)：44012302012330012312∧01∧2301233∧0∧vertexfirstarcadjvexnext數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第31頁(yè)。算法實(shí)現(xiàn)（有向圖）voidCreateAGraph(ALGraph*g){inti,j,v,e;ArcNode*p;scanf("%d%d",&g->vn,&g->en);/*輸入頂點(diǎn)數(shù)和邊數(shù)*/for(v=0;v<g->vn;v++)/*頂點(diǎn)數(shù)組元素值的獲得*/{scanf("%d",&g->adjlist[v].vertex);/*頂點(diǎn)數(shù)據(jù)鍵盤(pán)輸入*/

g->adjlist[v].firstarc=NULL;}for(e=0;e<g->en;e++)/*共有g(shù)->en條邊*/{scanf("%d%d",&i,&j);/*ij有弧，i、j為頂點(diǎn)序號(hào)*/p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=j;

/*把值為j的結(jié)點(diǎn)頭插入到i頂點(diǎn)的鏈表中*/

p->next=g->adjlist[i].firstarc;g->adjlist[i].firstarc=p;}}思考：建無(wú)向圖如何修改？數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第32頁(yè)。0A141B0452C353D254E015F123BACDFE補(bǔ)例：圖的鄰接表存儲(chǔ)表示數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第33頁(yè)。有向圖的鄰接表142301201234ABCDEABECD可見(jiàn)，在有向圖的鄰接表中不易找到指向該頂點(diǎn)的弧數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第34頁(yè)。ABECD有向圖的逆鄰接表ABCDE30342001234在有向圖的逆鄰接表中，對(duì)每個(gè)頂點(diǎn)，鏈接的是指向該頂點(diǎn)的弧數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第35頁(yè)。

8.3圖的遍歷

從圖中某個(gè)頂點(diǎn)出發(fā)遍歷圖，訪遍圖中其余頂點(diǎn)，并且使圖中的每個(gè)頂點(diǎn)僅被訪問(wèn)一次的過(guò)程。圖的遍歷有兩種方法：深度優(yōu)先搜索遍歷（DFS）廣度優(yōu)先搜索遍歷（BFS）。它們對(duì)無(wú)向圖和有向圖都適用。

數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第36頁(yè)。8.3.1連通圖的深度優(yōu)先搜索遍歷1．深度優(yōu)先搜索(dfs)的基本思想首先訪問(wèn)初始出發(fā)點(diǎn)V0，并將其標(biāo)記設(shè)置為已訪問(wèn)；然后任選一個(gè)與V0相鄰接且沒(méi)有被訪問(wèn)的鄰接點(diǎn)V1作為新的出發(fā)點(diǎn)，訪問(wèn)V1之后，將其標(biāo)記設(shè)置為已訪問(wèn)；再以V1為新的出發(fā)點(diǎn)，繼續(xù)進(jìn)行深度優(yōu)先搜索，訪問(wèn)與V1相鄰接且沒(méi)有被訪問(wèn)的任一個(gè)頂點(diǎn)V2；重復(fù)上述過(guò)程，若遇到一個(gè)所有鄰接點(diǎn)均被訪問(wèn)過(guò)的頂點(diǎn)，則回到已訪問(wèn)頂點(diǎn)序列中最后一個(gè)還存在未被訪問(wèn)的鄰接點(diǎn)的頂點(diǎn)，再?gòu)脑擁旤c(diǎn)出發(fā)繼續(xù)進(jìn)行深度優(yōu)先搜索，直到圖中所有頂點(diǎn)都被訪問(wèn)過(guò)，搜索結(jié)束。數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第37頁(yè)。

V0

V7

V6

V5

V4

V3

V2

V1

V0

V1

V3

V2

V7

V6

V5

V4例序列1：V0,V1,V3,V7,V4,V2,V5,V6從v0出發(fā)的DFS序列為：由于沒(méi)有規(guī)定訪問(wèn)鄰接點(diǎn)的順序，DFS序列不是唯一的序列2：V0,V1,V4,V7,V3,V2,V5,V6數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第38頁(yè)。算法描述：訪問(wèn)開(kāi)始頂點(diǎn)（如v）；尋找v頂點(diǎn)未被訪問(wèn)的第一個(gè)鄰接頂點(diǎn)（如w）；并把w作為開(kāi)始頂點(diǎn)繼續(xù)深度優(yōu)先搜索遍歷（遞歸思想）；直到所有頂點(diǎn)被訪問(wèn)；

其中處理：（1）訪問(wèn)頂點(diǎn)：自定義訪問(wèn)函數(shù)visit()（2）未被訪問(wèn)的鄰接點(diǎn)：定義一個(gè)標(biāo)記數(shù)組：intvisited[MAX]visited[i]=0i號(hào)頂點(diǎn)未被訪問(wèn)

1i號(hào)頂點(diǎn)已被訪問(wèn)

注意：由于函數(shù)是遞歸的，數(shù)組定義成外部數(shù)組

（3）第一個(gè)鄰接點(diǎn)：按鄰接距陣或鄰接表中邊存儲(chǔ)的順序2．dfs遞歸算法實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第39頁(yè)。函數(shù)實(shí)現(xiàn)：形參：圖變量地址，開(kāi)始頂點(diǎn)的序號(hào)（下標(biāo)）返回值：無(wú)voiddfs(MGraph*g,intv){intj,w;

visit(g,v);/*訪問(wèn)v號(hào)頂點(diǎn)*/visited[v]=1;/*v號(hào)頂點(diǎn)為已訪問(wèn)*/for(j=0;j<g->vn;j++)/*找所有的鄰接頂點(diǎn)*/if(g->arc[v][j]==1&&visited[j]==0)/*v號(hào)頂點(diǎn)與j號(hào)頂點(diǎn)間有邊，且j號(hào)頂點(diǎn)為被訪問(wèn)*/{w=j;dfs(g,w);}}2．dfs遞歸算法實(shí)現(xiàn)鄰接距陣存儲(chǔ)結(jié)構(gòu)的圖起始頂點(diǎn)的序號(hào)（下標(biāo)）voidvisit(MGraph*g,intv){printf("\n%d",g->vex[v]);}數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第40頁(yè)。按算法實(shí)現(xiàn)的dfs遍歷舉例：V0頂點(diǎn)出發(fā)遍歷結(jié)果（唯一）：V0、V1、V2、V3、V4V2頂點(diǎn)出發(fā)遍歷結(jié)果（唯一）：V2、V1、V0、V4、V3V0V1V2V3V4無(wú)向圖：鄰接矩陣存儲(chǔ)結(jié)構(gòu)：V0V1V2V3V401234數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第41頁(yè)。設(shè)計(jì)程序創(chuàng)建鄰接矩陣的無(wú)向圖，并用dfs圖中頂點(diǎn)信息并輸出：宏定義及數(shù)據(jù)類(lèi)型：#include<stdlib.h>#defineMAX20/*圖頂點(diǎn)最多不超過(guò)20*/typedefintvextype;/*圖頂點(diǎn)為int型*/typedefstruct{vextypevex[MAX];intarc[MAX][MAX];intvn,en;}MGraph;/*鄰接矩陣圖類(lèi)型*/intvisited[MAX];/*訪問(wèn)標(biāo)記數(shù)組*/數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第42頁(yè)。函數(shù)定義：voidCreateGraph(MGraph*g)/*創(chuàng)建無(wú)向圖*/{……}voidvisit(MGraph*g,intv)/*訪問(wèn)圖中某個(gè)頂點(diǎn)*/{……}voiddfs(MGraph*g,intv)/*dfs遍歷圖*/{……}main()/*主函數(shù)*/{MGraphmg;/*mg為圖結(jié)構(gòu)變量/inti,start;/*start開(kāi)始頂點(diǎn)序號(hào)*/CreateGraph(&mg);for(i=0;i<mg.vn;i++)/*訪問(wèn)標(biāo)記數(shù)組置初值0*/visited[i]=0;scanf("%d",&start);dfs(&mg,start);}數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第43頁(yè)。8.3.2連通圖的廣度優(yōu)先搜索遍歷

1．廣度優(yōu)先搜索(bfs)的基本思想從圖G=(V,E)的某個(gè)起始點(diǎn)v0出發(fā)，首先訪問(wèn)起始點(diǎn)v0，接著依次訪問(wèn)v0所有鄰接點(diǎn);再找v0的第一個(gè)鄰接頂點(diǎn)(如w1)，再依次訪問(wèn)w1頂點(diǎn)的所有未被訪問(wèn)的鄰接頂點(diǎn)；再找v0的第二個(gè)鄰接頂點(diǎn)(如w2)，再依次訪問(wèn)w2頂點(diǎn)的所有未被訪問(wèn)的鄰接頂點(diǎn)；……直到圖中所有頂點(diǎn)都被訪問(wèn)到為止。數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第44頁(yè)。

V0

V7

V6

V5

V4

V3

V2

V1V0

V1

V3

V2

V7

V6

V5

V4求圖G的以V0起點(diǎn)的的廣度優(yōu)先序列:V0,V1,V2,V3,V4,V5,V6,V7例數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第45頁(yè)。c0c1c3c2c4c5從C0出發(fā)的BFS序列為：由于沒(méi)有規(guī)定訪問(wèn)鄰接點(diǎn)的順序，BFS序列不是唯一的c0

c1

c2c3

c4

c5數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第46頁(yè)。從圖中某頂點(diǎn)vi出發(fā)：1）訪問(wèn)頂點(diǎn)vi

；（容易實(shí)現(xiàn)）2）訪問(wèn)vi

的所有未被訪問(wèn)的鄰接點(diǎn)w1,w2,…wk

；3）依次從這些鄰接點(diǎn)（在步驟2）訪問(wèn)的頂點(diǎn)）出發(fā)，訪問(wèn)它們的所有未被訪問(wèn)的鄰接點(diǎn);依此類(lèi)推，直到圖中所有訪問(wèn)過(guò)的頂點(diǎn)的鄰接點(diǎn)都被訪問(wèn)；為實(shí)現(xiàn)3），需要保存在步驟2）中訪問(wèn)的頂點(diǎn)，而且訪問(wèn)這些頂點(diǎn)鄰接點(diǎn)的順序?yàn)椋骸跋缺辉L問(wèn)先出發(fā)”的原則。故用隊(duì)列來(lái)管理鄰接點(diǎn)出發(fā)的次序。在廣度優(yōu)先遍歷算法中，需設(shè)置一隊(duì)列Q，保存已訪問(wèn)的頂點(diǎn)，并控制遍歷頂點(diǎn)的順序。2．bfs算法實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第47頁(yè)。QUEUEV0V1V2V3V4V5V6V7V1V2V3V0V4V5V6V7

V0

V7

V6

V5

V4

V3

V2

V1數(shù)據(jù)結(jié)構(gòu)：1）全局標(biāo)記數(shù)組intvisited[MAX];visited[i]=0i號(hào)頂點(diǎn)未被訪問(wèn)

1i號(hào)頂點(diǎn)已被訪問(wèn)2）鄰接表存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第48頁(yè)。算法描述：

(1)定義一個(gè)隊(duì)列Q并初始化

(2)開(kāi)始頂點(diǎn)（如v）入隊(duì)，置訪問(wèn)標(biāo)記為1；

(3)當(dāng)隊(duì)列不空時(shí)，反復(fù)做：(a)隊(duì)頭頂點(diǎn)出隊(duì)→w，訪問(wèn)w；(b)尋找w的所有未被訪問(wèn)的鄰接頂點(diǎn)入隊(duì)，置訪問(wèn)標(biāo)記為1；2．bfs算法實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第49頁(yè)。函數(shù)實(shí)現(xiàn)：形參：圖變量地址，開(kāi)始頂點(diǎn)的序號(hào)（下標(biāo)）返回值：無(wú)voidbfs(ALGraph*g,intv){inti,w;ArcNode*p;SeqQueueQ;/*循環(huán)隊(duì)列*/

InitQueue(&Q);/*初始化隊(duì)列*/EnQueue(&Q,v);/*入隊(duì)*/

visited[v]=1;/*置v號(hào)頂點(diǎn)訪問(wèn)標(biāo)記為1*/while(!EmptyQueue(&Q))/*隊(duì)列不空*/

{w=DeQueue(&Q);

/*出隊(duì)*/

visit(g,w);

/*訪問(wèn)w號(hào)頂點(diǎn),自定義函數(shù)*/p=g->adjlist[w].firstarc;/*w號(hào)頂點(diǎn)的第一個(gè)鄰接點(diǎn)地址*/

2．bfs算法實(shí)現(xiàn)鄰接表存儲(chǔ)結(jié)構(gòu)的圖起始頂點(diǎn)的序號(hào)（下標(biāo)）數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第50頁(yè)。while(p!=NULL){i=p->adjvex;/*i為鄰接頂點(diǎn)的序號(hào)（下標(biāo)）*/if(visited[i]==0){EnQueue(&Q,i);visited[i]=1;}p=p->next;}/*找所有未訪問(wèn)的鄰接點(diǎn)的循環(huán)*/}/*隊(duì)列循環(huán)*/}/*函數(shù)結(jié)束*/數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第51頁(yè)。按算法實(shí)現(xiàn)的bfs遍歷舉例：V0頂點(diǎn)出發(fā)遍歷結(jié)果（唯一）：V0、V1、V4、V3、V2V2頂點(diǎn)出發(fā)遍歷結(jié)果（唯一）：V2、V3、V1、V4、V0V0V1V2V3V4無(wú)向圖：鄰接表存儲(chǔ)結(jié)構(gòu)：V0V1V2V3V40123414∧03∧3∧124∧03∧數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第52頁(yè)。設(shè)計(jì)程序創(chuàng)建鄰接表存儲(chǔ)的無(wú)向圖，并用bfs圖中頂點(diǎn)信息并輸出：宏定義及數(shù)據(jù)類(lèi)型：#include<stdlib.h>#include"Queue.h"/*循環(huán)隊(duì)列相關(guān)操作的定義文件*/#defineMAX20/*圖頂點(diǎn)最多不超過(guò)20*/typedefintvextype;/*圖頂點(diǎn)為int型*/typedefstructarcnode{intadjvex;structarcnode*next;}ArcNode;/*表結(jié)點(diǎn)類(lèi)型*/數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第53頁(yè)。typedefstructvexnode{vextypevertex;

ArcNode*firstarc;}VexNode;/*頂點(diǎn)結(jié)點(diǎn)類(lèi)型*/typedefstruct{VexNodeadjlist[MAX];/*頂點(diǎn)結(jié)點(diǎn)所在數(shù)組*/intvn,en;}ALGraph;/*鄰接表存儲(chǔ)的圖類(lèi)型*/intvisited[MAX];/*訪問(wèn)標(biāo)記數(shù)組*/數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第54頁(yè)。函數(shù)定義：voidCreateGraph(ALGraph*g)/*創(chuàng)建圖*/{……}voidvisit(MGraph*g,intv)/*訪問(wèn)圖中某個(gè)頂點(diǎn)*/{……}voidbfs(MGraph*g,intv)/*bfs遍歷圖*/{……}main()/*主函數(shù)*/{ALGraphalg;/*mg為鄰接表圖結(jié)構(gòu)變量/inti,start;/*start開(kāi)始頂點(diǎn)序號(hào)*/CreateGraph(&alg);for(i=0;i<alg.vn;i++)/*訪問(wèn)標(biāo)記數(shù)組置初值0*/visited[i]=0;scanf("%d",&start);bfs(&alg,start);}數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第55頁(yè)。關(guān)于遍歷小結(jié)：若圖是連通的或強(qiáng)連通的，則從圖中某一個(gè)頂點(diǎn)出發(fā)可以訪問(wèn)到圖中所有頂點(diǎn)；若圖是非連通的或非強(qiáng)連通圖，則需從圖中多個(gè)頂點(diǎn)出發(fā)搜索訪問(wèn)，而每一次從一個(gè)新的起始點(diǎn)出發(fā)進(jìn)行搜索過(guò)程中得到的頂點(diǎn)訪問(wèn)序列恰為每個(gè)連通分量中的頂點(diǎn)集。數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第56頁(yè)。問(wèn)題：如何通過(guò)遍歷算法，求一個(gè)非連通圖的連同分量個(gè)數(shù)？intcount(MGraph*g){inti,m=0;for(i=0;i<g->vn;i++)if(visited[i]==0){m++;dfs(g,i);}returnm;}數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第57頁(yè)。

生成樹(shù)定義圖的遍歷過(guò)程中經(jīng)過(guò)的n個(gè)頂點(diǎn)n-1條邊即為一棵生成樹(shù)。8.4圖的應(yīng)用8.4.1連通圖的最小生成樹(shù)——無(wú)向圖的應(yīng)用在無(wú)向連通圖G中，其一個(gè)極小連通子圖(無(wú)回路)是G的生成樹(shù)，它含有圖中全部n個(gè)頂點(diǎn)，但只有n-1條邊，且不唯一。數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第58頁(yè)。深度優(yōu)先生成樹(shù)：按深度優(yōu)先遍歷生成的生成樹(shù)c0c1c3c2c4c5例c0c1c3c2c4c5數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第59頁(yè)。c0c1c3c2c4c5例c0c1c3c2c4c5廣度優(yōu)先生成樹(shù)：按廣度優(yōu)先遍歷生成的生成樹(shù)數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第60頁(yè)。非連通圖的生成森林V0V1V3V4V2V6V8V7V5V9（a）不連通的無(wú)向圖G12V0V1V3V4V2V8V7V9V6V5（c）圖G12的一個(gè)BFS生成森林V0V1V3V4V2V6V8V7V5V9（b）圖G12的一個(gè)DFS生成森林?jǐn)?shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第61頁(yè)。例

要在n個(gè)城市間建立通訊網(wǎng)，如何在保證n個(gè)城市連通的前題下最節(jié)省經(jīng)費(fèi)?ABCDEF101015121287665無(wú)向網(wǎng)G1ABCDEF10101276花費(fèi)：45ABCDEF1512865花費(fèi)：465ABCDEF107610花費(fèi)：38數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第62頁(yè)。例

要在n個(gè)城市間建立通訊網(wǎng)，如何在保證n個(gè)城市連通的前題下最節(jié)省經(jīng)費(fèi)?ABCDEF101015121287665無(wú)向網(wǎng)G1這個(gè)問(wèn)題實(shí)際上是連通圖的最小生成樹(shù)問(wèn)題。數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第63頁(yè)。ABCDEF1010151212876655ABCDEF107610最小生成樹(shù)的定義若圖G是帶權(quán)的無(wú)向連通圖（連通網(wǎng)），生成樹(shù)上各邊權(quán)值之和稱(chēng)為生成樹(shù)的代價(jià)，代價(jià)最小的生成樹(shù)稱(chēng)為最小生成樹(shù)；n個(gè)頂點(diǎn)、n-1條邊、權(quán)值之和最小。數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第64頁(yè)。1654327131791812752410連通網(wǎng)：1654321397510生成樹(shù)1：1654327139724生成樹(shù)2：代價(jià)：44代價(jià)：60最小生成樹(shù)例數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第65頁(yè)。最小生成樹(shù)的應(yīng)用集成電路布線通訊線路布線數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第66頁(yè)。如何快速有效地構(gòu)造最小生成樹(shù)？數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第67頁(yè)。

構(gòu)造最小生成樹(shù)的準(zhǔn)則：必須只使用該網(wǎng)絡(luò)中的邊來(lái)構(gòu)造最小生成樹(shù)；必須使用且僅使用n-1條邊來(lái)聯(lián)接網(wǎng)絡(luò)中的n個(gè)頂點(diǎn)。數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第68頁(yè)。一、Prim(普里姆)算法1、算法思想設(shè)原連通網(wǎng)G=(V,E)，生成的最小生成樹(shù)T=(U,TE)，則算法步驟如下：(1)任選一個(gè)頂點(diǎn)u0放入U(xiǎn)中，即初始U={u0}，TE={}(2)找連接U與V-U集合的一條權(quán)值最小的邊即找頂點(diǎn)u∈U,頂點(diǎn)v∈V-U的權(quán)值最小的一條邊(u,v)∈E；并把頂點(diǎn)v加入到U中，邊(u,v)加入到TE中，即修改U=U+{v},TE=TE+(u,v)(3)轉(zhuǎn)到（2）重復(fù)執(zhí)行，直到U=V結(jié)束數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第69頁(yè)。ABCDEF101015121287665

（a）無(wú)向網(wǎng)G1算法演示:Prim算法求解最小生成樹(shù)ABCE101512（b）求解過(guò)程數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第70頁(yè)。67ABCDEF1010151212865

（a）無(wú)向網(wǎng)G1算法演示:Prim算法求解最小生成樹(shù)ABCDEF101512765（b）求解過(guò)程數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第71頁(yè)。ABCDEF101015121287665

（a）無(wú)向網(wǎng)G1算法演示:Prim算法求解最小生成樹(shù)ABCDEF1015765（b）求解過(guò)程數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第72頁(yè)。6ABCDEF10101512128765

（a）無(wú)向網(wǎng)G1算法演示:Prim算法求解最小生成樹(shù)ABCDEF1015765（b）求解過(guò)程數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第73頁(yè)。6ABCDEF10101512128765

（a）無(wú)向網(wǎng)G1算法演示:Prim算法求解最小生成樹(shù)ABCDEF10157665（b）求解過(guò)程數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第74頁(yè)。ABCDEF101015121287665

（a）無(wú)向網(wǎng)G1算法演示:Prim算法求解最小生成樹(shù)ABCDEF1015765（b）求解過(guò)程數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第75頁(yè)。ABCDEF101015121287665

（a）無(wú)向網(wǎng)G1算法演示:Prim算法求解最小生成樹(shù)ABCDEF1015765（b）求解過(guò)程數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第76頁(yè)。86ABCDEF101015121287665

（a）無(wú)向網(wǎng)G1算法演示:Prim算法求解最小生成樹(shù)BCDEF10101575（b）求解過(guò)程A數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第77頁(yè)。6ABCDEF101015121287665

（a）無(wú)向網(wǎng)G1算法演示:Prim算法求解最小生成樹(shù)ABCDEF101075（b）求解過(guò)程15數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第78頁(yè)。67ABCDEF101015121287665

（a）無(wú)向網(wǎng)G1算法演示:Prim算法求解最小生成樹(shù)ABCDEF1010125（b）求解過(guò)程E數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第79頁(yè)。67ABCDEF101015121287665

（a）無(wú)向網(wǎng)G1算法演示:Prim算法求解最小生成樹(shù)最小生成樹(shù)ABCDEF10105E數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第80頁(yè)。例1654326513566425131163141643142116432142516543214253Prim算法最小生成樹(shù)生成過(guò)程事例(從1號(hào)頂點(diǎn)開(kāi)始)數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第81頁(yè)。課堂練習(xí)：寫(xiě)出如下連通網(wǎng)的最小生成樹(shù)過(guò)程165432496102014510106165432495106最小生成樹(shù)1165432495106最小生成樹(shù)2最小生成樹(shù)不唯一！數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第82頁(yè)。i012345d[i].adj000000d[i].dist01∞∞58定義一個(gè)結(jié)構(gòu)數(shù)組：structcost{intadj;intdist;}d[20];2、算法實(shí)現(xiàn)02315451839762說(shuō)明：i—數(shù)組下標(biāo)，又是圖中對(duì)應(yīng)頂點(diǎn)的序號(hào)d[i].adj—表示i號(hào)頂點(diǎn)與生成樹(shù)中頂點(diǎn)集合U距離最小的頂點(diǎn)號(hào)（u）d[i].dist—表示i號(hào)頂點(diǎn)與生成樹(shù)中adj頂點(diǎn)（u號(hào)頂點(diǎn)）的距離，當(dāng)dist=0時(shí)表示i號(hào)頂點(diǎn)已到生成樹(shù)中。生成樹(shù)初始選0號(hào)頂點(diǎn)數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第83頁(yè)。2、算法實(shí)現(xiàn)i012345d[i].adj000000d[i].dist01∞∞5802315451839762(1)取d數(shù)組中dist≠0的最小值，則把u=0,v=1,w=1送入生成樹(shù)，其頂點(diǎn)集為：{0,1}，并修改數(shù)組d的內(nèi)容i012345d[i].adj011000d[i].dist002∞58生成樹(shù)初始選0號(hào)頂點(diǎn)uvw數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第84頁(yè)。(2)取d數(shù)組中dist≠0的最小值，則把u=1,v=2,w=2送入生成樹(shù)，其頂點(diǎn)集為：{0,1,2}，并修改數(shù)組d的內(nèi)容i012345d[i].adj011000d[i].dist002∞58i012345d[i].adj012202d[i].dist000756i012345d[i].adj012202d[i].dist000756(3)取d數(shù)組中dist≠0的最小值，則把u=0,v=4,w=5送入生成樹(shù)，其頂點(diǎn)集為：{0,1,2,4}，并修改數(shù)組d的內(nèi)容i012345d[i].adj012442d[i].dist000306數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第85頁(yè)。(4)取d數(shù)組中dist≠0的最小值，則把u=4,v=3,w=3送入生成樹(shù)，其頂點(diǎn)集為：{0,1,2,4,3}，并修改數(shù)組d的內(nèi)容i012345d[i].adj012442d[i].dist000306i012345d[i].adj012342d[i].dist000006i012345d[i].adj012342d[i].dist000006(5)取d數(shù)組中dist≠0的最小值，則把u=2,v=5,w=6送入生成樹(shù)，其頂點(diǎn)集為：{0,1,2,4,3,5}，并修改數(shù)組d的內(nèi)容i012345d[i].adj012345d[i].dist000000數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第86頁(yè)。無(wú)向網(wǎng)的建立：#include<stdio.h>#defineINF32767typedefstruct{intu,v,w;}Tree;/*最小生成樹(shù)順序存儲(chǔ)元素類(lèi)型*/voidCreateGraph(MGraph*g){inti,j,w,e;FILE*fp;/*文件指針fp*/fp=fopen("graph.dat","r");/*打開(kāi)數(shù)據(jù)文件*/

/*圖的頂點(diǎn)數(shù)和邊數(shù)、頂點(diǎn)數(shù)據(jù)和邊的信息從文件獲取*/fscanf(fp,"%d%d",&g->vn,&g->en);for(i=0;i<g->vn;i++)/*鄰接矩陣初始化*/for(j=0;j<g->vn;j++)/*對(duì)角線為0，其余為∞*/if(i==j)g->arc[i][j]=0;elseg->arc[i][j]=INF;02315451839762數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第87頁(yè)。無(wú)向網(wǎng)的建立（續(xù)）：for(i=0;i<g->vn;i++)g->vex[i]='A'+i;/*頂點(diǎn)數(shù)據(jù)為A、B、C……*/for(e=0;e<g->en;e++){/*從文件讀取對(duì)應(yīng)邊信息，即有邊的頂點(diǎn)序號(hào)及權(quán)值*/fscanf(fp,"%d%d%d",&i,&j,&w)；

g->arc[i][j]=w;g->arc[j][i]=w;}fclose(fp);/*關(guān)閉文件*/}/*結(jié)束函數(shù)*/文件graph.dat中的內(nèi)容為：68011045058122237256343359數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第88頁(yè)。無(wú)向網(wǎng)鄰接距陣的輸出：voidOutGraph(MGraph*g){inti,j;printf("\n-------Graph--------\n");printf("\nvn=%d\ten=%d",g->vn,g->en);for(i=0;i<g->vn;i++){for(j=0;j<g->vn;j++)printf("%d\t",g->arc[i][j]);printf("\n");}}輸出：----------Graph-----------68數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第89頁(yè)。prim算法實(shí)現(xiàn)：voidPrim(MGraph*g,intv0,TreeE[]){inti,j,k,min;structcost{

intadj;intdist;}d[20];for(i=0;i<g->vn;i++)/*d數(shù)組初始化*/{d[i].adj=v0;d[i].dist=g->arc[v0][i];}}for(k=0;k<g->vn-1;k++)/*求vn-1條生成樹(shù)的邊*/{min=INF;j=-1;for(i=0;i<g->vn;i++)/*找權(quán)值最小的邊*/if(d[i].dist!=0&&d[i].dist<min){j=i;min=d[i].dist;}E[k].u=d[j].adj;E[k].v=j;E[k].w=min;/*送入生成樹(shù)*/

d[j].adj=j;d[j].dist=0;/*修改新送入生成樹(shù)頂點(diǎn)的信息*/數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第90頁(yè)。prim算法實(shí)現(xiàn)（續(xù)）：

for(i=0;i<g->vn;i++)/*修改數(shù)組d中數(shù)組*/{/*新加入到生成樹(shù)的j頂點(diǎn)與i頂點(diǎn)邊的權(quán)值更小，則修改*/if(d[i].dist!=0&&g->arc[j][i]<d[i].dist){d[i].adj=j;d[i].dist=g->arc[j][i];}}}/*結(jié)束求生成樹(shù)的for*/}/*結(jié)束函數(shù)*/數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第91頁(yè)。最小生成樹(shù)的輸出：voidOutTree(TreeE[],intk){inti;printf("\nspaningtree\n");for(i=0;i<k;i++)/*生成樹(shù)E數(shù)組中有k條邊*/printf("\n%c-----%c------%d",E[i].u,E[i].v,E[i].w);}輸出：spaningtree0--------1---------11--------2---------20--------4---------54--------3---------32--------5---------6數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第92頁(yè)。主函數(shù)：main(){MGraphG;TreeE[20];CreateGraph(&G);OutGraph(&G);Prim(&G,0,E);OutTree(E,G.vn-1);}數(shù)據(jù)結(jié)構(gòu)--圖的基本知識(shí)點(diǎn)全文共107頁(yè)，當(dāng)前為第93頁(yè)。二、Kruskal（克魯斯卡爾）算法1、算法思想把圖的所有邊按其權(quán)