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

第8章圖數(shù)據(jù)結(jié)構(gòu)--圖的基本知識點(diǎn)-PPT全文共108頁，當(dāng)前為第1頁。第8章圖8.1圖的基本概念8.2圖的基本存儲結(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連通圖的最小生成樹8.4.2拓?fù)渑判驍?shù)據(jù)結(jié)構(gòu)--圖的基本知識點(diǎn)-PPT全文共108頁，當(dāng)前為第2頁。一、現(xiàn)實(shí)中的圖8.1圖的基本概念

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

圖G是由一個頂點(diǎn)集V和一個邊集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)的對偶構(gòu)成的有限集合，記為：E={(V0,V2),(V3,V4),…}，若E為空，則圖中只有頂點(diǎn)而沒有邊。其中對偶可以表示成：

(Vi,Vj)—無序的對偶稱為邊，即(Vi,Vj)=(Vj,Vi)，其圖稱為無向圖

<Vi,Vj>—有序的對偶稱為弧，即<Vi,Vj>≠<Vj,Vi>，則稱Vi為弧尾，稱Vj為弧頭，該圖稱為有向圖二、圖的定義數(shù)據(jù)結(jié)構(gòu)--圖的基本知識點(diǎn)-PPT全文共108頁，當(dāng)前為第4頁。有向圖和無向圖示例：無向圖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)--圖的基本知識點(diǎn)-PPT全文共108頁，當(dāng)前為第5頁。在無向圖中，若存在一條邊（Vi,Vj），則稱Vi和Vj互為鄰接點(diǎn)（Adjacent）在有向圖中，若存在一條弧<Vi,Vj>，則稱Vi為此弧的起點(diǎn)，稱Vj為此弧的終點(diǎn)，稱Vi鄰接到Vj，Vj鄰接自Vi，Vi和Vj互為鄰接點(diǎn)。1．鄰接點(diǎn)

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

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

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

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

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

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

是V的子集，即V′

V，E′是E的子集，即

E′

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

,Vi1,Vi2,…,Vin

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

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

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

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

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

V0

V4

V3

V1

V2

V0

V1

V2

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

[i][j]={0vi與vj無邊1vi與vj有邊8.2.1鄰接矩陣及其實(shí)現(xiàn)頂點(diǎn)數(shù)據(jù)存儲：一維數(shù)組（順序存儲）邊（?。┬畔⒌拇鎯Γ亨徑泳仃嚕簣D中n個頂點(diǎn)之間相鄰關(guān)系的n階方陣（即二維數(shù)組a[n][n]）鄰接矩陣中元素值情況（規(guī)定自身無邊、無?。簾o向圖a

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

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

0101010111010001100V1V2

V4

V5

V3

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

V4

V5

V3

254311鄰接矩陣表示02∞4∞

2

01∞5∞

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

V3

V4

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

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

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

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

0101010111010001100數(shù)據(jù)結(jié)構(gòu)--圖的基本知識點(diǎn)-PPT全文共108頁，當(dāng)前為第24頁。算法實(shí)現(xiàn)（無向圖）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);/*指明有邊的兩個頂點(diǎn)的序號*/g->arc[i][j]=1;/*有邊賦值為1*/g->arc[j][i]=1;/*建有向圖時此句不要*/}}數(shù)據(jù)結(jié)構(gòu)--圖的基本知識點(diǎn)-PPT全文共108頁，當(dāng)前為第25頁。8.2.2鄰接表及其實(shí)現(xiàn)是順序與鏈接相結(jié)合的圖的存儲方式所有頂點(diǎn)組成一個數(shù)組，為每個頂點(diǎn)建立一個單鏈表有兩部分組成：表頭——頂點(diǎn)數(shù)組（存放頂點(diǎn)信息）表體——單鏈表（存放與頂點(diǎn)相關(guān)的邊或弧的信息）數(shù)據(jù)結(jié)構(gòu)--圖的基本知識點(diǎn)-PPT全文共108頁，當(dāng)前為第26頁。1、舉例無向圖鄰接表表示V1V2

V4

V5

V3

