大二上學期學習第

第五章圖圖（Graph）是一種較線性表和樹更為復雜的非線性結構。在圖結構中，對結點（圖中常稱為頂點）的前趨和后繼個數(shù)不加限制，即結點之間的關系是任意的。圖中任意兩個結點之間都可能相關。圖狀結構可以描述各種復雜的數(shù)據(jù)對象。圖的應用極為廣泛，特別是近年來的迅速發(fā)展，已經(jīng)滲透到諸如語言學、邏輯學、物理、化學、電訊工程、計算機科學以及數(shù)學的其它分支中。圖的出現(xiàn)最早可以追溯到1736年，著名的數(shù)學家歐拉使用它解決了經(jīng)典的柯尼斯堡七橋難題。從此，有關圖的理論形成了一個專門的數(shù)學分支——圖論?？履崴贡な?8世紀初普魯士的一個小鎮(zhèn)，普雷格爾河流經(jīng)此鎮(zhèn)，共有7座橋橫跨河上，把全鎮(zhèn)連接起來。當時當?shù)鼐用駸嶂杂谝豁椃浅Ｓ腥さ南不顒樱涸谛瞧诹饕淮巫哌^所有七座橋的散步，每座橋只能經(jīng)過一次而且起點與終點必須是同一地點，這就是柯尼斯堡七橋問題。為了解決七橋問題，歐拉第一次提出了“圖”的概念。歐拉用點表示島和陸地，兩點之間的連線（邊）表示連接它們的橋，將河流、小島和橋簡化為一幅圖。定義與頂點相連的邊的數(shù)目為頂點的度，歐拉證明了如果這個問題有答案的話只有在每個頂點的度都是偶數(shù)的情況下才成立，而在七橋所形成的圖中沒有一個點具有偶數(shù)條邊，因此七橋問題不存在解。圖狀結構的實際背景

在城市之間建立通訊網(wǎng)絡，使得其中的任意兩個城市之間有直接或間接的通訊線路，假設已知每對城市之間通訊線路的造價，要求找出一個造價最低的通訊網(wǎng)絡。

城市航線網(wǎng)天津北京上海廣州深圳計算機網(wǎng)絡computerconnection

不一定具有一個根結點沒有明顯的父子關系從一個頂點到另一個頂點可能有多個（或0個）路徑圖

VS.樹

第五章圖5.1基本概念5.2圖的存儲結構5.3圖的遍歷5.4拓撲排序5.5關鍵路徑5.6最短路徑5.7最小支撐樹5.8圖的應用定義5.1：圖G由兩個集合V和E組成，記為G=(V,E)；其中V是頂點的有限集合，E是連接V中兩個不同頂點的邊的有限集合。通常，也將圖G的頂點集和邊集分別記為V(G)和E(G)。如果E中的頂點對是有序的，即E中的每條邊都是有方向的，則稱G為有向圖。如果頂點對是無序對，則稱G是無向圖。5.1圖的基本概念定義5.2

若G=(V,E)是有向圖，則它的一條有向邊是由V中兩個頂點構成的有序對，亦稱為弧，記為<w,v>，其中w是邊的始點，又稱弧尾；v是邊的終點，又稱弧頭。有向圖G=（V，E）V={v1，v2，v3，v4}E={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}v1v3v2v4無向圖G=(V,E)V={V1,V2,V3,V4,V5}E={(V1,V4),(V1,V2),(V2,V3),(V2,V5),(V3,V4),(V3,V5)}V1V4V3V2V5定義5.3

在無向圖中，若兩個頂點w和v之間存在一條邊(w,v)，則稱w,v是相鄰的，二者互為鄰接頂點。在有向圖中，若存在一條邊<w,v>，則稱頂點w鄰接到頂點v，頂點v鄰接自頂點w.v3v4v1v2oooov1v2v3v4定義5.4

由于E是邊的集合，故一個圖中不會多次出現(xiàn)一條邊。若去掉此限制，則由此產(chǎn)生的結構稱為多重圖。圖(c)就是一個多重圖。

