數(shù)據(jù)結(jié)構(gòu) 課件 第8章 圖

第8章圖總體要求：熟悉圖的定義熟悉圖的抽象數(shù)據(jù)類型描述中各種操作的含義掌握圖的存儲結(jié)構(gòu)熟練掌握圖各種存儲接結(jié)構(gòu)下的建立、遍歷算法熟練掌握帶權(quán)圖的最小生成樹的定義和普里姆算法、克魯斯卡爾算法熟練掌握帶權(quán)圖的最短路徑的定義和迪杰斯特拉算法、弗洛伊德算法核心技能點：具有圖理論應用于實際問題的能力1第8章圖8.1圖的實例及概念8.1.1實例8.1.2圖的定義和基本概念8.2圖的存儲結(jié)構(gòu)及實現(xiàn)8.2.1鄰接矩陣8.2.2鄰接鏈表8.2.3圖的ADT定義8.3遍歷圖8.3.1深度優(yōu)先搜索法8.3.2廣度優(yōu)先搜索2第8章圖8.4最小生成樹8.4.1最小生成樹的基本概念8.4.2普里姆算法8.4.3克魯斯卡爾算法8.5最短路徑8.5.1從某個源點到其它各頂點的最短路徑8.5.2求每一對頂點之間最短路徑8.6上機實驗本章小結(jié)習題3第8章圖擴展技能點：圖各種存儲結(jié)構(gòu)和算法C語言環(huán)境下的實現(xiàn)相關知識點：C語言數(shù)組的知識C語言結(jié)構(gòu)體的知識C語言指針的知識C語言函數(shù)的知識離散數(shù)學圖論的知識4第8章圖學習重點：熟悉圖的定義熟悉圖的抽象數(shù)據(jù)類型描述中各種操作的含義掌握圖的存儲結(jié)構(gòu)熟練掌握圖各種存儲接結(jié)構(gòu)下的建立、遍歷算法熟練掌握帶權(quán)圖的最小生成樹的定義和普里姆算法、克魯斯卡爾算法熟練掌握帶權(quán)圖的最短路徑的定義和迪杰斯特拉算法、弗洛伊德算法5第8章圖圖(Graph)是一種復雜的非線性結(jié)構(gòu)。在線性表中，數(shù)據(jù)元素滿足唯一的線性關系，每個元素(除第一個元素和最后一個元素之外)，只有一個直接前趨和直接后繼；在樹型結(jié)構(gòu)中，數(shù)據(jù)元素有明顯的層次關系，并且每個元素只與上層一個元素(雙親結(jié)點)及下層中多個元素(孩子結(jié)點)相關；而在圖型結(jié)構(gòu)中，數(shù)據(jù)元素之間的關系是任意的，任何兩個元素都可以相關，因此它較線性結(jié)構(gòu)和樹結(jié)構(gòu)更復雜。圖在各個領域的應用是十分廣泛的。在計算機的應用領域如開關理論、邏輯設計、人工智能、形式語言、操作系統(tǒng)、編譯程序以及信息檢索內(nèi)，圖都起著重要的作用；在其他領域如電路分析、項目規(guī)劃、遺傳學、控制論以及一些社會科學中，圖的應用也非常普遍。有關圖論的內(nèi)容是離散數(shù)學的主要內(nèi)容之一，因此本章將主要討論圖在計算機中的存儲表示、操作的實現(xiàn)及典型的應用等。6第8章圖8.1圖的實例及概念8.1.1實例在日常生活中，對象和對象之間的關系常?？梢杂冒c和線的示意圖來表示。如圖8.1表示的是我國部分省市之間的鐵路交通示意圖，反映了這幾個城市之間的鐵路分布情況。其中，省市用點表示，點和點之間的連線代表了對應的兩個省市之間的鐵路線。7第8章圖8

從以上例子可以看出，點及點之間的連線可被用來反映客觀世界中某些對象之間的特定關系。圖8．1我國部分省市之間的鐵路交通示意圖第8章圖8.1.2圖的定義和基本概念1．圖的定義圖(graph)是由頂點集合(vertex)及頂點間的關系集合組成的一種數(shù)據(jù)結(jié)構(gòu)：Graph=(V，E)其中，V={x|x∈某個數(shù)據(jù)對象}是頂點的有窮非空集合；E={(x,y)|x,y∈V}或E={<x,y>|x,y∈V&&Path(x,y)}是頂點之間關系的有窮集合，也叫做邊(Edge)集合。Path(x,y)表示從x到y(tǒng)的一條單向通路，它是有方向的。9第8章圖2．一些與圖有關的基本概念(1)有向圖(DirectedGraph)與無向圖(UndirectedGraph)。在有向圖中，頂點對<x,y>是有序的，它稱為從頂點x到頂點y的一條有向邊。因此，<x,y>與<y,x>是不同的兩條邊。此時，頂點對<x,y>用一對尖括號括起來，x是有向邊的始點，y是有向邊的終點。在無向圖中，頂點對(x,y)是無序的，它稱為與頂點x和頂點y相關聯(lián)的一條邊，這條邊沒有特定的方向，(x,y)與(y,x)是同一條邊。一般為了有別于有向圖，頂點對用一對圓括號括起來。圖8.2中有4個圖，其中圖G1和G2是無向圖，G1的頂點集合為V(G1)={0，l，2，3}，邊集合為E(G1)={(0，1)，(0，2)，(0，3)，(1，2)，(1，3)，(2，3)}。G2的頂點集合為V(G2)={0，1，2，3，4，5，6}，邊集合為E(G2)={(0，1)，(0，2)，(1，3)，(1，4)，(2，5)，(2，6)}。在無向圖中邊上不加箭頭。圖G3和G4是有向圖，G3的頂點集合為V(G3)={0，1，2}，邊集合為E(G3)={<0，1>，<l，0>，<1，2>}。G4的頂點集合為V(G4)={0，1，2，3}，邊集合為E(G4)={<0，1>，<l，0>，<0，2>，<2，0>，<0，3>，<3，0>，<l，2>，<2，1>，<1，3>，<3，1>，<2，3>，<3，2>}。在有向圖中，為了表示有向邊，按邊的方向用箭頭畫出，箭頭從邊的始點指向終點。10第8章圖11圖8．2圖的示例第8章圖并不是所有的圖都是我們的研究對象，在討論圖的時候，對討論的對象有一些限制：①圖中不能有從自身到自身的邊(即自身環(huán)SelfLoop)，就是說不應有形如(x,x)或<y,y>的邊。如圖8.3(a)的帶自身環(huán)的圖不在本章討論之內(nèi)。②與兩個特定頂點相關聯(lián)的邊不能多于一條。如圖8.3(b)所示的多重圖也不討論。12圖8．3本章不予討論的圖(a)帶自身環(huán)的圖(b)多重圖第8章圖(2)完全圖(CompleteGraph)。在有n個頂點的無向圖中，若有n(n-1)/2條邊，則稱此圖為完全無向圖，如圖8．2(a)所示的圖G1。在有n個頂點的有向圖中，若有n(n-1)條邊，則稱此圖為完全有向圖，如圖8.1(d)所示的圖G4。完全圖中的邊數(shù)達到最大。(3)權(quán)(Weight)。有些圖的邊附帶有數(shù)據(jù)信息，這些附帶的數(shù)據(jù)信息稱為權(quán)。權(quán)可以表示實際問題中從一個頂點到另一個頂點的距離、花費的代價、所需的時間，等等。帶權(quán)的圖稱作網(wǎng)絡(Network)。圖8.4就是帶權(quán)圖。其中，圖8.4(a)是一個工程的施工進度圖，圖8.4(b)是一個交通網(wǎng)絡圖。13第8章圖14圖8.4帶權(quán)的圖(a)是一個工程的施工進度圖(b)是一個交通網(wǎng)絡圖第8章圖(4)鄰接頂點(AdjacentVertex)。如果(x,y)是E中的一條邊，則稱x與y互為鄰接頂點，且邊(x,y)依附于頂點x和y。在圖8．2的G2中，與頂點1相鄰接的頂點有0，3，4。在G2中依附于頂點2的邊有(0，2)、(2，5)和(2，6)。如果<x,y>是圖中的一條有向邊，則稱頂點x鄰接到頂點y，頂點y鄰接自頂點x，邊<x,y>是頂點x的出邊(Outedge)，是頂點y的入邊(Inedge)。例如，在圖8．2的G3中，有向邊<1，2>的頂點1鄰接到頂點2，頂點2鄰接自頂點1，頂點1的出邊是<1，0>和<1，2>，入邊是<0，1>。(5)子圖(Subgraph)。設有兩個圖G1=x(V,E)和G2=(V,E)。若V(G1)V(G2)且E(G1)E(G2)則稱圖G1是圖G2的子圖。15第8章圖(6)頂點的度(Degree)。一個頂點v的度是與它相關聯(lián)的邊的條數(shù)，記作TD(v)。在有向圖中，頂點的度等于該頂點的人度與出度之和。其中，頂點v的人度是以v為終點的有向邊(入邊)的條數(shù)，記作ID(v)；頂點v的出度是以v為始點的有向邊(出邊)的條數(shù)，記作OD(v)。頂點v的度TD(v)=ID(v)+OD(v)。一般地，若圖G中有n個頂點，e條邊(或弧)，則

