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

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

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

E={{}(7)路徑(Path)。在圖G=<V,E)中，若從頂點(diǎn)vi出發(fā)，沿一些邊經(jīng)過(guò)一些頂點(diǎn)vp1,vp2,…vpm到達(dá)頂點(diǎn)vj。則稱頂點(diǎn)序列(vi,vp1,vp2,…vpm,vj)為從頂點(diǎn)vi到頂點(diǎn)vj的路徑。它經(jīng)過(guò)的邊(vi,vp1)，(vp1,vp2),…(vpm,vj)應(yīng)是屬于E的邊。16第8章圖(7)路徑(Path)。在圖G=<V,E)中，若從頂點(diǎn)vi出發(fā)，沿一些邊經(jīng)過(guò)一些頂點(diǎn)vp1,vp2,…vpm到達(dá)頂點(diǎn)vj。則稱頂點(diǎn)序列(vi,vp1,vp2,…vpm,vj)為從頂點(diǎn)vi到頂點(diǎn)vj的路徑。它經(jīng)過(guò)的邊(vi,vp1)，(vp1,vp2),…(vpm,vj)應(yīng)是屬于E的邊。(8)路徑長(zhǎng)度(PathLength)。對(duì)于不帶權(quán)的圖，路徑長(zhǎng)度是指此路徑上邊的條數(shù)。對(duì)于帶權(quán)圖，路徑長(zhǎng)度是指路徑上各邊的權(quán)之和。(9)簡(jiǎn)單路徑與回路(Cycle)。若路徑上各頂點(diǎn)v1,v2…vmv1,均不互相重復(fù)，則稱這樣的路徑為簡(jiǎn)單路徑。若路徑上第一個(gè)頂點(diǎn)v1與最后一個(gè)頂點(diǎn)vm重合，則稱這樣的路徑為回路或環(huán)。如圖8.5所示。圖8.5(a)所示是簡(jiǎn)單路徑，圖8.5(b)所示是非簡(jiǎn)單路徑。通常在解決實(shí)際應(yīng)用問(wèn)題時(shí)，只考慮簡(jiǎn)單路徑。圖8．5(c)所示是回路。17第8章圖18圖8.5簡(jiǎn)單路徑與回路(a)簡(jiǎn)單路徑(b)非簡(jiǎn)單路徑(c)回路第8章圖(10)連通圖與連通分量(ConnectedGraph&ConnectedComponent)。在無(wú)向圖中若從頂點(diǎn)v1到頂點(diǎn)v2有路徑，則稱頂點(diǎn)v1與v2是連通的。如果圖中任意一對(duì)頂點(diǎn)都是連通的，則稱此圖是連通圖。非連通圖的極大連通子圖叫做連通分量。(11)強(qiáng)連通圖與強(qiáng)連通分量(StronglyConnectedGraph)。在有向圖中，若對(duì)于每一對(duì)頂點(diǎn)vi和vj，都存在一條從vi到vj和從vj到vi的路徑，則稱此圖是強(qiáng)連通圖。非強(qiáng)連通圖的極大強(qiáng)連通子圖叫做強(qiáng)連通分量。(12)生成樹(SpanningTree)。一個(gè)連通圖的生成樹是它的極小連通子圖，在n個(gè)頂點(diǎn)的情形下，有n-l條邊。但有向圖則可能得到它的由若干有向樹組成的生成森林。19第8章圖8.2圖的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)圖的存儲(chǔ)結(jié)構(gòu)比較多。對(duì)于圖的存儲(chǔ)結(jié)構(gòu)的選擇取決于具體的應(yīng)用和需要進(jìn)行的運(yùn)算。下面給出兩種常用的圖的結(jié)構(gòu)，鄰接矩陣和鄰接表。8.2.1鄰接矩陣在圖的鄰接矩陣(AdjacencyMatrix)表示中，除了一個(gè)記錄各個(gè)頂點(diǎn)信息的頂點(diǎn)表外，還有一個(gè)稱之為鄰接矩陣的表示各個(gè)頂點(diǎn)之間關(guān)系的矩陣。若設(shè)圖A=(V，E)是一個(gè)有n個(gè)頂點(diǎn)的圖，則圖的鄰接矩陣是一個(gè)二維數(shù)組A.edge[n][n]，它的定義為：1，if((i，j)or<i，j>∈E)A.edge[i][j]=0，otherwise20第8章圖圖8．6給出了無(wú)向圖和它的鄰接矩陣，圖8．7給出了有向圖和它的鄰接矩陣。從圖8．6中可知，無(wú)向圖的鄰接矩陣是對(duì)稱的，將第i行的元素值或第i列的元素值累加起來(lái)就得到頂點(diǎn)i的度。但有向圖的鄰接矩陣可能是不對(duì)稱的。如果第i行的A．Edge[i][j]=1，則表示有一條從頂點(diǎn)i到頂點(diǎn)j的有向邊，將第i行的所有元素值累加起來(lái)就得到頂點(diǎn)i的出度；如果第j列的A．Edge[k][j]=l，則表示有一條從頂點(diǎn)k到頂點(diǎn)j的有向邊，將第j列的所有元素值累加起來(lái)就得到頂點(diǎn)j的入度。21第8章圖22圖8．6無(wú)向圖和它的鄰接矩陣圖8．7有向圖和它的鄰接矩陣第8章圖對(duì)于網(wǎng)絡(luò)(或帶權(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給出一個(gè)網(wǎng)絡(luò)的鄰接矩陣。23圖8．8一個(gè)網(wǎng)絡(luò)和它的鄰接矩陣第8章圖對(duì)于用鄰接矩陣表示的圖來(lái)說(shuō)，要想確定“圖中有多少條邊?”和“圖是否連通?”等問(wèn)題，需要檢查除對(duì)角線外的所有n2-n個(gè)矩陣元素，時(shí)間開銷很高。當(dāng)圖中的邊數(shù)e遠(yuǎn)遠(yuǎn)小于圖的鄰結(jié)矩陣元素個(gè)數(shù)n2時(shí)，圖的鄰接矩陣變成稀疏矩陣，存儲(chǔ)利用率很低。為此，可以改用后面介紹的鄰接表。下面給出用鄰接矩陣作為存儲(chǔ)表示的圖的類型定義及算法實(shí)現(xiàn)。其中有一個(gè)類型為順序表的頂點(diǎn)表向量Vertices，用以存儲(chǔ)頂點(diǎn)的信息，還有—個(gè)作為鄰接矩陣使用的二維數(shù)組edge，用以存儲(chǔ)圖中的邊，其矩陣元素個(gè)數(shù)取決于頂點(diǎn)個(gè)數(shù)，與邊數(shù)無(wú)關(guān)。當(dāng)前頂點(diǎn)個(gè)數(shù)在順序表中聲明，當(dāng)前邊數(shù)由CurrentEdges指明。24第8章圖以下的類型定義和函數(shù)都放在鄰接矩陣頭文件AdjMGraph.h中。#include"SeqList.h"/*包含順序表頭文件*/typedefstruct{SeqListVertices;/*存放頂點(diǎn)的順序表*/intedge[MaxVertices][MaxVertices];/*存放邊的鄰接矩陣*/intCurrentEdges;/*邊的條數(shù)*/}AdjMWGraph;/*圖的結(jié)構(gòu)體定義*/1.鄰接矩陣的初始化鄰接矩陣的初始化可表示為：voidInitiate(AdjMWGraph*G,intn)；其中參數(shù)G表示指定的鄰接矩陣，其類型為AdjMWGraph，參數(shù)n表示頂點(diǎn)個(gè)數(shù)。函數(shù)的功能：實(shí)現(xiàn)鄰接矩陣的初始化。25第8章圖處理過(guò)程為：⑴使圖G鄰接矩陣的對(duì)角線元素為0，其它元素為∞；⑵使圖G鄰接矩陣的邊數(shù)為0；⑶圖G頂點(diǎn)表向量Vertices的初始化。函數(shù)實(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.圖的鄰接矩陣加入新頂點(diǎn)圖的鄰接矩陣加入新頂點(diǎn)可表示為：voidInsertVertex(AdjMWGraph*G,DataTypevertex)；其中參數(shù)G表示指定的鄰接矩陣，其類型為AdjMWGraph，參數(shù)vertex表示頂點(diǎn)，其類型為DataType。函數(shù)的功能：實(shí)現(xiàn)圖的鄰接矩陣加入新頂點(diǎn)。27第8章圖處理過(guò)程為：⑴圖G頂點(diǎn)表向量Vertices中增加一個(gè)新元素，元素個(gè)數(shù)加1，即在順序表表尾插入；⑵返回。函數(shù)實(shí)現(xiàn)如下：voidInsertVertex(AdjMWGraph*G,DataTypevertex)/*在圖G中插入頂點(diǎn)vertex*/{ListInsert(&G->Vertices,G->Vertices.size,vertex);}3.圖的鄰接矩陣加入新邊圖的鄰接矩陣加入新邊可表示為：voidInsertEdge(AdjMWGraph*G,intv1,intv2,intweight)；其中參數(shù)G表示指定的鄰接矩陣，其類型為AdjMWGraph，參數(shù)v1,v2表示頂點(diǎn)編號(hào)，其類型為int，weight為邊的權(quán)值。28第8章圖函數(shù)的功能：實(shí)現(xiàn)圖的鄰接矩陣加入新邊。處理過(guò)程為：若v1,v2合法，則⑴使圖G->edge[v1][v2]=weight；⑵G->CurrentEdges++。函數(shù)實(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越界出錯(cuò)!\n");exit(1);}G->edge[v1][v2]=weight;G->CurrentEdges++;}29第8章圖4.圖的鄰接矩陣刪除邊圖的鄰接矩陣刪除邊可表示為：voidDeleteEdge(AdjMWGraph*G,intv1,intv2)；其中參數(shù)G表示指定的鄰接矩陣，其類型為AdjMWGraph，參數(shù)v1,v2表示頂點(diǎn)編號(hào)，其類型為int。函數(shù)的功能：實(shí)現(xiàn)圖的鄰接矩陣刪除邊。處理過(guò)程為：若v1,v2合法，則⑴使圖G->edge[v1][v2]=MaxWeight；⑵G->CurrentEdges--。30第8章圖函數(shù)實(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越界出錯(cuò)!\n");exit(1);}G->edge[v1][v2]=MaxWeight;G->CurrentEdges--;}31第8章圖4.圖的鄰接矩陣刪除頂點(diǎn)圖的鄰接矩陣刪除頂點(diǎn)可表示為：voidDeleteVertex(AdjMWGraph*G,intv)；其中參數(shù)G表示指定的鄰接矩陣，其類型為AdjMWGraph，參數(shù)v表示頂點(diǎn)編號(hào)，其類型為int。函數(shù)的功能：實(shí)現(xiàn)圖的鄰接矩陣刪除頂點(diǎn)。處理過(guò)程為：⑴若G->edge[i][j]是與該頂點(diǎn)相關(guān)的所有邊，G->CurrentEdges--；⑵刪除該頂點(diǎn)所在的行；⑶刪除該頂點(diǎn)所在的列；⑷圖G頂點(diǎn)表向量Vertices中刪除該元素，元素個(gè)數(shù)減1。32第8章圖函數(shù)實(shí)現(xiàn)如下：voidDeleteVertex(AdjMWGraph*G,intv)/*刪除圖G頂點(diǎn)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--;/*被刪除邊計(jì)數(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é)點(diǎn)v*/}34第8章圖5.尋找第一個(gè)鄰接頂點(diǎn)尋找第一個(gè)鄰接頂點(diǎn)可表示為：intGetFirstVex(AdjMWGraphG,intv)；其中參數(shù)G表示指定的鄰接矩陣，其類型為AdjMWGraph，參數(shù)v表示頂點(diǎn)編號(hào)，其類型為int。函數(shù)的功能：在圖G中尋找序號(hào)為v的頂點(diǎn)的第一個(gè)鄰接頂點(diǎn)，如果這樣的鄰接頂點(diǎn)存在則返回該鄰接頂點(diǎn)的序號(hào)，否則返回-1。處理過(guò)程為：若v合法，在鄰接矩陣的第v行，尋找G.edge[v][col]>0&&G.edge[v][col]<MaxWeight)的元素。尋找到，返回col，否則返回-1。35第8章圖函數(shù)實(shí)現(xiàn)如下：intGetFirstVex(AdjMWGraphG,intv)/*在圖G中尋找序號(hào)為v的頂點(diǎn)的第一個(gè)鄰接頂點(diǎn)*//*如果這樣的鄰接頂點(diǎn)存在則返回該鄰接頂點(diǎn)的序號(hào)，否則返回-1*/{intcol;if(v<0||v>=G.Vertices.size){printf("參數(shù)v1越界出錯(cuò)!\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.尋找下一個(gè)鄰接頂點(diǎn)尋找下一個(gè)鄰接頂點(diǎn)可表示為：intGetNextVex(AdjMWGraphG,intv1,intv2)；其中參數(shù)G表示指定的鄰接矩陣，其類型為AdjMWGraph，參數(shù)v1，v2表示頂點(diǎn)編號(hào)，其類型為int。函數(shù)的功能：在圖G中尋找序號(hào)為v1頂點(diǎn)的鄰接頂點(diǎn)v2的下一個(gè)鄰接頂點(diǎn)，如果這樣的鄰接頂點(diǎn)存在則返回該鄰接頂點(diǎn)的序號(hào)，否則返回-1。處理過(guò)程為：若v1，v2合法，在鄰接矩陣的第v1行，從v2+1開始尋找G.edge[v1][col]>0&&G.edge[v1][col]<MaxWeight)的元素。尋找到，返回col，否則返回-1。37第8章圖函數(shù)實(shí)現(xiàn)如下：intGetNextVex(AdjMWGraphG,intv1,intv2)/*在圖G中尋找v1頂點(diǎn)的鄰接頂點(diǎn)v2的下一個(gè)鄰接頂點(diǎn)*//*如果這樣的鄰接頂點(diǎn)存在則返回該鄰接頂點(diǎn)的序號(hào)，否則返回-1*//*這里v1和v2都是相應(yīng)頂點(diǎn)的序號(hào)*/{intcol;if(v1<0||v1>=G.Vertices.size||v2<0||v2>=G.Vertices.size){printf("參數(shù)v1或v2越界出錯(cuò)!\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表示頂點(diǎn)數(shù)組，其類型為DataType，參數(shù)n表示頂點(diǎn)數(shù)，其類型為int，參數(shù)E表示邊數(shù)組，其類型為RowColWeight，函數(shù)外定義,參數(shù)e表示邊數(shù)，其類型為int。函數(shù)的功能：在圖G中插入n個(gè)頂點(diǎn)信息V和e條邊信息。處理過(guò)程為：⑴頂點(diǎn)順序表初始化⑵頂點(diǎn)插入⑶邊插入39第8章圖函數(shù)實(shí)現(xiàn)如下：/*建立鄰接矩陣的AdjMGraphCreate.h*/typedefstruct{introw;/*行下標(biāo)*/intcol;/*列下標(biāo)*/intweight;/*權(quán)值*/}RowColWeight;/*邊信息三元組結(jié)構(gòu)體定義*/voidCreatGraph(AdjMWGraph*G,DataTypeV[],intn,RowColWeightE[],inte)/*在圖G中插入n個(gè)頂點(diǎn)信息V和e條邊信息E*/{inti,k;Initiate(G,n);/*頂點(diǎn)順序表初始化*/for(i=0;i<n;i++)InsertVertex(G,V[i]);/*頂點(diǎn)插入*/for(k=0;k<e;k++)InsertEdge(G,E[k].row,E[k].col,E[k].weight);/*邊插入*/}40第8章圖有興趣的讀者，可以用下面函數(shù)測(cè)試，看一看執(zhí)行的結(jié)果。/*測(cè)試主函數(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);/*刪除頂點(diǎn)3*/42第8章圖printf("頂點(diǎn)集合為：");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）存儲(chǔ)結(jié)構(gòu)是一種順序分配和鏈?zhǔn)椒峙湎嘟Y(jié)合的存儲(chǔ)結(jié)構(gòu)。它包括兩個(gè)部分，一部分是向量；另一部分是鏈表。原則上，在鏈表部分共有n個(gè)鏈表，即每個(gè)頂點(diǎn)一個(gè)鏈表。每個(gè)鏈表由一個(gè)表頭結(jié)點(diǎn)和若干個(gè)表結(jié)點(diǎn)組成。表頭結(jié)點(diǎn)用來(lái)指示第i個(gè)頂點(diǎn)vi的數(shù)據(jù)信息（data）、是否被訪問(wèn)過(guò)（tag）和所對(duì)應(yīng)的鏈表指針（adj）；表結(jié)點(diǎn)由頂點(diǎn)編號(hào)域(vertexnum)和鏈域（next）所組成,對(duì)帶權(quán)圖還可增加權(quán)值域（weight）。頂點(diǎn)域指示了與vi相鄰接的頂點(diǎn)的序號(hào)，所以一個(gè)表結(jié)點(diǎn)實(shí)際代表了一條依附于vi的邊；鏈域指示了依附于vi的另一條邊的表結(jié)點(diǎn)。因此，第i個(gè)鏈表就表示了依附于vi的所有邊。對(duì)有向圖來(lái)講，第i個(gè)鏈表就表示了從vi發(fā)出的所有弧。如果要表示指向vi的弧，則要采用逆鄰接鏈表，第i個(gè)鏈表就表示了指向vi的所有弧。鄰接鏈表中的表頭部分是向量，用來(lái)存儲(chǔ)n個(gè)表頭結(jié)點(diǎn)。向量的下標(biāo)指示了頂點(diǎn)的序號(hào)。44第8章圖在C語(yǔ)言中，圖的鄰接表存儲(chǔ)表示如下。typedefstructNode{intvertexNum;/*頂點(diǎn)編號(hào)域*/intweight/*權(quán)值域*/structNode*next;/*鏈表指針*/}Edge;/*表結(jié)點(diǎn)*/typedefstruct{DataTypedata;/*結(jié)點(diǎn)信息*/inttag;/*標(biāo)識(shí)域*/Edge*adj;/*頭指針*/}AdjLHeight;/*表頭結(jié)點(diǎn)45第8章圖typedefstruct{AdjLHeighta[MaxVertices];/*表頭向量*/intnumOfVerts;/*頂點(diǎn)數(shù)*/intnumOfEdges;/*邊數(shù)*/}AdjLGraph;例如，圖8.9為無(wú)向圖及其鄰接鏈表，圖8.10為有向圖及其鄰接鏈表、逆接鏈表，圖8.11為有向帶權(quán)圖和其鄰接鏈表。46第8章圖47圖8.9無(wú)向圖和其鄰接鏈表（a）無(wú)向圖（b）鄰接鏈表第8章圖48圖8.10有向圖及其鄰接鏈表、逆接鏈表（a）無(wú)向圖（b）鄰接鏈表（c）逆接鏈表第8章圖49圖8.11有向帶權(quán)圖和其鄰接鏈表（a）有向帶權(quán)圖（b）鄰接鏈表第8章圖下面給出用鄰接鏈表作為存儲(chǔ)表示的圖的類型定義及常用算法實(shí)現(xiàn)。以上的類型定義和函數(shù)都放在鄰接表頭文件AdjLGraph.h中。1.鄰接表的初始化鄰接表的初始化可表示為：AdjInitiate(AdjLGraph*G)；其中參數(shù)G表示指定的鄰接表，其類型為AdjLGraph。函數(shù)的功能：實(shí)現(xiàn)鄰接表的初始化。處理過(guò)程為：⑴使圖G鄰接表頂點(diǎn)數(shù)為0；⑵使圖G鄰接表的邊數(shù)為0；⑶圖G頂點(diǎn)表向量a初始化。50第8章圖函數(shù)實(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ù)的功能：實(shí)現(xiàn)鄰接表的銷毀。處理過(guò)程為：從0號(hào)頂點(diǎn)開始，釋放圖G鄰接表中頂點(diǎn)。函數(shù)實(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.圖的鄰接表加入新頂點(diǎn)圖的鄰接表加入新頂點(diǎn)可表示為：voidInsertVertex(AdjLGraph*G,inti,DataTypevertex)；其中參數(shù)G表示指定的鄰接表，其類型為AdjLGraph，參數(shù)vertex表示頂點(diǎn)，其類型為DataType。I為頂點(diǎn)編號(hào)。函數(shù)的功能：實(shí)現(xiàn)圖的鄰接表加入新頂點(diǎn)。處理過(guò)程為：⑴若i合法，圖G頂點(diǎn)表向量a[i]中增加一個(gè)新元素，頂點(diǎn)個(gè)數(shù)加1；⑵返回。54第8章圖函數(shù)實(shí)現(xiàn)如下：voidInsertVertex(AdjLGraph*G,inti,DataTypevertex)/*鄰接表插入頂點(diǎn)*/{if(i>=0&&i<MaxVertices){G->a[i].data=vertex;G->numOfVerts++;}elseprintf("頂點(diǎn)越界");}55第8章圖4.圖的鄰接表加入新邊圖的鄰接表加入新邊可表示為：voidInsertEdge(AdjLGraph*G,intv1,intv2)；其中參數(shù)G表示指定的鄰接表，其類型為AdjLGraph，參數(shù)v1,v2表示頂點(diǎn)編號(hào)，其類型為int。函數(shù)的功能：實(shí)現(xiàn)圖的鄰接表加入新邊。處理過(guò)程為：若v1,v2合法，則⑴建立新結(jié)點(diǎn)p，p->next=G->a[v1].adj，G->a[v1].adj=p；⑵G->numOfEdges++。56第8章圖函數(shù)實(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越界出錯(cuò)!");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表示頂點(diǎn)編號(hào)，其類型為int。函數(shù)的功能：實(shí)現(xiàn)圖的鄰接表刪除邊。處理過(guò)程為：若v1,v2合法，則⑴查找v2在v1鄰接結(jié)點(diǎn)中，若存在，則刪除到⑵，否則，返回；⑵G->numOfEdges--。58第8章圖函數(shù)實(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越界出錯(cuò)!");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的第一鄰接點(diǎn)是v2*/G->a[v1].adj=curr->next;free(curr);G->numOfEdges--;}elseif(curr!=NULL&&curr->vertexNum==v2&&pre!=NULL){/*v1的鄰接點(diǎn)v2在其它位置*/pre->next=curr->next;free(curr);G->numOfEdges--;}elseprintf("邊<v1,v2>不存在!");}60第8章圖6.尋找第一個(gè)鄰接頂點(diǎn)尋找第一個(gè)鄰接頂點(diǎn)可表示為：intGetFirstVex(AdjLGraphG,intv)；其中參數(shù)G表示指定的鄰接表，其類型為AdjGraph，參數(shù)v表示頂點(diǎn)編號(hào)，其類型為int。函數(shù)的功能：在圖G中尋找序號(hào)為v的頂點(diǎn)的第一個(gè)鄰接頂點(diǎn)，如果這樣的鄰接頂點(diǎn)存在則返回該鄰接頂點(diǎn)的編號(hào)，否則返回-1。處理過(guò)程為：若v合法，在鄰接表的第v行p=G.a[v].adj，若p!=NULL，返回p->vertexNum，否則返回-1。61第8章圖intGetFirstVex(AdjLGraphG,intv)/*取鄰接表中第一個(gè)鄰接頂點(diǎn)編號(hào)*/{Edge*p;if(v<0||v>=G.numOfVerts){printf("參數(shù)v1或v2越界出錯(cuò)!");exit(0);}p=G.a[v].adj;if(p!=NULL)returnp->vertexNum;elsereturn-1;}62第8章圖6.取鄰接表中v2之后鄰接頂點(diǎn)編號(hào)取鄰接表中v2之后鄰接頂點(diǎn)編號(hào)可表示為：intGetNextVex(AdjLGraphG,intv1,intv2)；其中參數(shù)G表示指定的鄰接表，其類型為AdjGraph，參數(shù)v1,V2表示頂點(diǎn)編號(hào)，其類型為int。函數(shù)的功能：在圖G中尋找序號(hào)為v1的頂點(diǎn)的V2之后的鄰接頂點(diǎn)，如果這樣的鄰接頂點(diǎn)存在則返回該鄰接頂點(diǎn)的編號(hào)，否則返回-1。處理過(guò)程為：若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之后鄰接頂點(diǎn)編號(hào)*/{Edge*p;if(v1<0||v1>G.numOfVerts||v2<0||v2>G.numOfVerts){printf("參數(shù)v1或v2越界出錯(cuò)!");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表示頂點(diǎn)數(shù)組，其類型為DataType，參數(shù)n表示頂點(diǎn)數(shù)，其類型為int，參數(shù)d表示邊數(shù)組，其類型為RowColWeight，函數(shù)外定義,參數(shù)e表示邊數(shù)，其類型為int。66第8章圖函數(shù)的功能：在圖G中插入n個(gè)頂點(diǎn)信息V和e條邊信息。處理過(guò)程為：⑴鄰接表初始化⑵插入頂點(diǎn)集⑶插入邊集函數(shù)實(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]);/*插入頂點(diǎn)集*/for(k=0;k<e;k++)InsertEdge(G,d[k].row,d[k].col);/*插入邊集*/}67第8章圖有興趣的讀者，可以用下面函數(shù)測(cè)試，看一看執(zhí)行的結(jié)果。/*測(cè)試函數(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++)/*輸出每一個(gè)頂點(diǎn)的鄰接頂點(diǎn)編號(hào)*/{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)特征、存儲(chǔ)方式及其相關(guān)操作的實(shí)現(xiàn)，在本節(jié)中我們將給出線性表的ADT定義即抽象數(shù)據(jù)類型定義，為以后面向?qū)ο蟪绦蛟O(shè)計(jì)中的類定義奠定基礎(chǔ)。根據(jù)面向?qū)ο蟪绦蛟O(shè)計(jì)的原則，實(shí)現(xiàn)部分與接口部分兩者應(yīng)該分離。接口部分可以用ADT定義即抽象數(shù)據(jù)類型定義來(lái)進(jìn)行描述。一種數(shù)據(jù)類型的ADT定義由數(shù)據(jù)元素、結(jié)構(gòu)及操作三部分組成。元素：ai同屬于一個(gè)數(shù)據(jù)元素類型，i=1，2，…，n（n≥0）；結(jié)構(gòu)：對(duì)所有的數(shù)據(jù)元素ai，aj(i,j=1，2，…，n-1、i≠j)存在關(guān)系<ai，aj>或（ai，aj）；71第8章圖對(duì)圖可執(zhí)行基本操作為：⑴Initiate(G)：初始化，建立一個(gè)空的圖G。⑵Destroy(G)：銷毀，釋放圖G空間。⑶InsertVertex(G,i,vertex)：插入頂點(diǎn)，圖G插入一個(gè)頂點(diǎn)vertex，編號(hào)為i。⑷InsertEdge(G,v1,v2)：插入邊，構(gòu)成邊的兩個(gè)頂點(diǎn)v1和v2是圖中的頂點(diǎn)，則在圖G中插入一條邊。⑸DeleteEdge(G,v1,v2)：刪除邊，若構(gòu)成邊的兩個(gè)頂點(diǎn)v1和v2是圖中的頂點(diǎn)，則在圖G中刪去邊。⑹GetFirstVex(G,v)：取第一個(gè)鄰接頂點(diǎn)，給出頂點(diǎn)位置為v的第一個(gè)鄰接頂點(diǎn)的位置，如果找不到，則函數(shù)返回-1。⑺GetNextVex(G,v1,v2):取下一個(gè)鄰接頂點(diǎn),給出頂點(diǎn)位置為v1的某鄰接頂點(diǎn)v2的下—個(gè)鄰接頂點(diǎn)的位置，如果找不到，則返回-1。通過(guò)前面的學(xué)習(xí)，我們知道，同樣的操作會(huì)因?yàn)榇鎯?chǔ)結(jié)構(gòu)的不同而不同。72第8章圖8.3遍歷圖給定一個(gè)無(wú)向連通圖G，G=(V，E)，當(dāng)從V(G)中的任一頂點(diǎn)v出發(fā)，去訪問(wèn)圖中其余頂點(diǎn)，使每個(gè)頂點(diǎn)僅被訪問(wèn)一次。這個(gè)過(guò)程叫做圖的遍歷。73圖8.12存在回路的圖第8章圖然而，圖的遍歷要比樹的遍歷復(fù)雜的多。因?yàn)閳D中的任一頂點(diǎn)都可能和其余的頂點(diǎn)相鄰接。所以在訪問(wèn)某個(gè)頂點(diǎn)后，可能沿著某條路徑搜索之后，又回到該頂點(diǎn)。例如圖8.12，由于圖中存在回路，因此在訪問(wèn)了1,2,4,3之后沿著邊(3,1)又可訪問(wèn)到1。為了避免同一頂點(diǎn)被訪問(wèn)多次，在遍歷圖的過(guò)程中，必須記下每個(gè)已訪問(wèn)過(guò)的頂點(diǎn)。為此，我們?cè)O(shè)一個(gè)輔助數(shù)組，可以利用表頭向量a，讓其tag域作為標(biāo)志域

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

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

為實(shí)現(xiàn)普里姆算法，我們還需定義一個(gè)臨時(shí)數(shù)組lowCost[n]，用來(lái)保存集合U中頂點(diǎn)u與集合V-U中頂點(diǎn)v的所有邊中當(dāng)前具有最小權(quán)值的邊(u，v)?；仡檸?quán)圖中權(quán)的定義，當(dāng)弧頭頂點(diǎn)等于弧尾頂點(diǎn)時(shí)權(quán)值等于0(即鄰接矩陣的對(duì)角線元素值為0)，我們?cè)诖丝梢岳脵?quán)定義中的這一點(diǎn)，令lowCost的初始值為鄰接矩陣中第0行的值，lowCost表示了從集合U中第一個(gè)頂點(diǎn)到達(dá)集合V-U中各個(gè)頂點(diǎn)的代價(jià)。然后我們從lowCost中尋找具有最小權(quán)值的邊，這樣的邊也就意味著其弧頭頂點(diǎn)為集合U中頂點(diǎn)，其弧尾頂點(diǎn)為集合V-U中頂點(diǎn)。每選到一條這樣的邊(u,v)，就將lowCost[v]置為0，表示頂點(diǎn)v已從集合V-U加入到集合U中。如果頂點(diǎn)v從集合V-U進(jìn)入集合U后，當(dāng)前l(fā)owCost中從集合U中頂點(diǎn)到達(dá)集合V-U中頂點(diǎn)存在更小代價(jià)的邊時(shí)，則用這樣的邊的權(quán)值修改原來(lái)的權(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;/*從序號(hào)為0的頂點(diǎn)出發(fā)構(gòu)造最小生成樹*/printf("頂點(diǎn)值=%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章圖/*尋找當(dāng)前最小權(quán)值的邊的頂點(diǎ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("頂點(diǎn)值=%c邊的權(quán)值=%d\n",G.Vertices.list[k],minCost);lowCost[k]=-1;97