(a)(b)(c)很多問題都可以抽象成一個圖結構，考慮如下三個例子：將電影界的所有演員構成頂點集V，其中兩位演員u和v如果共同出演過至少一部影片，那么在u和v之間連接一條邊。演員之間的這種合作關系看作對等關系。按照這種方式建立的圖是無向圖。將C++程序中所有的類構成頂點集V，且如果類a是類b的子類，則定義一條從b指向a的有向邊。按照這種方式建立的圖是有向圖。將多個城市構成頂點集V，如果城市a和城市b之間有一條高速公路，則在a和b之間連接一條邊。允許在兩個城市之間修建多條高速公路。按照這種方式建立的圖是多重圖。定義5.5

設G是無向圖，vV(G)，E(G)中以v為端點的邊的個數(shù)，稱為頂點的度。若G是有向圖，則v的出度是以v為始點的邊的個數(shù)，v的入度是以v為終點的邊的個數(shù)。有向圖中，以某頂點為弧頭的弧的數(shù)目稱為該頂點的入度。以某頂點為弧尾的弧的數(shù)目稱為該頂點的出度。頂點的度=入度+出度。度:D(v)入度:ID(v)出度:OD(v)D(v)=ID(v)+OD(v)Graph2V5V1V2V3V4V4V3V2V1Graph1設圖G(可以為有向或無向圖)共有n個頂點，e條邊，若頂點vi的度數(shù)為D(vi)，則因為一條邊關聯(lián)兩個頂點，而且使得這兩個頂點的度數(shù)分別增加1。因此頂點的度數(shù)之和就是邊的兩倍。定義5.6

設G是圖，若存在一個頂點序列使得或屬于E(G)，則稱vp到vq存在一條路徑，其中vp

稱為起點，vq稱為終點。

路徑的長度是該路徑上邊的個數(shù)。如果一條路徑上除了起點和終點可以相同外，再不能有相同的頂點，則稱此路徑為簡單路徑。如果一條簡單路徑的起點和終點相同，且路徑長度大于等于2，則稱之為簡單回路。圖(a)中，v1到v3之間存在一條路徑v1,v2,v5,v4,v3，同時這也是一條簡單路徑；v1,v2,v5,v4,v3,v1是一條簡單回路。

(a)(b)(c)V5V4V2V1V3V1V2V3V4路徑：v1v3v4v3v5簡單路徑：v1v3v5簡單回路：v1v2v3v1路徑：v1v3v2v4v3v2簡單路徑：v1v3v2簡單回路：v1v3v2v1定義5.7

設G，H是圖，如果V(H)V(G)，E(H)E(G)，則稱H是G的子圖，G是H的母圖。如果H是G的子圖，并且V(H)=V(G)，則稱H為G的支撐子圖?！璙5V1V2V3V4V1V1V2V5V2V3V5V1V2V3V4V4V3V2V1V1V2V1V4V3V2V1V4V3V1……定義5.8

設G是圖，若存在一條從頂點vi到頂點vj的路徑，則稱vi與vj可及(連通)。若G為無向圖，且V(G)中任意兩頂點都可及，則稱G為連通圖。若G為有向圖，且對于V(G)中任意兩個不同的頂點vi和vj

，vi與vj可及，vj與vi也可及，則稱G為強連通圖。也可以定義“弱連通圖”的概念，即在任何頂點u和v之間，至少存在一條從u到v的路徑或者存在一條從v到u的路徑。V5V4V2V1V3V1V2V3V4定義5.9設圖G=(V，E)是無向（或有向）圖，若G的子圖GK是一個（強）連通圖，則稱GK