E={{}(7)路徑(Path)。在圖G=<V,E)中，若從頂點vi出發(fā)，沿一些邊經(jīng)過一些頂點vp1,vp2,…vpm到達頂點vj。則稱頂點序列(vi,vp1,vp2,…vpm,vj)為從頂點vi到頂點vj的路徑。它經(jīng)過的邊(vi,vp1)，(vp1,vp2),…(vpm,vj)應是屬于E的邊。16第8章圖(7)路徑(Path)。在圖G=<V,E)中，若從頂點vi出發(fā)，沿一些邊經(jīng)過一些頂點vp1,vp2,…vpm到達頂點vj。則稱頂點序列(vi,vp1,vp2,…vpm,vj)為從頂點vi到頂點vj的路徑。它經(jīng)過的邊(vi,vp1)，(vp1,vp2),…(vpm,vj)應是屬于E的邊。(8)路徑長度(PathLength)。對于不帶權(quán)的圖，路徑長度是指此路徑上邊的條數(shù)。對于帶權(quán)圖，路徑長度是指路徑上各邊的權(quán)之和。(9)簡單路徑與回路(Cycle)。若路徑上各頂點v1,v2…vmv1,均不互相重復，則稱這樣的路徑為簡單路徑。若路徑上第一個頂點v1與最后一個頂點vm重合，則稱這樣的路徑為回路或環(huán)。如圖8.5所示。圖8.5(a)所示是簡單路徑，圖8.5(b)所示是非簡單路徑。通常在解決實際應用問題時，只考慮簡單路徑。圖8．5(c)所示是回路。17第8章圖18圖8.5簡單路徑與回路(a)簡單路徑(b)非簡單路徑(c)回路第8章圖(10)連通圖與連通分量(ConnectedGraph&ConnectedComponent)。在無向圖中若從頂點v1到頂點v2有路徑，則稱頂點v1與v2是連通的。如果圖中任意一對頂點都是連通的，則稱此圖是連通圖。非連通圖的極大連通子圖叫做連通分量。(11)強連通圖與強連通分量(StronglyConnectedGraph)。在有向圖中，若對于每一對頂點vi和vj，都存在一條從vi到vj和從vj到vi的路徑，則稱此圖是強連通圖。非強連通圖的極大強連通子圖叫做強連通分量。(12)生成樹(SpanningTree)。一個連通圖的生成樹是它的極小連通子圖，在n個頂點的情形下，有n-l條邊。但有向圖則可能得到它的由若干有向樹組成的生成森林。19第8章圖8.2圖的存儲結(jié)構(gòu)及實現(xiàn)圖的存儲結(jié)構(gòu)比較多。對于圖的存儲結(jié)構(gòu)的選擇取決于具體的應用和需要進行的運算。下面給出兩種常用的圖的結(jié)構(gòu)，鄰接矩陣和鄰接表。8.2.1鄰接矩陣在圖的鄰接矩陣(AdjacencyMatrix)表示中，除了一個記錄各個頂點信息的頂點表外，還有一個稱之為鄰接矩陣的表示各個頂點之間關系的矩陣。若設圖A=(V，E)是一個有n個頂點的圖，則圖的鄰接矩陣是一個二維數(shù)組A.edge[n][n]，它的定義為：1，if((i，j)or<i，j>∈E)A.edge[i][j]=0，otherwise20第8章圖圖8．6給出了無向圖和它的鄰接矩陣，圖8．7給出了有向圖和它的鄰接矩陣。從圖8．6中可知，無向圖的鄰接矩陣是對稱的，將第i行的元素值或第i列的元素值累加起來就得到頂點i的度。但有向圖的鄰接矩陣可能是不對稱的。如果第i行的A．Edge[i][j]=1，則表示有一條從頂點i到頂點j的有向邊，將第i行的所有元素值累加起來就得到頂點i的出度；如果第j列的A．Edge[k][j]=l，則表示有一條從頂點k到頂點j的有向邊，將第j列的所有元素值累加起來就得到頂點j的入度。21第8章圖22圖8．6無向圖和它的鄰接矩陣圖8．7有向圖和它的鄰接矩陣第8章圖對于網(wǎng)絡(或帶權(quán)圖)，鄰接矩陣定義如下：

