數(shù)據(jù)結構-圖的基本知識點

第8章圖8.1圖的基本概念8.2圖的基本存儲結構8.2.1鄰接距陣及其實現(xiàn)8.2.2鄰接表及其實現(xiàn)8.3圖的遍歷8.3.1深度優(yōu)先搜索遍歷8.3.2廣度優(yōu)先搜索遍歷8.4圖的應用8.4.1連通圖的最小生成樹8.4.2拓撲排序數(shù)據(jù)結構--圖的基本知識點全文共107頁，當前為第1頁。一、現(xiàn)實中的圖8.1圖的基本概念

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

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

V是由頂點構成的非空有限集合，記為：V＝{V0,V1,V2,…Vn-1}

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

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

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

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

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

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

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

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

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

是V的子集，即V′

V，E′是E的子集，即

E′

E則稱圖G′為圖G的子圖。數(shù)據(jù)結構--圖的基本知識點全文共107頁，當前為第9頁。5．路徑、回路和路徑長度在無向圖G中，若存在一個頂點序列(Vp

,Vi1,Vi2,…,Vin

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

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

到頂點Vj的路徑，也存在從頂點Vj

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

8．權、帶權圖、有向網(wǎng)和無向網(wǎng)在一個圖中，各邊(或弧)上可以帶一個數(shù)值，這個數(shù)值稱為權。這種每條邊都帶權的圖稱為帶權圖或網(wǎng)有向網(wǎng)：帶權有向圖無向網(wǎng)：帶權無向圖數(shù)據(jù)結構--圖的基本知識點全文共107頁，當前為第16頁。8.2圖的基本存儲結構圖需存儲的信息：各頂點的數(shù)據(jù)各個邊（?。┑男畔?，包括：哪兩個頂點有邊（?。┤粲袡嘁硎境鰜眄旤c數(shù)、邊（?。?shù)

V0

V4

V3

V1

V2

V0

V1

V2

V3數(shù)據(jù)結構--圖的基本知識點全文共107頁，當前為第17頁。a