為G的（強）連通子圖。定義5.10對于G的一個連通子圖GK，如果不存在G的另一個連通子圖G′，使得V(GK)?V(G′)，則稱GK為G的連通分量。(a)(b)(c)(d)(e)一個圖的連通子圖e是a的連通分量連通分量V4V3V1V2V4V3V2V1連通分量BAEJKGLMDIFCHALJCFBMDEKIHG有時候，圖不僅要表示出元素之間是否存在某種關系，同時還需要表示與這一關系相關的某些信息。例如在計算機網(wǎng)絡對應的圖中，頂點表示計算機，頂點之間的邊表示計算機之間的通訊鏈路。實際中，為了管理計算機網(wǎng)絡，我們需要這個圖包含更多的信息，例如每條通訊鏈路的物理長度、成本和帶寬等信息。為此，我們?yōu)閭鹘y(tǒng)圖中的每條邊添加相應的數(shù)據(jù)域以記錄所需要的信息。定義5.11

設G=(V,E)是圖，若對圖中的任意一條邊l，都有實數(shù)w(l)與其對應，則稱G為權圖，記為G=(V,E,w)。記w(u,v)表示w((u,v))或w(<u,v>)，規(guī)定：?u∈V,有w((u,u))=0或w(<u,u>)=0?u,v∈V,若(u,v)?E(G)或<u,v>?E(G)

則w((u,v))=＋∞或w(<u,v>)=＋∞定義5.12

若是權圖G中的一條路徑，則稱為加權路徑

的長度或權重。權通常用來表示從一個頂點到另一個頂點的距離或費用。V1V2V3V42357

無向圖

有向圖端點弧弧頭弧尾相鄰的鄰接到鄰接自度出度入度連通圖強連通圖

第五章圖5.1基本概念5.2圖的存儲結構5.3圖的遍歷5.4拓撲排序5.5關鍵路徑5.6最短路徑5.7最小支撐樹5.8圖的應用鄰接矩陣鄰接表(逆鄰接表)1、圖的存儲結構用順序方式或鏈接方式存儲圖的頂點表v0,v1,…vn-1,圖的邊用n×n階矩陣A=(aij)表示，A的定義如下：（a）若圖為權圖，aij對應邊<vi,vj>的權值；（b）若圖為非權圖，則（1）aii=0；（2）aij=1，當i≠j且<vi,vj>或(vi,vj)存在時；（3）aij=0，當i≠j且<vi,vj>或(vi,vj)不存在時。稱矩陣A為圖的鄰接矩陣。1、鄰接矩陣[例1]無向圖的鄰接矩陣無向圖的鄰接矩陣是對稱陣。0123

01111001100111100123V0V3V2V1[例2]有向圖的鄰接矩陣V0V3V4V1V201234

010001000101010100000001001234

[例3]權圖的鄰接矩陣0123035830

∞45∞0284200123V0V3V2V135284特點：無向圖的鄰接矩陣對稱，可壓縮存儲，有n個頂點的無向圖需存儲空間為n(n+1)/2有向圖鄰接矩陣不一定對稱，有n個頂點的有向圖需存儲空間為n2

借助鄰接矩陣，可以很容易地求出圖中頂點的度。無向圖

鄰接矩陣的第i行（或第i列）的非零元素的個數(shù)是頂點Vi的度。有向圖鄰接矩陣第i行的非零元素的個數(shù)為頂點Vi的出度；第i列的非零元素的個數(shù)為頂點Vi的入度。Graph1V4V3V2V1Graph2V5V1V2V3V4

0

1

1

000000001

1000

01010101010101110100011002、鄰接表鄰接表是圖的一種鏈式存儲結構。對圖的每個頂點建立一個單鏈表（n個頂點建立n個單鏈表），第i個單鏈表中的結點包含頂點Vi的所有鄰接頂點。由順序存儲的頂點表和鏈接存儲的邊鏈表構成的圖的存儲結構被稱為鄰接表。

V0V3V2V1V0V1V2V30231123∧012∧03∧03∧頂點的結構