Wi,j,if((i!=j)&&<i,j>∈Eor(i,j)∈E)A.edge[i][j]=∝,otherwise,but(i≠j)0,if(i==j)圖8．8給出一個網(wǎng)絡的鄰接矩陣。23圖8．8一個網(wǎng)絡和它的鄰接矩陣第8章圖對于用鄰接矩陣表示的圖來說，要想確定“圖中有多少條邊?”和“圖是否連通?”等問題，需要檢查除對角線外的所有n2-n個矩陣元素，時間開銷很高。當圖中的邊數(shù)e遠遠小于圖的鄰結(jié)矩陣元素個數(shù)n2時，圖的鄰接矩陣變成稀疏矩陣，存儲利用率很低。為此，可以改用后面介紹的鄰接表。下面給出用鄰接矩陣作為存儲表示的圖的類型定義及算法實現(xiàn)。其中有一個類型為順序表的頂點表向量Vertices，用以存儲頂點的信息，還有—個作為鄰接矩陣使用的二維數(shù)組edge，用以存儲圖中的邊，其矩陣元素個數(shù)取決于頂點個數(shù)，與邊數(shù)無關。當前頂點個數(shù)在順序表中聲明，當前邊數(shù)由CurrentEdges指明。24第8章圖以下的類型定義和函數(shù)都放在鄰接矩陣頭文件AdjMGraph.h中。#include"SeqList.h"/*包含順序表頭文件*/typedefstruct{SeqListVertices;/*存放頂點的順序表*/intedge[MaxVertices][MaxVertices];/*存放邊的鄰接矩陣*/intCurrentEdges;/*邊的條數(shù)*/}AdjMWGraph;/*圖的結(jié)構(gòu)體定義*/1.鄰接矩陣的初始化鄰接矩陣的初始化可表示為：voidInitiate(AdjMWGraph*G,intn)；其中參數(shù)G表示指定的鄰接矩陣，其類型為AdjMWGraph，參數(shù)n表示頂點個數(shù)。函數(shù)的功能：實現(xiàn)鄰接矩陣的初始化。25第8章圖處理過程為：⑴使圖G鄰接矩陣的對角線元素為0，其它元素為∞；⑵使圖G鄰接矩陣的邊數(shù)為0；⑶圖G頂點表向量Vertices的初始化。函數(shù)實現(xiàn)如下：voidInitiate(AdjMWGraph*G,intn){inti,j;for(i=0;i<n;i++)for(j=0;j<n;j++){if(i==j)G->edge[i][j]=0;elseG->edge[i][j]=MaxWeight;}26第8章圖G->CurrentEdges=0;/*邊的條數(shù)置為0*/ListInitiate(&G->Vertices);/*順序表初始化*/}2.圖的鄰接矩陣加入新頂點圖的鄰接矩陣加入新頂點可表示為：voidInsertVertex(AdjMWGraph*G,DataTypevertex)；其中參數(shù)G表示指定的鄰接矩陣，其類型為AdjMWGraph，參數(shù)vertex表示頂點，其類型為DataType。函數(shù)的功能：實現(xiàn)圖的鄰接矩陣加入新頂點。27第8章圖處理過程為：⑴圖G頂點表向量Vertices中增加一個新元素，元素個數(shù)加1，即在順序表表尾插入；⑵返回。函數(shù)實現(xiàn)如下：voidInsertVertex(AdjMWGraph*G,DataTypevertex)/*在圖G中插入頂點vertex*/{ListInsert(&G->Vertices,G->Vertices.size,vertex);}3.圖的鄰接矩陣加入新邊圖的鄰接矩陣加入新邊可表示為：voidInsertEdge(AdjMWGraph*G,intv1,intv2,intweight)；其中參數(shù)G表示指定的鄰接矩陣，其類型為AdjMWGraph，參數(shù)v1,v2表示頂點編號，其類型為int，weight為邊的權(quán)值。28第8章圖函數(shù)的功能：實現(xiàn)圖的鄰接矩陣加入新邊。處理過程為：若v1,v2合法，則⑴使圖G->edge[v1][v2]=weight；⑵G->CurrentEdges++。函數(shù)實現(xiàn)如下：voidInsertEdge(AdjMWGraph*G,intv1,intv2,intweight)/*在圖G中插入邊<v1,v2>，邊<v1,v2>的權(quán)為weight*/{if(v1<0||v1>G->Vertices.size||v2<0||v2>G->Vertices.size){printf("參數(shù)v1或v2越界出錯!\n");exit(1);}G->edge[v1][v2]=weight;G->CurrentEdges++;}29第8章圖4.圖的鄰接矩陣刪除邊圖的鄰接矩陣刪除邊可表示為：voidDeleteEdge(AdjMWGraph*G,intv1,intv2)；其中參數(shù)G表示指定的鄰接矩陣，其類型為AdjMWGraph，參數(shù)v1,v2表示頂點編號，其類型為int。函數(shù)的功能：實現(xiàn)圖的鄰接矩陣刪除邊。處理過程為：若v1,v2合法，則⑴使圖G->edge[v1][v2]=MaxWeight；⑵G->CurrentEdges--。30第8章圖函數(shù)實現(xiàn)如下：voidDeleteEdge(AdjMWGraph*G,intv1,intv2)/*在圖G中刪除邊<v1,v2>*/{if(v1<0||v1>G->Vertices.size||v2<0||v2>G->Vertices.size||v1==v2){printf("參數(shù)v1或v2越界出錯!\n");exit(1);}G->edge[v1][v2]=MaxWeight;G->CurrentEdges--;}31第8章圖4.圖的鄰接矩陣刪除頂點圖的鄰接矩陣刪除頂點可表示為：voidDeleteVertex(AdjMWGraph*G,intv)；其中參數(shù)G表示指定的鄰接矩陣，其類型為AdjMWGraph，參數(shù)v表示頂點編號，其類型為int。函數(shù)的功能：實現(xiàn)圖的鄰接矩陣刪除頂點。處理過程為：⑴若G->edge[i][j]是與該頂點相關的所有邊，G->CurrentEdges--；⑵刪除該頂點所在的行；⑶刪除該頂點所在的列；⑷圖G頂點表向量Vertices中刪除該元素，元素個數(shù)減1。32第8章圖函數(shù)實現(xiàn)如下：voidDeleteVertex(AdjMWGraph*G,intv)/*刪除圖G頂點v*/{intn=ListLength(G->Vertices),i,j;DataTypex;for(i=0;i<n;i++)for(j=0;j<n;j++)if((i==v||j==v)&&G->edge[i][j]>0&&G->edge[i][j]<MaxWeight)G->CurrentEdges--;/*被刪除邊計數(shù)*/33第8章圖for(i=v;i<n;i++)for(j=0;j<n;j++)G->edge[i][j]=G->edge[i+1][j];/*刪除第v行*/for(i=0;i<n;i++)for(j=v;j<n;j++)G->edge[i][j]=G->edge[i][j+1];/*刪除第v列*/ListDelete(&G->Vertices,v,&x);/*刪除結(jié)點v*/}34第8章圖5.尋找第一個鄰接頂點尋找第一個鄰接頂點可表示為：intGetFirstVex(AdjMWGraphG,intv)；其中參數(shù)G表示指定的鄰接矩陣，其類型為AdjMWGraph，參數(shù)v表示頂點編號，其類型為int。函數(shù)的功能：在圖G中尋找序號為v的頂點的第一個鄰接頂點，如果這樣的鄰接頂點存在則返回該鄰接頂點的序號，否則返回-1。處理過程為：若v合法，在鄰接矩陣的第v行，尋找G.edge[v][col]>0&&G.edge[v][col]<MaxWeight)的元素。尋找到，返回col，否則返回-1。35第8章圖函數(shù)實現(xiàn)如下：intGetFirstVex(AdjMWGraphG,intv)/*在圖G中尋找序號為v的頂點的第一個鄰接頂點*//*如果這樣的鄰接頂點存在則返回該鄰接頂點的序號，否則返回-1*/{intcol;if(v<0||v>=G.Vertices.size){printf("參數(shù)v1越界出錯!\n");exit(1);}for(col=0;col<=G.Vertices.size;col++)if(G.edge[v][col]>0&&G.edge[v][col]<MaxWeight)returncol;return-1;}36第8章圖6.尋找下一個鄰接頂點尋找下一個鄰接頂點可表示為：intGetNextVex(AdjMWGraphG,intv1,intv2)；其中參數(shù)G表示指定的鄰接矩陣，其類型為AdjMWGraph，參數(shù)v1，v2表示頂點編號，其類型為int。函數(shù)的功能：在圖G中尋找序號為v1頂點的鄰接頂點v2的下一個鄰接頂點，如果這樣的鄰接頂點存在則返回該鄰接頂點的序號，否則返回-1。處理過程為：若v1，v2合法，在鄰接矩陣的第v1行，從v2+1開始尋找G.edge[v1][col]>0&&G.edge[v1][col]<MaxWeight)的元素。尋找到，返回col，否則返回-1。37第8章圖函數(shù)實現(xiàn)如下：intGetNextVex(AdjMWGraphG,intv1,intv2)/*在圖G中尋找v1頂點的鄰接頂點v2的下一個鄰接頂點*//*如果這樣的鄰接頂點存在則返回該鄰接頂點的序號，否則返回-1*//*這里v1和v2都是相應頂點的序號*/{intcol;if(v1<0||v1>=G.Vertices.size||v2<0||v2>=G.Vertices.size){printf("參數(shù)v1或v2越界出錯!\n");exit(1);}for(col=v2+1;col<G.Vertices.size;col++)if(G.edge[v1][col]>0&&G.edge[v1][col]<MaxWeight)returncol;return-1;}38第8章圖7.建立鄰接矩陣建立鄰接矩陣可表示為：voidCreatGraph(AdjMWGraph*G,DataTypeV[],intn,RowColWeightE[],inte)；其中參數(shù)G表示指定的鄰接矩陣，其類型為AdjMWGraph，參數(shù)V表示頂點數(shù)組，其類型為DataType，參數(shù)n表示頂點數(shù)，其類型為int，參數(shù)E表示邊數(shù)組，其類型為RowColWeight，函數(shù)外定義,參數(shù)e表示邊數(shù)，其類型為int。函數(shù)的功能：在圖G中插入n個頂點信息V和e條邊信息。處理過程為：⑴頂點順序表初始化⑵頂點插入⑶邊插入39第8章圖函數(shù)實現(xiàn)如下：/*建立鄰接矩陣的AdjMGraphCreate.h*/typedefstruct{introw;/*行下標*/intcol;/*列下標*/intweight;/*權(quán)值*/}RowColWeight;/*邊信息三元組結(jié)構(gòu)體定義*/voidCreatGraph(AdjMWGraph*G,DataTypeV[],intn,RowColWeightE[],inte)/*在圖G中插入n個頂點信息V和e條邊信息E*/{inti,k;Initiate(G,n);/*頂點順序表初始化*/for(i=0;i<n;i++)InsertVertex(G,V[i]);/*頂點插入*/for(k=0;k<e;k++)InsertEdge(G,E[k].row,E[k].col,E[k].weight);/*邊插入*/}40第8章圖有興趣的讀者，可以用下面函數(shù)測試，看一看執(zhí)行的結(jié)果。/*測試主函數(shù)*/#include<stdio.h>#include<stdlib.h>typedefcharDataType;#defineMaxSize100#defineMaxVertices10#defineMaxEdges100#defineMaxWeight10000#include"AdjMGraph.h"#include"AdjMGraphCreate.h"41第8章圖voidmain(void){AdjMWGraphg1;DataTypea[]={'A','B','C','D','E'};RowColWeightrcw[]={{0,1,10},{0,4,20},{1,3,30},{2,1,40},{3,2,50}};intn=5,e=5;inti,j;CreatGraph(&g1,a,n,rcw,e);DeleteEdge(&g1,0,4);/*刪除邊<0,4>*/DeleteVertex(&g1,3);/*刪除頂點3*/42第8章圖printf("頂點集合為：");for(i=0;i<g1.Vertices.size;i++)printf("%c",g1.Vertices.list[i]);printf("\n");printf("權(quán)值集合為：\n");for(i=0;i<g1.Vertices.size;i++){for(j=0;j<g1.Vertices.size;j++)printf("%5d",g1.edge[i][j]);printf("\n");}}43第8章圖8.2.2鄰接鏈表圖的鄰接鏈表（AdjacencyList）存儲結(jié)構(gòu)是一種順序分配和鏈式分配相結(jié)合的存儲結(jié)構(gòu)。它包括兩個部分，一部分是向量；另一部分是鏈表。原則上，在鏈表部分共有n個鏈表，即每個頂點一個鏈表。每個鏈表由一個表頭結(jié)點和若干個表結(jié)點組成。表頭結(jié)點用來指示第i個頂點vi的數(shù)據(jù)信息（data）、是否被訪問過（tag）和所對應的鏈表指針（adj）；表結(jié)點由頂點編號域(vertexnum)和鏈域（next）所組成,對帶權(quán)圖還可增加權(quán)值域（weight）。頂點域指示了與vi相鄰接的頂點的序號，所以一個表結(jié)點實際代表了一條依附于vi的邊；鏈域指示了依附于vi的另一條邊的表結(jié)點。因此，第i個鏈表就表示了依附于vi的所有邊。對有向圖來講，第i個鏈表就表示了從vi發(fā)出的所有弧。如果要表示指向vi的弧，則要采用逆鄰接鏈表，第i個鏈表就表示了指向vi的所有弧。鄰接鏈表中的表頭部分是向量，用來存儲n個表頭結(jié)點。向量的下標指示了頂點的序號。44第8章圖在C語言中，圖的鄰接表存儲表示如下。typedefstructNode{intvertexNum;/*頂點編號域*/intweight/*權(quán)值域*/structNode*next;/*鏈表指針*/}Edge;/*表結(jié)點*/typedefstruct{DataTypedata;/*結(jié)點信息*/inttag;/*標識域*/Edge*adj;/*頭指針*/}AdjLHeight;/*表頭結(jié)點45第8章圖typedefstruct{AdjLHeighta[MaxVertices];/*表頭向量*/intnumOfVerts;/*頂點數(shù)*/intnumOfEdges;/*邊數(shù)*/}AdjLGraph;例如，圖8.9為無向圖及其鄰接鏈表，圖8.10為有向圖及其鄰接鏈表、逆接鏈表，圖8.11為有向帶權(quán)圖和其鄰接鏈表。46第8章圖47圖8.9無向圖和其鄰接鏈表（a）無向圖（b）鄰接鏈表第8章圖48圖8.10有向圖及其鄰接鏈表、逆接鏈表（a）無向圖（b）鄰接鏈表（c）逆接鏈表第8章圖49圖8.11有向帶權(quán)圖和其鄰接鏈表（a）有向帶權(quán)圖（b）鄰接鏈表第8章圖下面給出用鄰接鏈表作為存儲表示的圖的類型定義及常用算法實現(xiàn)。以上的類型定義和函數(shù)都放在鄰接表頭文件AdjLGraph.h中。1.鄰接表的初始化鄰接表的初始化可表示為：AdjInitiate(AdjLGraph*G)；其中參數(shù)G表示指定的鄰接表，其類型為AdjLGraph。函數(shù)的功能：實現(xiàn)鄰接表的初始化。處理過程為：⑴使圖G鄰接表頂點數(shù)為0；⑵使圖G鄰接表的邊數(shù)為0；⑶圖G頂點表向量a初始化。50第8章圖函數(shù)實現(xiàn)如下：AdjInitiate(AdjLGraph*G)/*圖的鄰接表初始化*/{inti;G->numOfVerts=0;G->numOfEdges=0;for(i=0;i<MaxVertices;i++){G->a[i].tag=0;G->a[i].adj=NULL;}}51第8章圖2.銷毀鄰接表銷毀鄰接表可表示為：AdjDestroy(AdjLGraph*G)；其中參數(shù)G表示指定的鄰接表，其類型為AdjLGraph。函數(shù)的功能：實現(xiàn)鄰接表的銷毀。處理過程為：從0號頂點開始，釋放圖G鄰接表中頂點。函數(shù)實現(xiàn)如下：52第8章圖AdjDestroy(AdjLGraph*G)/*銷毀鄰接表*/{inti;Edge*p,*q;for(i=0;i<G->numOfVerts;i++){p=G->a[i].adj;while(p!=NULL){q=p->next;free(p);p=q;}}}53第8章圖3.圖的鄰接表加入新頂點圖的鄰接表加入新頂點可表示為：voidInsertVertex(AdjLGraph*G,inti,DataTypevertex)；其中參數(shù)G表示指定的鄰接表，其類型為AdjLGraph，參數(shù)vertex表示頂點，其類型為DataType。I為頂點編號。函數(shù)的功能：實現(xiàn)圖的鄰接表加入新頂點。處理過程為：⑴若i合法，圖G頂點表向量a[i]中增加一個新元素，頂點個數(shù)加1；⑵返回。54第8章圖函數(shù)實現(xiàn)如下：voidInsertVertex(AdjLGraph*G,inti,DataTypevertex)/*鄰接表插入頂點*/{if(i>=0&&i<MaxVertices){G->a[i].data=vertex;G->numOfVerts++;}elseprintf("頂點越界");}55第8章圖4.圖的鄰接表加入新邊圖的鄰接表加入新邊可表示為：voidInsertEdge(AdjLGraph*G,intv1,intv2)；其中參數(shù)G表示指定的鄰接表，其類型為AdjLGraph，參數(shù)v1,v2表示頂點編號，其類型為int。函數(shù)的功能：實現(xiàn)圖的鄰接表加入新邊。處理過程為：若v1,v2合法，則⑴建立新結(jié)點p，p->next=G->a[v1].adj，G->a[v1].adj=p；⑵G->numOfEdges++。56第8章圖函數(shù)實現(xiàn)如下：voidInsertEdge(AdjLGraph*G,intv1,intv2)/*鄰接表插入邊*/{Edge*p;if(v1<0||v1>=G->numOfVerts||v2<0||v2>=G->numOfVerts){printf("參數(shù)v1或v2越界出錯!");exit(0);}p=(Edge*)malloc(sizeof(Edge));p->next=G->a[v1].adj;G->a[v1].adj=p;G->numOfEdges++;}57第8章圖5.圖的鄰接表刪除邊圖的鄰接矩陣刪除邊可表示為：voidDeleteEdge(AdjLGraph*G,intv1,intv2)；其中參數(shù)G表示指定的鄰接表，其類型為AdjLGraph，參數(shù)v1,v2表示頂點編號，其類型為int。函數(shù)的功能：實現(xiàn)圖的鄰接表刪除邊。處理過程為：若v1,v2合法，則⑴查找v2在v1鄰接結(jié)點中，若存在，則刪除到⑵，否則，返回；⑵G->numOfEdges--。58第8章圖函數(shù)實現(xiàn)如下：voidDeleteEdge(AdjLGraph*G,intv1,intv2)/*鄰接表刪除邊*/{Edge*curr,*pre;if(v1<0||v1>=G->numOfVerts||v2<0||v2>=G->numOfVerts){printf("參數(shù)v1或v2越界出錯!");exit(0);}pre=NULL;curr=G->a[v1].adj;while(curr!=NULL&&curr->vertexNum!=v2){pre=curr;curr=curr->next;}59第8章圖if(curr!=NULL&&curr->vertexNum==v2&&pre==NULL){/*v1的第一鄰接點是v2*/G->a[v1].adj=curr->next;free(curr);G->numOfEdges--;}elseif(curr!=NULL&&curr->vertexNum==v2&&pre!=NULL){/*v1的鄰接點v2在其它位置*/pre->next=curr->next;free(curr);G->numOfEdges--;}elseprintf("邊<v1,v2>不存在!");}60第8章圖6.尋找第一個鄰接頂點尋找第一個鄰接頂點可表示為：intGetFirstVex(AdjLGraphG,intv)；其中參數(shù)G表示指定的鄰接表，其類型為AdjGraph，參數(shù)v表示頂點編號，其類型為int。函數(shù)的功能：在圖G中尋找序號為v的頂點的第一個鄰接頂點，如果這樣的鄰接頂點存在則返回該鄰接頂點的編號，否則返回-1。處理過程為：若v合法，在鄰接表的第v行p=G.a[v].adj，若p!=NULL，返回p->vertexNum，否則返回-1。61第8章圖intGetFirstVex(AdjLGraphG,intv)/*取鄰接表中第一個鄰接頂點編號*/{Edge*p;if(v<0||v>=G.numOfVerts){printf("參數(shù)v1或v2越界出錯!");exit(0);}p=G.a[v].adj;if(p!=NULL)returnp->vertexNum;elsereturn-1;}62第8章圖6.取鄰接表中v2之后鄰接頂點編號取鄰接表中v2之后鄰接頂點編號可表示為：intGetNextVex(AdjLGraphG,intv1,intv2)；其中參數(shù)G表示指定的鄰接表，其類型為AdjGraph，參數(shù)v1,V2表示頂點編號，其類型為int。函數(shù)的功能：在圖G中尋找序號為v1的頂點的V2之后的鄰接頂點，如果這樣的鄰接頂點存在則返回該鄰接頂點的編號，否則返回-1。處理過程為：若v1，v2合法，在鄰接表的第v行p=G.a[v].adj，若p->next!=NULL，p->vertexNum==v2，返回p->next->vertexNum,否則返回-1。63第8章圖intGetNextVex(AdjLGraphG,intv1,constintv2)/*取鄰接表中v2之后鄰接頂點編號*/{Edge*p;if(v1<0||v1>G.numOfVerts||v2<0||v2>G.numOfVerts){printf("參數(shù)v1或v2越界出錯!");exit(0);}p=G.a[v1].adj;64第8章圖while(p!=NULL){if(p->vertexNum!=v2){p=p->next;continue;}elsebreak;}p=p->next;if(p!=NULL)returnp->vertexNum;elsereturn-1;}65第8章圖/*建立鄰接鏈表頭文件CreatGraph.h*/typedefstruct{introw;intcol;}RowCol;7.建立鄰接表建立鄰接表可表示為：voidCreatGraph(AdjLGraph*G,DataTypev[],intn,RowCold[],inte)；其中參數(shù)G表示指定的鄰接表，其類型為AdjGraph，參數(shù)V表示頂點數(shù)組，其類型為DataType，參數(shù)n表示頂點數(shù)，其類型為int，參數(shù)d表示邊數(shù)組，其類型為RowColWeight，函數(shù)外定義,參數(shù)e表示邊數(shù)，其類型為int。66第8章圖函數(shù)的功能：在圖G中插入n個頂點信息V和e條邊信息。處理過程為：⑴鄰接表初始化⑵插入頂點集⑶插入邊集函數(shù)實現(xiàn)如下：voidCreatGraph(AdjLGraph*G,DataTypev[],intn,RowCold[],inte){/*建立鄰接鏈表*/inti,k;AdjInitiate(G);/*初始化*/for(i=0;i<n;i++)InsertVertex(G,i,v[i]);/*插入頂點集*/for(k=0;k<e;k++)InsertEdge(G,d[k].row,d[k].col);/*插入邊集*/}67第8章圖有興趣的讀者，可以用下面函數(shù)測試，看一看執(zhí)行的結(jié)果。/*測試函數(shù)*/#include<stdio.h>#include<stdlib.h>typedefcharDataType;#defineMaxVertices100#include"AdjLGraph.h"#include"CreatGraph.h"voidmain(void){AdjLGraphg;chara[]={'A','B','C','D','E'};RowColrc[]={{0,1},{1,3},{3,2},{2,1},{0,4}};inti,n=5,e=5;Edge*p;CreatGraph(&g,a,n,rc,e);printf("%d%d\n",g.numOfVerts,g.numOfEdges);68第8章圖for(i=0;i<g.numOfVerts;i++)/*輸出每一個頂點的鄰接頂點編號*/{printf("%c",g.a[i].data);p=g.a[i].adj;while(p!=NULL){printf("%d",p->vertexNum);p=p->next;}printf("\n");}DeleteEdge(&g,1,3);/*刪除一條邊*/printf("%d%d\n",g.numOfVerts,g.numOfEdges);69第8章圖for(i=0;i<g.numOfVerts;i++){printf("%c",g.a[i].data);p=g.a[i].adj;while(p!=NULL){printf("%d",p->vertexNum);p=p->next;}printf("\n");}AdjDestroy(&g);}70第8章圖8.2.3圖的ADT定義以上我們討論了圖的結(jié)構(gòu)特征、存儲方式及其相關操作的實現(xiàn)，在本節(jié)中我們將給出線性表的ADT定義即抽象數(shù)據(jù)類型定義，為以后面向?qū)ο蟪绦蛟O計中的類定義奠定基礎。根據(jù)面向?qū)ο蟪绦蛟O計的原則，實現(xiàn)部分與接口部分兩者應該分離。接口部分可以用ADT定義即抽象數(shù)據(jù)類型定義來進行描述。一種數(shù)據(jù)類型的ADT定義由數(shù)據(jù)元素、結(jié)構(gòu)及操作三部分組成。元素：ai同屬于一個數(shù)據(jù)元素類型，i=1，2，…，n（n≥0）；結(jié)構(gòu)：對所有的數(shù)據(jù)元素ai，aj(i,j=1，2，…，n-1、i≠j)存在關系<ai，aj>或（ai，aj）；71第8章圖對圖可執(zhí)行基本操作為：⑴Initiate(G)：初始化，建立一個空的圖G。⑵Destroy(G)：銷毀，釋放圖G空間。⑶InsertVertex(G,i,vertex)：插入頂點，圖G插入一個頂點vertex，編號為i。⑷InsertEdge(G,v1,v2)：插入邊，構(gòu)成邊的兩個頂點v1和v2是圖中的頂點，則在圖G中插入一條邊。⑸DeleteEdge(G,v1,v2)：刪除邊，若構(gòu)成邊的兩個頂點v1和v2是圖中的頂點，則在圖G中刪去邊。⑹GetFirstVex(G,v)：取第一個鄰接頂點，給出頂點位置為v的第一個鄰接頂點的位置，如果找不到，則函數(shù)返回-1。⑺GetNextVex(G,v1,v2):取下一個鄰接頂點,給出頂點位置為v1的某鄰接頂點v2的下—個鄰接頂點的位置，如果找不到，則返回-1。通過前面的學習，我們知道，同樣的操作會因為存儲結(jié)構(gòu)的不同而不同。72第8章圖8.3遍歷圖給定一個無向連通圖G，G=(V，E)，當從V(G)中的任一頂點v出發(fā)，去訪問圖中其余頂點，使每個頂點僅被訪問一次。這個過程叫做圖的遍歷。73圖8.12存在回路的圖第8章圖然而，圖的遍歷要比樹的遍歷復雜的多。因為圖中的任一頂點都可能和其余的頂點相鄰接。所以在訪問某個頂點后，可能沿著某條路徑搜索之后，又回到該頂點。例如圖8.12，由于圖中存在回路，因此在訪問了1,2,4,3之后沿著邊(3,1)又可訪問到1。為了避免同一頂點被訪問多次，在遍歷圖的過程中，必須記下每個已訪問過的頂點。為此，我們設一個輔助數(shù)組，可以利用表頭向量a，讓其tag域作為標志域