[i][j]={0vi與vj無邊1vi與vj有邊8.2.1鄰接矩陣及其實現(xiàn)頂點數(shù)據(jù)存儲：一維數(shù)組（順序存儲）邊（?。┬畔⒌拇鎯Γ亨徑泳仃嚕簣D中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表示邊上的權值；0表示vi與vj是同一個頂點∞表示一個計算機允許的、大于所有邊上權值的數(shù)。數(shù)據(jù)結構--圖的基本知識點全文共107頁，當前為第18頁。1、舉例無向圖鄰接矩陣表示010101

0101010111010001100V1V2

V4

V5

V3

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

V4

V5

V3

254311鄰接矩陣表示02∞4∞

2

01∞5∞

10314∞30∞∞51∞0V1V2V3V4V5V1V2V3V4V5V1V2V3V4V5V1V2V3V4V5數(shù)據(jù)結構--圖的基本知識點全文共107頁，當前為第19頁。1、舉例有向圖V1V2

V3

V4

0110000000011000鄰接矩陣表示特點：不一定對稱行方向的非零元素（或1）的個數(shù)為此頂點的出度列方向的非零元素（或1）的個數(shù)為此頂點的入度V1V2V3V4V1V2V3V4數(shù)據(jù)結構--圖的基本知識點全文共107頁，當前為第20頁。

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

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

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

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

V4

V5

V3

頂點的度：該頂點所在單鏈表中表結點個數(shù)無向網(wǎng)V1V2

V4

V5

V3

254311鄰接表表示V1V2V3V4V50123413∧04∧202∧12∧14∧3V1V2V3V4V501234123∧4024∧521114∧133042∧3152∧1與頂點V1相鄰接的頂點在數(shù)組中的下標權值數(shù)據(jù)結構--圖的基本知識點全文共107頁，當前為第26頁。1、舉例有向圖V1V2

V3

V4

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

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

/*把值為j的結點頭插入到i頂點的鏈表中*/

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

8.3圖的遍歷

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

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

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

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

1i號頂點已被訪問

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

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

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

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

V0

V7

V6

V5

V4

V3

V2

V1V0

V1

V3

V2

V7

V6

V5

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

c1

c2c3

c4

c5數(shù)據(jù)結構--圖的基本知識點全文共107頁，當前為第46頁。從圖中某頂點vi出發(fā)：1）訪問頂點vi

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

的所有未被訪問的鄰接點w1,w2,…wk

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

V0

V7

V6

V5

V4

V3

V2

V1數(shù)據(jù)結構：1）全局標記數(shù)組intvisited[MAX];visited[i]=0i號頂點未被訪問

1i號頂點已被訪問2）鄰接表存儲結構數(shù)據(jù)結構--圖的基本知識點全文共107頁，當前為第48頁。算法描述：

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

(2)開始頂點（如v）入隊，置訪問標記為1；

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

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

visited[v]=1;/*置v號頂點訪問標記為1*/while(!EmptyQueue(&Q))/*隊列不空*/

{w=DeQueue(&Q);

/*出隊*/

visit(g,w);

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（a）無向網(wǎng)G1算法演示:Prim算法求解最小生成樹最小生成樹ABCDEF10105E數(shù)據(jù)結構--圖的基本知識點全文共107頁，當前為第80頁。例1654326513566425131163141643142116432142516543214253Prim算法最小生成樹生成過程事例(從1號頂點開始)數(shù)據(jù)結構--圖的基本知識點全文共107頁，當前為第81頁。課堂練習：寫出如下連通網(wǎng)的最小生成樹過程165432496102014510106165432495106最小生成樹1165432495106最小生成樹2最小生成樹不唯一！數(shù)據(jù)結構--圖的基本知識點全文共107頁，當前為第82頁。i012345d[i].adj000000d[i].dist01∞∞58定義一個結構數(shù)組：structcost{intadj;intdist;}d[20];2、算法實現(xiàn)02315451839762說明：i—數(shù)組下標，又是圖中對應頂點的序號d[i].adj—表示i號頂點與生成樹中頂點集合U距離最小的頂點號（u）d[i].dist—表示i號頂點與生成樹中adj頂點（u號頂點）的距離，當dist=0時表示i號頂點已到生成樹中。生成樹初始選0號頂點數(shù)據(jù)結構--圖的基本知識點全文共107頁，當前為第83頁。2、算法實現(xiàn)i012345d[i].adj000000d[i].dist01∞∞5802315451839762(1)取d數(shù)組中dist≠0的最小值，則把u=0,v=1,w=1送入生成樹，其頂點集為：{0,1}，并修改數(shù)組d的內容i012345d[i].adj011000d[i].dist002∞58生成樹初始選0號頂點uvw數(shù)據(jù)結構--圖的基本知識點全文共107頁，當前為第84頁。(2)取d數(shù)組中dist≠0的最小值，則把u=1,v=2,w=2送入生成樹，其頂點集為：{0,1,2}，并修改數(shù)組d的內容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送入生成樹，其頂點集為：{0,1,2,4}，并修改數(shù)組d的內容i012345d[i].adj012442d[i].dist000306數(shù)據(jù)結構--圖的基本知識點全文共107頁，當前為第85頁。(4)取d數(shù)組中dist≠0的最小值，則把u=4,v=3,w=3送入生成樹，其頂點集為：{0,1,2,4,3}，并修改數(shù)組d的內容i012345d[i].adj012442d[i].dist000306i012345d[i].adj012342d[i].dist000006i012345d[i].adj012342d[i].dist000006(5)取d數(shù)組中dist≠0的最小值，則把u=2,v=5,w=6送入生成樹，其頂點集為：{0,1,2,4,3,5}，并修改數(shù)組d的內容i012345d[i].adj012345d[i].dist000000數(shù)據(jù)結構--圖的基本知識點全文共107頁，當前為第86頁。無向網(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ù)文件*/

/*圖的頂點數(shù)和邊數(shù)、頂點數(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ù)結構--圖的基本知識點全文共107頁，當前為第87頁。無向網(wǎng)的建立（續(xù)）：for(i=0;i<g->vn;i++)g->vex[i]='A'+i;/*頂點數(shù)據(jù)為A、B、C……*/for(e=0;e<g->en;e++){/*從文件讀取對應邊信息，即有邊的頂點序號及權值*/fscanf(fp,"%d%d%d",&i,&j,&w)；

g->arc[i][j]=w;g->arc[j][i]=w;}fclose(fp);/*關閉文件*/}/*結束函數(shù)*/文件graph.dat中的內容為：68011045058122237256343359數(shù)據(jù)結構--圖的基本知識點全文共107頁，當前為第88頁。無向網(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ù)結構--圖的基本知識點全文共107頁，當前為第89頁。prim算法實現(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++)/*找權值最小的邊*/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;/*修改新送入生成樹頂點的信息*/數(shù)據(jù)結構--圖的基本知識點全文共107頁，當前為第90頁。prim算法實現(xiàn)（續(xù)）：

for(i=0;i<g->vn;i++)/*修改數(shù)組d中數(shù)組*/{/*新加入到生成樹的j頂點與i頂點邊的權值更小，則修改*/if(d[i].dist!=0&&g->arc[j][i]<d[i].dist){d[i].adj=j;d[i].dist=g->arc[j][i];}}}/*結束求生成樹的for*/}/*結束函數(shù)*/數(shù)據(jù)結構--圖的基本知識點全文共107頁，當前為第91頁。最小生成樹的輸出：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ù)結構--圖的基本知識點全文共107頁，當前為第92頁。主函數(shù)：main(){MGraphG;TreeE[20];CreateGraph(&G);OutGraph(&G);Prim(&G,0,E);OutTree(E,G.vn-1);}數(shù)據(jù)結構--圖的基本知識點全文共107頁，當前為第93頁。二、Kruskal（克魯斯卡爾）算法1、算法思想把圖的所有邊按其權