非權圖中邊結點結構為（VerAdj,link）權圖中邊結點結構為（VerAdj,cost,link）VerNameadjacentVerAdjcostlinkVerAdjlink[例1]無向圖的鄰接表V0V3V2V1V0V1V2V30231123∧012∧03∧03∧[例2]有向圖的鄰接表V0V1V2V3V4024311∧3∧0∧0∧4∧1∧3∧V0V3V4V1V2對于用鄰接表存儲的有向圖，每條邊只對應一個邊結點；而對于用鄰接表存儲的無向圖，每條邊則對應兩個邊結點。根據(jù)鄰接表，可以統(tǒng)計出有向圖中每個頂點的出度。但是，如果要統(tǒng)計頂點的入度，每統(tǒng)計一個頂點，就要遍歷所有的邊結點，其時間復雜度為O(e)(e為圖中邊的個數(shù))，從而統(tǒng)計所有頂點入度的時間復雜度為O(ne)(n為圖的頂點個數(shù))。建立逆鄰接表(頂點的指向關系與鄰接表恰好相反)，根據(jù)逆鄰接表，很容易統(tǒng)計出圖中每個頂點的入度。[例3]有向圖的逆鄰接表V0V3V4V1V2V0V1V2V3V4024311∧0∧2∧2∧4∧1∧3∧∧[例4]權圖的鄰接表V0V3V2V135284V0V1V2V30231133∧825082∧214053∧2033∧4采用鄰接矩陣還是用鄰接表來存儲圖，要視對給定圖實施的具體操作而定。對于邊很多的圖(也稱稠密圖)，適于用鄰接矩陣存儲，因為占用的空間少。而對于頂點多而邊少的圖(也稱稀疏圖)，若用鄰接矩陣存儲，對應的鄰接矩陣將是一個稀疏矩陣，存儲利用率很低。因此，頂點多而邊少的圖適于用鄰接表存儲。鄰接矩陣存儲的圖類Graph_Matrix鄰接表存儲的圖類Graph_List2、圖的實現(xiàn)1.用鄰接矩陣存儲的圖類●Graph_Matrix類聲明constintMaxGraphSize=256;//圖的最大頂點個數(shù)constintMaxWeight=1000;//邊的最大權值template<classT>

classGraph_Matrix{private:

SLList<T>VertexList;//頂點表

intedge[MaxGraphSize][MaxGraphSize];//鄰接矩陣

intgraphsize;//當前頂點數(shù)public://I.構造函數(shù)與析構函數(shù)

Graph_Matrix(); ~Graph_Matrix();//II.圖的維護函數(shù)

intGraphEmpty(void)const//檢測圖是否為空

intGraphFull(void)const;//檢測圖是否已滿，即頂點個數(shù)是否越界

intNumberOfVertices(void)const;//返回圖的頂點個數(shù)

intNumberOfEdges(void)const;//返回圖的邊個數(shù)

intGetWeight(constintv1,constintv2);//返回指定邊的權值

int*&GetNeighbors(constintv);//返回頂點v的鄰接頂點表

intGetFirstNeighbor(constintv);//返回序號為v的頂點的第一個鄰接頂點的序號

intGetNextNeighbor(constintv1,constintv2);//返回序號為v1的頂點相對于序號為v2的頂點的下一個鄰接頂點的序號

voidInsertVertex(constint&v);//向圖中插入一個頂點

voidInsertEdge(constint&v1,constint&v2,intweight);//向圖中插入一條邊

voidDeleteVertex(constint&v);//從圖中刪除一個頂點

voidDeleteEdge(constint&v1,constint&v2);//從圖中刪除一條邊

//III.圖的基本算法

voidDepthFirstSearch();//圖的深度優(yōu)先搜索(遞歸)voidDFS(constintv);//從頂點v開始進行圖的深度優(yōu)先搜索(迭代方法)voidBFS(constintv);//從頂點v開始進行圖的廣度優(yōu)先搜索

voidTopoOrder();//圖的拓撲排序

voidCriticalPath();//輸出圖的關鍵路徑

voidShortestPath(constintv);//求無權圖中頂點v到其他頂點的最短路徑

voidDShortestPath(constintv);//求正權圖中頂點v到其他頂點的最短路徑

voidAllLength();//求正權圖中每對頂點間的最短路徑

voidPrim();//構造圖的最小支撐樹的普里姆算法

};//構造函數(shù),創(chuàng)建一個圖Graph_Matrix::Graph_Matrix(){cin>>graphsize;for(inti=0;i<graphsize;i++)for(intj=0;j<graphsize;j++)cin>>edge[i][j]; }0123035830