1已訪問過即AdjLHeighta[v].tag=0未訪問過通常有兩種遍歷圖的方法，一種是深度優(yōu)先搜索法，另一種為廣度優(yōu)先搜索法。74第8章圖8.3.1深度優(yōu)先搜索法設有無向連通圖G(V，E)，從V(G)中任一頂點V出發(fā)深度優(yōu)先搜索法進行遍歷的步驟是：先訪問指定頂點v，然后訪問與該頂點v相鄰的頂點vt，再從vt出發(fā)，訪問與Vt相鄰且未被訪問過的任意頂點，然后從此頂點出發(fā)，重復上述過程，直到一個所有鄰接點都被訪問過為止，然后回溯到此頂點的直接前趨，從這兒出發(fā)再繼續(xù)訪問。顯然搜索是一個遞歸過程。對于圖8.9(a)，鄰接表為圖8.9(b)，先選取A頂點作為搜索的起始點。頂點A的相鄰頂點分別是C、B，所以沿著它的一個相鄰頂點往下走。當走到頂C時，它有一個相鄰頂點A，而A已被訪問過所以應原路返回A,訪問A的下一個相鄰頂點B，往下走到D，而D有一個相鄰頂點B已被訪問過所以應原路返回B,其相鄰頂點已被訪問,原路返回上層A,上層為空則結(jié)束。75第8章圖深度優(yōu)先遍歷遞歸函數(shù)可表示為：DepthFirstSearch(AdjLGraphgintv)；其中參數(shù)g表示指定的鄰接表，其類型為AdjGraph，v為起始頂點編號。函數(shù)的功能：從v開始對鄰接表g所表示的圖遞歸地進行深度優(yōu)先遍歷。處理過程為：⑴訪問頂點v，并作訪問標記；⑵按鄰接取v的下一個未訪問的鄰接點w，并從w出發(fā)進行深度優(yōu)先遍歷；⑶重復⑵直至v的所有鄰接點均被訪問。76第8章圖程序如下：DepthFirstSearch(AdjLGraphgintv)/*從某頂點v出發(fā)深度優(yōu)先搜索子函數(shù)*/｛intw;printf(“%d”,v);/*輸出頂點*/g.a[v].tag=1;/*頂點標志域置1*/while(ptr[v]!=NULL){w=ptr[v]->vextexNum;/*取出頂點V的某相鄰頂點的序號*/if(g.a[w].tag==0)DepthFirstSearch(g,w);/*如果該頂點未被訪問過則遞歸調(diào)用，從該頂點w出發(fā)，*//*沿著它的各相鄰頂點向下搜索*/77第8章圖ptr[v]=ptr[v]->next;/*若從頂點v出發(fā)沿著某個相鄰頂點的向下搜索已走到頭，*//*則換一個相鄰頂點，沿著它往下搜索*/}/*從頂點v出發(fā)對各相鄰頂點逐個搜索，*//*直至從頂點v出發(fā)的所有并行路線已被搜索*/return;}78第8章圖有興趣的讀者，可以用下面函數(shù)測試，看一看執(zhí)行的結(jié)果。include<stdio.h>#include<stdlib.h>typedefcharDataType;#defineMaxVertices100#include"AdjLGraph.h"#include"CreatGraph.h"Edge*ptr[MaxVertices]voidmain(void){AdjLGraphg;chara[]={'A','B','C','D','E'};RowColrc[]={{0,1},{1,3},{3,2},{2,1},{0,4}};inti,w,v,n=5,e=5;Edge*p;79第8章圖CreatGraph(&g,a,n,rc,e);for(v=0;v<=n;v++)*/初始化指針數(shù)組及標志域/*{ptr[v]=g.a[v].adj;g.a[v].tag=0;}for(v=0;v<n;v++)if(g.a[v].tag==0)DepthFirstSearch(g,v);}請讀者注意：①在主函數(shù)中一定要初始化指針數(shù)組及標志域，否則程序無法執(zhí)行。②主函數(shù)中要從每一個頂點出發(fā)作深度優(yōu)先遍歷，因為圖有可能不連通。80第8章圖8.3.2廣度優(yōu)先搜索設無向圖G(V，E)是連通的，從V(G)中的任一頂點v出發(fā)按廣度優(yōu)先搜索法遍歷圖的步驟是：首先訪問指定的起始頂點v，從v出發(fā)，依次訪問與v相鄰的未被訪問過的頂點w1，w2，w3，...，wt然后依次從w1，w2，w3，...，wt出發(fā)，重復上述訪問過程，直到所有頂點都被訪問過為止。以圖8.13為例，如選頂點1為起始點先進行訪問。頂點有三個相鄰頂點，依次是4、3、2，則廣度優(yōu)先搜索時對這幾個頂點依次訪問，然后再將這些相鄰頂點的第一相鄰頂點4作為起始頂點重復上述步驟，再優(yōu)先訪問6。再將第二個相鄰頂點3作為起始頂點，重復上述步驟，頂點3有三個相鄰頂點依次為6、5、2，其中2、6被訪問過(不再訪問),所以訪問5。依次再判2、6、5,再重復上述步驟，因相鄰頂點都被訪問過即結(jié)束。81第8章圖82廣度優(yōu)先遍歷遞歸函數(shù)可表示為：voidBroadFirstSearch(AdjLGraphg,intv)；其中參數(shù)g表示指定的鄰接表，其類型為AdjGraph，v為起始頂點編號。函數(shù)的功能：從v開始對鄰接表g所表示的圖遞歸地進行廣度優(yōu)先遍歷。圖8.13廣度優(yōu)先搜索示意圖第8章圖處理過程為：⑴初始化隊列；⑵訪問頂點v，并作訪問標記，v進入隊列；⑶從隊列中取出一個頂點，依次訪問、標記它的每一個未訪問的鄰接點，并進入隊列；重復⑵⑶直至隊列為空。程序如下：voidBroadFirstSearch(AdjLGraphg,intv)/*從v出發(fā)廣度優(yōu)先搜索函數(shù)*/{Edge*ptr;SeqCQueueq;intv1,w;QueueInitiate(&q);printf(“%c”v);/*輸出該頂點*/g.a[v]?tag=1;/*標志域置1*/QueueAppend(&q,v);/*將該頂點入隊尾*/83第8章圖while(QueueDelete(&q,&v1)!=0)/*while循環(huán)使屬于同一層頂點的相鄰頂點的依次出隊。由于這些相鄰頂點*//*作為上一層頂點均被訪問過，出隊的目的是訪問它的下層相鄰頂點*/{ptr=g.a[v1].adj;/*取出該頂點的第一個相鄰頂點地址*/while(ptr!=NULL)/*while循環(huán)依次訪問各相鄰頂點*/{w=ptr->vertexNum;/*取出該頂點的序號*/ptr=ptr->next;/*從鄰接表的相應鏈表中，取出下一個相鄰頂點的地址以備訪問*/if(g.a[w].tag==0)/*若該相鄰頂點未被訪問過*/{printf(“%d”w)/*則訪問該相鄰頂點*/g.a[w].tag=1;/*修改頂點標志域為1*/QueueAppend(&q,w);/*將訪問過的頂點入隊，以備在進入下一層搜索時使用*/}}}}84第8章圖有興趣的讀者，可以用下面函數(shù)測試，看一看執(zhí)行的結(jié)果。#include<stdlib.h>#include<malloc.h>typedefcharDataType;#defineMaxVertices100#include"AdjLGraph.h"#include"CreatGraph.h"#include"SeqCQueue.h"voidmain(void){AdjLGraphg;chara[]={'A','B','C','D','E'};RowColrc[]={{0,1},{1,3},{3,2},{2,1},{0,4}};inti,w,v,n=5,e=5;Edge*p;85第8章圖CreatGraph(&g,a,n,rc,e);for(v=0;v<n;v++)*/初始化標志域/*g.a[v].tag=0;for(v=1;v<=n;v++)if(g.a[v].tag==0)BroadFirstSearch(g,v);}請讀者注意：①在主函數(shù)中一定要初始化指針數(shù)組及標志域，否則程序無法執(zhí)行。②主函數(shù)中要從每一個頂點出發(fā)作深度優(yōu)先遍歷，因為圖有可能不連通。86第8章圖8.4最小生成樹8.4.1最小生成樹的基本概念一個有n個頂點的連通圖的生成樹是原圖的極小連通子圖，它包含原圖中的所有n個頂點，并且有保持圖連通的最少的邊。由生成樹的定義可知：⑴若在生成樹中刪除一條邊，就會使該生成樹因變成非連通圖而不再滿足生成樹的定義；⑵若在生成樹中增加一條邊，就會使該生成樹中因存在回路而不再滿足生成樹的定義；⑶一個連通圖的生成樹可能有許多。使用不同的遍歷圖的方法可以得到不同的生成樹。如對無向圖使用深度優(yōu)先搜索遍歷方法與使用廣度優(yōu)先搜索遍歷方法將會得到兩個結(jié)構(gòu)不同的生成樹；從不同的頂點出發(fā)，也可以得到不同的生成樹。圖8.14給出了一個無向圖和它的兩棵不同的生成樹。87第8章圖88圖8.14無向圖和它的不同的生成樹(a)無向圖；(b)生成樹1；(c)生成樹2第8章圖從生成樹的定義顯然可以證明，對于有n個頂點的無向連通圖，無論它的生成樹的形狀如何，一定有且僅有n-1條邊。如果無向連通圖是一個網(wǎng)(或稱帶權(quán)圖)，那么它的所有生成樹中必有一棵邊的權(quán)值總和最小的生成樹，我們稱這棵生成樹為最小代價生成樹，簡稱最小生成樹。對于一個帶權(quán)的連通圖(即網(wǎng)絡)，如何找出一棵生成樹，使得各邊上的權(quán)值總和達到最小，這是一個有實際意義的問題。例如，在n個城市之間建立通信網(wǎng)絡，至少要架設n-1條線路。這時自然會考慮：如何做才能使得總造價最少?89第8章圖在每兩個城市之間都可以架設一條通信線路，并要花費一定的代價。若用圖的頂點表示n個城市，用邊表示兩城市之間架設的線路，用邊上的權(quán)值表示架設該線路的造價，就可以建立一個通信網(wǎng)絡。對于這樣一個有n個頂點的網(wǎng)絡，可以有不同的生成樹，每一棵生成樹都可以構(gòu)成通信網(wǎng)絡。希望能夠根據(jù)各條邊上的權(quán)值，選擇一棵總造價最小的生成樹，這就是構(gòu)造網(wǎng)絡的最小(代價)生成樹(MinimumCostSpanningTree)的問題。從最小生成樹的定義可知，構(gòu)造有n個頂點的無向連通網(wǎng)的最小生成樹必須滿足以下三條：(1)構(gòu)造的最小生成樹必須包括n個頂點；(2)構(gòu)造的最小生成樹中有且只有n-1條邊；(3)構(gòu)造的最小生成樹中不存在回路。構(gòu)造的最小生成樹的方法有許多種，典型的構(gòu)造方法有兩種：一種稱作普里姆(Prim)算法，另一種稱作克魯斯卡爾(Kruskal)算法。90第8章圖8.4.2普里姆算法假設G=(V，E)是一個網(wǎng)絡，其中V為網(wǎng)中頂點的集合，E為網(wǎng)中帶權(quán)邊的集合。設置兩個新的集合U和T，其中U用于存放網(wǎng)G的最小生成樹的頂點的集合，T用于存放網(wǎng)G的最小生成樹的帶權(quán)邊的集合。令集合U的初值為U={u0}(即假設構(gòu)造最小生成樹時均從頂點u0開始)，集合T的初值為T={}。普里姆算法的思想是：從所有頂點u∈U和頂點v∈V-U的帶權(quán)邊中選出具有最小權(quán)值的邊(u,v)∈U，將頂點v加入集合U中，將邊(u,v)加入集合T中。如此不斷重復，直到U=V時即構(gòu)造完畢。此時集合U中存放著最小生成樹的頂點的集合，集合T中存放著最小生成樹的帶權(quán)邊的集合。91第8章圖圖8.15給出了用普里姆算法構(gòu)造最小生成樹的過程。圖8.15(a)是一個有7個頂點、10條無向邊的帶權(quán)圖。初始時算法的集合U={A}，集合V-U={B，C，D，E，F(xiàn)，G}，T={}，如圖8.15(b)所示。在所有u為集合U中頂點，v為集合V-U中頂點的邊(u,v)中，尋找具有最小權(quán)值的邊(u,v)，尋找到的是邊(A,B)，權(quán)為50，把頂點B從集合V—U加入到集合U中，把邊(A,B)加入到了中，如圖8.15(c)所示。在所有u為集合U中頂點，v為集合V-U中頂點的邊(u,v),中尋找具有最小權(quán)值的邊(u,v)，尋找到的是邊(B,E)，權(quán)為40，把頂點E從集合V-U加入到集合U中，把邊(B，E)加入到T中，如圖8.15(d)所示；隨后依次從集合V-U加入到集合U中的頂點為D，F(xiàn)，G，C，依次加入到T中的邊為(E，D)，權(quán)為50，(D，F(xiàn))權(quán)為30，(D，G)權(quán)為42，(G，C)權(quán)為45，分別如圖8.15(e)，(f)，(g)，(h)所示。最后得到的圖8.15(h)就是原帶權(quán)連通圖的最小生成樹。92第8章圖93圖8.15普里姆算法構(gòu)造最小生成樹的過程第8章圖