頂點(diǎn)的度：該頂點(diǎn)所在單鏈表中表結(jié)點(diǎn)個數(shù)無向網(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)--圖的基本知識點(diǎn)-PPT全文共108頁，當(dāng)前為第27頁。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)個數(shù)頂點(diǎn)的入度查詢整個鄰接表中的表結(jié)點(diǎn)，與該頂點(diǎn)的序號（數(shù)組下標(biāo)）一致的表結(jié)點(diǎn)個數(shù)數(shù)據(jù)結(jié)構(gòu)--圖的基本知識點(diǎn)-PPT全文共108頁，當(dāng)前為第28頁。鄰接表的缺點(diǎn)：鄰接表的優(yōu)點(diǎn)：空間效率高；容易尋找頂點(diǎn)的鄰接點(diǎn)；判斷任意兩頂點(diǎn)間是否有邊或弧，需搜索兩結(jié)點(diǎn)對應(yīng)的單鏈表，沒有鄰接矩陣方便。2、鄰接表法特點(diǎn)數(shù)據(jù)結(jié)構(gòu)--圖的基本知識點(diǎn)-PPT全文共108頁，當(dāng)前為第29頁。3、鄰接表存儲的圖類型定義（1）表(邊)結(jié)點(diǎn)——表示邊(或弧)信息的鏈表中結(jié)點(diǎn)adjvexnext表結(jié)點(diǎn)：adjvexnextw鄰接點(diǎn)序號(下標(biāo))下一個鄰接點(diǎn)地址權(quán)值typedefstructarcnode{intadjvex;structarcnode*next;}ArcNode,*Arc;表結(jié)點(diǎn)類型數(shù)據(jù)結(jié)構(gòu)--圖的基本知識點(diǎn)-PPT全文共108頁，當(dāng)前為第30頁。3、鄰接表存儲的圖類型定義（2）頂點(diǎn)結(jié)點(diǎn)類型vertexfirstarc頂點(diǎn)結(jié)點(diǎn)：頂點(diǎn)信息鏈表頭指針(指向第一個表結(jié)點(diǎn))typedefstructvexnode{vextypevertex;ArcNode*firstarc;}VexNode;頂點(diǎn)結(jié)點(diǎn)類型（3）圖的鄰接表類型typedefstruct{VexNodeadjlist[MAX];/*頂點(diǎn)結(jié)點(diǎn)所在數(shù)組*/intvn,en;}ALGraph;數(shù)據(jù)結(jié)構(gòu)--圖的基本知識點(diǎn)-PPT全文共108頁，當(dāng)前為第31頁。分析：各頂點(diǎn)信息：頂點(diǎn)數(shù)據(jù)鍵盤輸入各鏈表：若頂點(diǎn)有出度弧，創(chuàng)建表結(jié)點(diǎn)，頭插入鏈表頂點(diǎn)數(shù)、邊數(shù)：鍵盤輸入例：建一個如圖所示的有向圖4、建圖運(yùn)算建圖——就是完成圖類型變量中各個成員值的創(chuàng)建過程。執(zhí)行時輸入數(shù)據(jù)：44012302012330012312∧01∧2301233∧0∧vertexfirstarcadjvexnext數(shù)據(jù)結(jié)構(gòu)--圖的基本知識點(diǎn)-PPT全文共108頁，當(dāng)前為第32頁。算法實(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ù)鍵盤輸入*/

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)序號*/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;}}思考：建無向圖如何修改？數(shù)據(jù)結(jié)構(gòu)--圖的基本知識點(diǎn)-PPT全文共108頁，當(dāng)前為第33頁。0A141B0452C353D254E015F123BACDFE補(bǔ)例：圖的鄰接表存儲表示數(shù)據(jù)結(jié)構(gòu)--圖的基本知識點(diǎn)-PPT全文共108頁，當(dāng)前為第34頁。有向圖的鄰接表142301201234ABCDEABECD可見，在有向圖的鄰接表中不易找到指向該頂點(diǎn)的弧數(shù)據(jù)結(jié)構(gòu)--圖的基本知識點(diǎn)-PPT全文共108頁，當(dāng)前為第35頁。ABECD有向圖的逆鄰接表ABCDE30342001234在有向圖的逆鄰接表中，對每個頂點(diǎn)，鏈接的是指向該頂點(diǎn)的弧數(shù)據(jù)結(jié)構(gòu)--圖的基本知識點(diǎn)-PPT全文共108頁，當(dāng)前為第36頁。

8.3圖的遍歷

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

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

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

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

1i號頂點(diǎn)已被訪問

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

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

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

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

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)--圖的基本知識點(diǎn)-PPT全文共108頁，當(dāng)前為第46頁。c0c1c3c2c4c5從C0出發(fā)的BFS序列為：由于沒有規(guī)定訪問鄰接點(diǎn)的順序，BFS序列不是唯一的c0

c1

c2c3

c4

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

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

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

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

V0

V7

V6

V5

V4

V3

V2

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

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

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

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

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

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

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

{w=DeQueue(&Q);

/*出隊(duì)*/

visit(g,w);

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

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

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

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

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

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

構(gòu)造最小生成樹的準(zhǔn)則：必須只使用該網(wǎng)絡(luò)中的邊來構(gòu)造最小生成樹；必須使用且僅使用n-1條邊來聯(lián)接網(wǎng)絡(luò)中的n個頂點(diǎn)。數(shù)據(jù)結(jié)構(gòu)--圖的基本知識點(diǎn)-PPT全文共108頁，當(dāng)前為第69頁。一、Prim(普里姆)算法1、算法思想設(shè)原連通網(wǎng)G=(V,E)，生成的最小生成樹T=(U,TE)，則算法步驟如下：(1)任選一個頂點(diǎn)u0放入U中，即初始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)--圖的基本知識點(diǎn)-PPT全文共108頁，當(dāng)前為第70頁。ABCDEF101015121287665

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

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

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

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

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

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

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

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

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

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

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

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

for(i=0;i<g->vn;i++)/*修改數(shù)組d中數(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é)束求生成樹的for*/}/*結(jié)束函數(shù)*/數(shù)據(jù)結(jié)構(gòu)--圖的基本知識點(diǎn)-PPT全文共108頁，當(dāng)前為第92頁。最小生成樹的輸出：voidOutTree(TreeE[],intk){inti;printf("\nspaningtree\n");for(i=0;i<k;i++)/*生成樹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)--圖的基本知識點(diǎn)-PPT全文共108頁，當(dāng)前為第93頁。主函數(shù)：main(){MGraphG;TreeE[20];CreateGraph(&G);OutGraph(&G);Prim(&G,0,E);OutTree(E,G.vn-1);}數(shù)據(jù)結(jié)構(gòu)--圖的基本知識點(diǎn)-PPT全文共108頁，當(dāng)前為第94頁。二、Kruskal（克魯斯卡爾）算法1、算法思想把圖的所有邊按其權(quán)值從小到大排成升序先把權(quán)值