∞45∞0284200123ADCB35284//取得序號為v的頂點的第一個鄰接頂點的序號intGraph_Matrix::GetFirstNeighbor(constintv){if(v==-1)return-1;for(inti=0;i<graphsize;i++) if(edge[v][i]>0&&edge[v][i]<MaxWeight) returni;return-1;//若v沒有鄰接頂點，則返回-1}0123035830

∞45∞0284200123ADCB35284//取得頂點v1相對于v2的下一個鄰接頂點的序號intGraph_Matrix::GetNextNeighbor(constintv1,constintv2){if(v1==-1||v2==-1)return-1;for(inti=v2+1;i<graphsize;i++) if(edge[v1][i]>0&&edge[v1][i]<MaxWeight) returni; return-1;//若在v2之后沒有與v1鄰接的頂點，則返回-1}0123035830

∞45∞0284200123ADCB35284刪除頂點Vertex算法思想：不僅要從頂點表中刪除該頂點，還需要刪除該頂點所發(fā)出的邊以及所有的入邊，即在鄰接矩陣中刪除相應的行和列。2.用鄰接表存儲的圖類Graph_ListV0V3V2V1V0V1V2V30231123∧012∧03∧03∧2.用鄰接表存儲的圖類Graph_List//邊結點的結構體structEdge{friendclassGraph_List;intVerAdj;//鄰接頂點序號，從0開始編號

intcost; //邊的權值

Edge*link;//指向下一個邊結點的指針};//頂點表中結點的結構體structVertex{ friendclassGraph_List; intVerName; //頂點的名稱

Edge*adjacent; //邊鏈表的頭指針}

//采用鄰接表存儲的Graph_List類定義classGraph_List{private:Vertex*Head;//頂點表頭指針intgraphsize;//圖中當前頂點的個數(shù)

public://I.圖的構造函數(shù)和析構函數(shù)Graph_List();~Graph_List(); //II.圖的維護函數(shù)與Graph_Matrix類中的維護函數(shù)相同。//III.圖的基本算法與Graph_Matrix類中的基本算法相同。

};//求序號為v的頂點的第一個鄰接頂點的序號intGraph_List::GetFirstNeighbor(constintv){if(v==-1)return-1;Edge*p=Head[v].adjacent;if(p!=NULL)returnpVerAdj;elsereturn-1;}ADCBABCD0231123∧012∧03∧03∧//求序號為v1的頂點相對于序號為v2的頂點的下一個鄰接頂點的序號intGraph_List::GetNextNeighbor(constintv1,constintv2){if(v1!=-1&&v2!=-1){Edge*p=Head[v1].adjacent;while(pVerAdj!=v2&&p!=NULL) //令p指向v2所在的邊結點

p=plink;if(p==NULL)return-1;p=plink;//找v2的下一個邊結點

if(p==NULL)return-1;returnpVerAdj;}return-1;}ADCBABCD0231123∧012∧03∧03∧

第五章圖5.1基本概念5.2圖的存儲結構5.3圖的遍歷5.4拓撲排序5.5關鍵路徑5.6最短路徑5.7最小支撐樹5.8圖的應用從已給的連通圖中某一頂點出發(fā)，沿著一些邊訪遍圖中所有頂點，且使每個頂點僅被訪問一次，就叫做圖的遍歷(GraphTraversal)。圖中可能存在回路，且圖的任一頂點都可能與其它頂點相通，在訪問完某個頂點之后可能會沿著某些邊又回到了曾經(jīng)訪問過的頂點。為了避免重復訪問，可設置一個標志頂點是否被訪問過的輔助數(shù)組visited[]，它的初始狀態(tài)為0，在圖的遍歷過程中，一旦某一個頂點