我們再來討論普里姆算法的實現(xiàn)問題。普里姆算法要處理的帶權(quán)圖G可以是前面討論過的任意存儲結(jié)構(gòu)的圖。我們下面討論的普里姆算法使用鄰接矩陣作為圖的存儲結(jié)構(gòu)，算法中定義的圖G的頂點集合就是普里姆算法中的集合V，圖G的邊集合就是普里姆算法中的集合E。普里姆算法所構(gòu)造的最小生成樹是集合U和集合T，集合U是頂點的集合，集合T是帶權(quán)邊的集合。94第8章圖

為實現(xiàn)普里姆算法，我們還需定義一個臨時數(shù)組lowCost[n]，用來保存集合U中頂點u與集合V-U中頂點v的所有邊中當前具有最小權(quán)值的邊(u，v)?；仡檸?quán)圖中權(quán)的定義，當弧頭頂點等于弧尾頂點時權(quán)值等于0(即鄰接矩陣的對角線元素值為0)，我們在此可以利用權(quán)定義中的這一點，令lowCost的初始值為鄰接矩陣中第0行的值，lowCost表示了從集合U中第一個頂點到達集合V-U中各個頂點的代價。然后我們從lowCost中尋找具有最小權(quán)值的邊，這樣的邊也就意味著其弧頭頂點為集合U中頂點，其弧尾頂點為集合V-U中頂點。每選到一條這樣的邊(u,v)，就將lowCost[v]置為0，表示頂點v已從集合V-U加入到集合U中。如果頂點v從集合V-U進入集合U后，當前l(fā)owCost中從集合U中頂點到達集合V-U中頂點存在更小代價的邊時，則用這樣的邊的權(quán)值修改原來的權(quán)值。最后輸出即為所構(gòu)造的最小生成樹。95第8章圖用普里姆方法建立網(wǎng)G的最小生成樹minSTree的函數(shù)如下：voidPrim(AdjMWGraphG)/*用普里姆方法建立網(wǎng)G的最小生成樹closeVertex*/{intn=G.Vertices.size,minCost;int*lowCost=(int*)malloc(sizeof(int)*n);inti,j,k;/*從序號為0的頂點出發(fā)構(gòu)造最小生成樹*/printf("頂點值=%c\n",G.Vertices.list[0]);for(i=1;i<n;i++) lowCost[i]=G.edge[0][i];lowCost[0]=0;for(i=1;i<n;i++){96第8章圖/*尋找當前最小權(quán)值的邊的頂點*/minCost=MaxWeight;/*MaxWeight為定義的最大權(quán)值*/j=1;k=1;while(j<n){if(lowCost[j]<minCost&&lowCost[j]!=0){minCost=lowCost[j];k=j;}j++;}printf("頂點值=%c邊的權(quán)值=%d\n",G.Vertices.list[k],minCost);lowCost[k]=-1;97