i

被訪問，就立即讓visited[i]

為1，防止它被多次訪問。5.3.1深度優(yōu)先遍歷●深度優(yōu)先遍歷又被稱為深度優(yōu)先搜索DFS

(DepthFirstSearch)●基本思想:

DFS在訪問圖中某一起始頂點v后，由v出發(fā)，訪問它的任一鄰接頂點w1；再從w1出發(fā)，訪問與w1鄰接但還沒有訪問過的頂點w2；然后再從w2出發(fā)，進行類似的訪問，…如此進行下去，直至到達所有的鄰接頂點都被訪問過的頂點u為止。接著，退回一步，退到前一次剛訪問過的頂點，看是否還有其它沒有被訪問的鄰接頂點。如果有，則訪問此頂點，之后再從此頂點出發(fā)，進行與前述類似的訪問；如果沒有，就再退回一步進行搜索。重復上述過程，直到連通圖中所有頂點都被訪問過為止。深度優(yōu)先搜索DFS(DepthFirstSearch)深度優(yōu)先搜索的示例1.遞歸算法算法DepthFirstSearch(v,visited)/*圖的深度優(yōu)先遍歷的遞歸算法*/DFSearch1[初始化]PRINT(v). visited[v]

1.

p

adjacent(Head[v]).DFSearch2[深度優(yōu)先遍歷圖] WHILEp≠∧DO (IFvisited[VerAdj(p)]≠1THEN

DepthFirstSearch(VerAdj(p),visited).

p

link(p).)?算法DFS_Main(){visited=newint[graphsize];//為輔助數(shù)組申請空間

for(intk=0;k<graphsize;k++) visited[k]=0;//數(shù)組初始化

//從序號為0的頂點出發(fā)，深度優(yōu)先遍歷圖

DepthFirstSearch(0,visited[]);delete[]visited; //釋放輔助數(shù)組空間

}DFSearch1[初始化]PRINT(v).visited[v]

1.

p

adjacent(Head[v]).DFSearch2[深度優(yōu)先遍歷圖]WHILEp≠∧DO(IFvisited[VerAdj(p)]≠1THEN

DepthFirstSearch(VerAdj(p),visited).

p

link(p).)?V1V2V4V3V8V7V6V51234051717262534V1V2V3V4V5V6V7V86001234567V1V2V4V3V8V7V6V5V1V2V4V3V8V7V6V51234051717262534V1V2V3V4V5V6V7V86001234567

可以利用堆棧實現(xiàn)深度優(yōu)先遍歷的非遞歸算法。堆棧中存放已訪問結點的未被訪問的鄰接頂點，每次彈出棧頂元素時，如其未被訪問，則訪問該頂點，并檢查當前頂點的邊鏈表，將其未被訪問的鄰接頂點入棧，循環(huán)進行。2.非遞歸算法（迭代）算法

首先將所有頂點的visited[]值置為0,初始頂點壓入堆棧；①檢測堆棧是否為空。若堆棧為空，則迭代結束；否則，從棧頂彈出一個頂點v；②如果v未被訪問過，則訪問v，將visited[v]值更新為1，然后根據(jù)v的鄰接頂點表，將v的未被訪問的鄰接頂點壓入棧，執(zhí)行步驟①。A0243156BCDEFG16∧2∧34∧5∧0∧5∧4∧ACGBFED算法DFS(Head,v

,visited.visited)/*圖的深度優(yōu)先遍歷的非遞歸算法*/DFS1[初始化]CREATS(S)./*創(chuàng)建堆棧S*/FORi=1TOnDOvisited[i]0.S

v./*將v壓入棧中*/DFS2[利用堆棧S深度優(yōu)先遍歷圖]WHILENOT(ISEMTS(S))DO/*當S不空時*/

(vS./*彈出堆棧頂元素*/IFvisited[v]=0THEN//若v未被訪問

(PRINT(v).visited[v]1.

p

adjacent(Head[v]).//找v的第一個鄰接頂點pWHILEpDO (IFvisited[VerAdj(p)]=0THENS

VerAdj(p).//把所有未被訪問的鄰接頂點入棧p

link(p).))

)?算法分析圖中有n個頂點，e條邊。如果用鄰接表表示圖，沿頂點的adjacent可以找到某個頂點v的所有鄰接頂點w。由于總共有2e個邊結點，所以掃描邊的時間為O(e)。而且對所有頂點遞歸訪問1次，所以遍歷圖的時間復雜性為O(n+e)。如果用鄰接矩陣表示圖，則查找每一個頂點的所有的邊，所需時間為O(n)，則遍歷圖中所有的頂點所需的時間為O(n2)。非連通圖需要多次調用深度優(yōu)先遍歷算法Fori=0ton-1DO visited[i]0.Forj=0ton-1DO IFvisited[j]=0THEN

DepthFirstSearch(v[j],visited)V1V2V35.3.2廣度優(yōu)先遍歷

●

基本思想：首先訪問初始點頂點v0，之后依次訪問與v0鄰接的全部頂點w1，w2，...，wk。然后，再順次訪問與w1，w2，...，wk鄰接的尚未訪問的全部頂點，再從這些被訪問過的頂點出發(fā)，逐個訪問與它們鄰接的尚未訪問過的全部頂點。依此類推，直到連通圖中的所有頂點全部訪問完為止。廣度優(yōu)先搜索BFS(BreadthFirstSearch

)廣度優(yōu)先搜索的示例

廣度優(yōu)先搜索過程 廣度優(yōu)先生成樹廣度優(yōu)先搜索類似于樹的層次遍歷，是一種分層的搜索過程，每向前走一步可能訪問一批頂點，不像深度優(yōu)先搜索那樣有回退的情況。因此，廣度優(yōu)先搜索不是一個遞歸的過程，其算法也不是遞歸的。為了實現(xiàn)逐層訪問，算法中使用一個隊列，以便于向下一層訪問。與深度優(yōu)先搜索過程一樣，為避免重復訪問，需要一個輔助數(shù)組visited[]

。算法BFS(Head,v,visited.visited)/*廣度優(yōu)先遍歷算法*/BFS1[初始化]CREATQ(Q)./*創(chuàng)建隊列Q*/FORi=1TOnDOvisited[i]0.

PRINT(v).visited[v]1.Qv./*入隊*/BFS2[廣度優(yōu)先遍歷]WHILENOT(ISEMTQ(Q))DO/*當隊列不空時*/

(vQ./*出隊*/

p

adjacent(Head[v]). WHILEpDO/*依次處理v的每個未被訪問的鄰接頂點*/ (IFvisited[VerAdj(p)]=0THEN (Q

VerAdj(p). PRINT(VerAdj(p)).visited[VerAdj(p)]1.).

p

link(p).)

)?

WHILENOT(ISEMTQ(Q))DO/*當隊列不空時*/(vQ./*出隊*/

p

adjacent(Head[v]).WHILEpDO (IFvisited[VerAdj(p)]=0THEN (Q

VerAdj(p). PRINT(VerAdj(p)).

visited[VerAdj(p)]1.)

p

link(p).))

01234567024315670123457612∧04∧306∧517∧27∧27∧36∧4517∧算法分析如果使用鄰接表表示圖，則循環(huán)的總時間代價為d0+d1+…+dn-1=O(e)，其中的di是頂點i的度?？偟臅r間復雜度為O(n+e)。如果使用鄰接矩陣，則對于每一個被訪問的頂點，循環(huán)要檢測矩陣中的n個元素，總的時間代價為O(n2)。

第五章圖5.1基本概念5.2圖的存儲結構5.3圖的遍歷5.4拓撲排序5.5關鍵路徑5.6最短路徑5.7最小支撐樹5.8圖的應用

5.4拓撲排序

1、拓撲排序問題：計劃、施工過程、生產(chǎn)流程、程序流程等都是“工程”。除了很小的工程外，一般都把工程分為若干個叫做“活動”的子工程。完成了這些活動，這個工程就可以完成了。AOV網(wǎng):在有向圖中，用頂點表示活動，用有向邊表示活動之間的先后關系，稱這樣的有向圖為AOV網(wǎng)(ActivityOnVertexNetwork)。例如，計算機專業(yè)學生的學習就是一個工程，每一門課程的學習就是整個工程的一些活動。其中有些課程要求先修課程，有些則不要求。這樣在有的課程之間有領先關系，有的課程可以并行地學習。

[例]按拓撲次序安排計算機專業(yè)必修課程計算機專業(yè)必修課程課程代號 課程名稱 先修課程

C0

高等數(shù)學 無

C1

程序設計基礎 無

C2 離散數(shù)學C0,C1

C3

數(shù)據(jù)結構 C2,C4

C4

程序設計語言

C1

C5

編譯技術

C3,C4

C6

操作系統(tǒng)

C3,C8

C7

普通物理 C0

C8

計算機原理C7

C0C2C3C5C4C1C7C6C8AOV網(wǎng)中，如果活動Vi必須在活動Vj之前進行，則存在有向邊<Vi

,Vj>.

AOV網(wǎng)中不能出現(xiàn)有向回路，即有向環(huán)。在AOV網(wǎng)中如果出現(xiàn)了有向環(huán)，則意味著某項活動應以自己作為先決條件，表示該網(wǎng)絡的構建存在邏輯錯誤。拓撲序列：把AOV網(wǎng)中的所有頂點排成一個線性序列，使每個活動的所有前驅活動都排在該活動的前邊。拓撲排序：構造AOV網(wǎng)的拓撲序列的過程被稱為拓撲排序。序列C0,C1,C2,C4,C3,C5,C7,C8,C6序列C1,C4,C0,C2,C7,C8,C3,C5,C6是否為拓撲序列？C0C2C3C5C4C1C7C6C82、拓撲排序基本步驟：①

從網(wǎng)中選擇一個入度為0的頂點且輸出之。②

從網(wǎng)中刪除該頂點及其所有出邊。③

執(zhí)行①②，直至所有頂點已輸出，或網(wǎng)中剩余頂點入度均不為0(說明網(wǎng)中存在回路，無法繼續(xù)拓撲排序)C0C2C3C5C4C1C7C6C8

回路與拓撲排序任何無回路的AOV網(wǎng)，其頂點均可排成拓撲序列(其拓撲序列不一定唯一)；如果能將AOV網(wǎng)的所有頂點都排入一個拓撲序列，則該AOV網(wǎng)中必定無有向環(huán)；如果得不到所有頂點的拓撲序列，則說明AOV網(wǎng)中存在有向環(huán)(AOV網(wǎng)所代表的工程是不可行的)。存在回路的AOV網(wǎng)，找不到所有頂點的拓撲序列。因此，可以用拓撲排序判斷有向圖中是否有回路假定AOV網(wǎng)用鄰接表的形式存儲。為實現(xiàn)拓撲排序算法，事先需做好兩項準備工作：建立一個數(shù)組count[]，count[i]的元素值取對應頂點i的入度；建立一個堆棧，棧中存放入度為0的頂點，每當一個頂點的入度為0，就將其壓入棧。3、拓撲排序算法325140002123013425count0243152∧42∧3∧53∧5∧5∧在初始化堆棧和入度數(shù)組count基礎上，拓撲排序算法核心步驟：FORi=1TOnDO (jPop(S)

/*彈出棧頂j*/PRINT(j). p

adjacent(Head[j]).//掃描j的邊鏈表

WHILEp

DO

(k

VerAdj(p).count[k]

count[k]-1.//k的入度減1IFcount[k]=0THEN//若入度為0，

Push(S,k).//則k入棧

p

link(p).))?用一個堆