《數(shù)據(jù)結(jié)構(gòu)與算法項目化教程》課件第6章

學(xué)習(xí)情境６圖6.1任務(wù)一認(rèn)識圖6.2任務(wù)二圖的表示6.3任務(wù)三圖的遍歷6.4任務(wù)四圖的應(yīng)用6.5任務(wù)五圖的程序?qū)崿F(xiàn)圖是一種非線性數(shù)據(jù)結(jié)構(gòu)，各數(shù)據(jù)之間允許具有多對多的關(guān)系：圖中的每個數(shù)據(jù)可有多個前驅(qū)數(shù)據(jù)和多個后繼數(shù)據(jù)，任意兩個數(shù)據(jù)都可以相鄰。圖是刻畫離散結(jié)構(gòu)的一種有力工具，廣泛應(yīng)用于運籌學(xué)、網(wǎng)絡(luò)研究和計算機(jī)程序流程分析。生活中，我們經(jīng)常以圖表達(dá)文字難以描述的信息，如城市交通圖、路線圖、網(wǎng)絡(luò)圖等。本學(xué)習(xí)情境介紹圖的基本概念、圖的鄰接矩陣和鄰接表兩種存儲結(jié)構(gòu)，實現(xiàn)圖深度優(yōu)先遍歷和廣度優(yōu)先遍歷以及最小生成樹和最短路徑問題。

6.1任務(wù)一認(rèn)識圖6.1.1子任務(wù)1初識圖

1．圖的定義圖(graph)是由頂點(vertex)集合及頂點間的關(guān)系集合組成的一種數(shù)據(jù)結(jié)構(gòu)。頂點之間的關(guān)系稱為邊(edge)。一個圖G記為G=(V,E)，V是頂點A的有限集合，E是邊的有限集合，即

V={A|A∈某個數(shù)據(jù)集合}， E={(A,B)|A,B∈V}或 E={<A,B>|A,B∈V且path(A,B)}其中，path(A,B)表示從頂點A到B的一條通路。

2．圖的類型

(1)無向圖。無向圖(undirectedgraph)中的邊沒有方向，每條邊用兩個頂點的無序?qū)Ρ硎荆?A,B)表示連接頂點A和B之間的一條邊，(A,B)和(B,A)表示同一條邊。圖6-1是一個無向圖，用G表示無向圖，其頂點集合V為

V(G)?=?{A,B,C,D,E}邊集合E為

E(G)?=?{(A,B),(A,E),(B,C),(B,D),(B,E)(C,D),(D,E)}圖6-1圖

(2)有向圖。有向圖(directedgraph)中的邊有方向，每條邊用兩個頂點的有序?qū)Ρ硎?，?lt;A,B>表示從頂點A到B的一條有向邊，A是邊的起點，B是邊的終點。因此，<A,B>和<B,A>表示方向不同的兩條邊。有向圖G如圖6-2所示，圖中箭頭表示邊的方向，箭頭從起點指向終點。圖6-2的中圖G的頂點集合V和邊集合E分別為

V(G)={A,B,C,D,E} E(G)={<A,B>,<A,D>,<A,E>,<B,C>,<C,B>,<C,D>,<D,B>,<D,E>,<E,A>}圖6-2有向圖

(3)自身環(huán)的圖和多重圖。如圖6-3所示，頂點C有一個路徑指向自身，這種圖稱為帶自身環(huán)的圖；頂點B有兩條路徑到頂點A，這種圖屬于多重圖。這些一般不屬于數(shù)據(jù)結(jié)構(gòu)討論的范疇，本學(xué)習(xí)情境只討論無向圖和有向圖。

(4)完全圖。完全圖(completegraph)的任一頂點均有路徑到其他頂點。完全圖的邊數(shù)是最大的。無向完全圖的邊數(shù)有n?×?(n-1)/2，有向完全圖的邊數(shù)為n?×?(n-1)。圖6-3自身環(huán)、多重圖

(5)帶權(quán)圖。帶權(quán)圖(weightedgraph)中的一頂點到另一頂點的路徑有不同的耗費(時間、距離等)，耗費值稱權(quán)重值(weight)。在不同的應(yīng)用中，權(quán)值有不同的含義。例如，如果頂點表示計算機(jī)網(wǎng)絡(luò)節(jié)點，則兩個頂點間邊的權(quán)值可以表示兩個計算機(jī)節(jié)點間的距離、從一個節(jié)點到另一個節(jié)點所需的時間或所花費的代價等。帶權(quán)圖也稱為網(wǎng)絡(luò)(network)。帶權(quán)圖如圖6-4所示，邊上標(biāo)示的實數(shù)為權(quán)值。

(6)鄰接頂點。若(A,B)是無向圖E(G)中的一條邊，則A和B互為鄰接頂點(adjacentvertex)，且邊(A,B)依附于頂點A和B，頂點A和B依附于邊(A,B)。若<A,B>是有向圖E(G)中的一條邊，則稱頂點A鄰接于頂點B，頂點B鄰接自頂點A，邊<A,B>與頂點A和B相關(guān)聯(lián)。圖6-4帶權(quán)圖

3．頂點的度頂點的度(degree)指與頂點A關(guān)聯(lián)的邊數(shù)，記為deg(A)。

(1)無向圖頂點的度。無向圖頂點的度是連接該頂點的邊數(shù)，如圖6-4中頂點B的度deg(B)=3。

(2)有向圖頂點的度。在有向圖中，以A為終點的邊數(shù)稱為A的入度，記為indeg(A)：以A為起點的邊數(shù)稱為A的出度，記為outdeg(A)。出度為0的頂點稱為終端頂點(或葉子頂點)。頂點的度是入度與出度之和，有deg(A)=indeg(A)+outdeg(A)。圖6-2中，頂點A的入度indeg(A)=1，出度outdeg(A)=3，度deg(A)=4。(3)圖的邊與度的關(guān)系。若G為無向圖，頂點集合V={v1,v2,…,vn}，有ｅ條邊，則若G為有向圖，則6.1.2子任務(wù)2再識圖

1．子圖設(shè)圖G=(V,E)，G'=(V'，E')，若V'V且E'E，則稱圖G'是G的子圖(subgraph)。若G'≠G，稱圖G'是G的真子圖。若G'是G的子圖，且V'=V，稱圖G'是G的生成子圖(spanningsubgraph)。無向圖及部分生成子圖如圖6-5所示，有向圖及部分生成子圖如圖6-6所示。圖6-5無向圖及生成子圖圖6-6有向圖及生成子圖

2．路徑在圖G=(V,E)中，若存在頂點序列(vi,vp1,vp2,…,vpm,vj)且邊(vi,vp1)，(vp1,vp2),…,(vpm,vj)都是E(G)的邊，則稱頂點序列(vi,vp1,vp2,…,vpm,vj)是從頂點vi到vj的一條路徑(path)。若G是有向圖，則路徑<vi,vp1,vp2,…,vpm,vj>也是有向的，vi為路徑起點，vj為終點。對于不帶權(quán)圖，路徑長度(pathlength)指該路徑的邊數(shù)；對于帶權(quán)圖，路徑長度指該路徑上各條邊的權(quán)值之和。簡單路徑(simplepath)是指路徑<v1,v2,…,vm>上各頂點互不重復(fù)?；芈?cycle)是指起點和終點相同且長度大于1的簡單路徑，回路又稱環(huán)。

3．連通性

(1)連通和連通分量。在無向圖G中，若從頂點vi到vj有路徑，則稱vi和vj是連通的。若圖中G任意一對頂點vi和vj(vi≠vj)都是連通的，則稱G為連通圖(connectedgraph)。非連通圖的極大連通子圖稱為該圖的連通分量(connectedcomponent)。例如，圖6-7(a)是連通圖，圖6-7(b)是非連通圖，它由兩個連通分量組成。

(2)強連通圖和強連通分量。在有向圖中，若在每一對頂點vi和vj(vi≠vj)之間都存在一條從vi到vj的路徑，也存在一條從vj到vi的路徑，則稱該圖是強連通圖(stronglyconnectedgraph)。非強連通圖的極大強連通圖稱為該圖的強連通分量。例如，圖6-2是強連通圖，圖6-8(a)是非強連通圖，因為從頂點B到A沒有路徑，它由兩個強連通分量組成，如圖6-8(b)所示。圖6-7連通圖和非連通圖圖6-8非強連通圖和其強連通分量6.2任務(wù)二圖的表示從任務(wù)一中可以看到，圖是由頂點集合和邊集合組成的，因此存儲一個圖需要存儲圖的頂點集合和邊集合。圖的存儲結(jié)構(gòu)通常采用鄰接矩陣、鄰接表、鄰接多重表等表示。本學(xué)習(xí)情境主要介紹鄰接矩陣、鄰接表兩種結(jié)構(gòu)。6.2.1子任務(wù)1圖的鄰接矩陣表示圖的鄰接矩陣表示采用數(shù)學(xué)中矩陣的行號和列號來表示圖的頂點，矩陣中某行某列對應(yīng)的數(shù)據(jù)來表示圖的邊。

1．圖的鄰接矩陣圖的鄰接矩陣(adjacencymatrix)是表示圖中各頂點之間鄰接關(guān)系的矩陣。根據(jù)邊是否帶權(quán)值，鄰接矩陣有不帶權(quán)圖的鄰接矩陣和帶權(quán)圖的鄰接矩陣兩種。

2．不帶權(quán)圖的鄰接矩陣設(shè)圖G=(V,E)有n(n≥1)個頂點，V={v0,v1,…,vn-1}，E可用一個矩陣A描述，A=[aij](0≤i<n,0≤j<n)定義如下：

A稱為圖G的鄰接矩陣。A的數(shù)據(jù)aij表示G中的頂點vi到vj之間的鄰接關(guān)系，若存在從頂點vi到vj的邊，則aij?=?1，否則aij?=?0。圖6-1是無向圖，其鄰接矩陣如圖6-9所示；圖6-2是有向圖，其鄰接矩陣如圖6-10所示。圖6-9無向圖鄰接矩陣表示圖6-10有向圖鄰接矩陣表示無向圖的鄰接矩陣是對稱的，有向圖的鄰接矩陣不一定對稱。從鄰接矩陣可計算出頂點的度。對于無向圖，鄰接矩陣第i行(或第i列)上各數(shù)據(jù)之和是頂點vi的度；對于有向圖，鄰接矩陣第i行上的各數(shù)據(jù)之和是頂點vi的出度，第i列上的各數(shù)據(jù)之和是頂點vi的入度。

3．帶權(quán)圖的鄰接矩陣帶權(quán)圖的鄰接矩陣A?=?[aij](0≤i<n,0≤j<n)定義如下，其中wij(wij>0)表示無向圖邊(vi,vj)或有向圖邊<vi,vj>的權(quán)值。帶權(quán)無向圖和帶權(quán)有向圖及其鄰接矩陣如圖6-11和圖6-12所示。圖6-11帶權(quán)無向圖及其鄰接矩陣表圖6-12帶權(quán)有向圖及其鄰接矩陣表6.2.2子任務(wù)2圖的鄰接表表示圖的鄰接表(adjacencylist)表示采用鏈表存儲與一個頂點相關(guān)聯(lián)的頂點和邊信息。一個圖的鄰接表表示由頂點表和邊表組成。頂點表順序存儲圖中的所有頂點數(shù)據(jù)，邊表以單鏈表存儲與頂點相關(guān)聯(lián)的頂點及邊，每個頂點都關(guān)聯(lián)一條鏈表。圖的鄰接表表示相對圖的鄰接矩陣表示而言，可以減少存儲空間，這是由于圖的鄰接矩陣表示將頂點vi與其他頂點的鄰接關(guān)系順序存儲在鄰接矩陣的第i行和第i列，即使兩個頂點之間沒有鄰接關(guān)系，也占用一個存儲單遠(yuǎn)存儲0或∞；而圖的鄰接表表示則不存儲沒有鄰接關(guān)系的頂點。

1．鄰接表頂點表數(shù)據(jù)由兩個域組成：第i個頂點數(shù)據(jù)vi和該頂點的邊鏈表引用結(jié)構(gòu)如圖6-13(a)所示。邊鏈表中的節(jié)點由三個域組成：鄰接頂點dest、邊的權(quán)重值weight和下一個鄰接頂引用，結(jié)構(gòu)如圖6-13(b)所示。

2．無向圖的鄰接表表示邊表中，第i行單鏈表存儲所有與頂點vi相關(guān)聯(lián)的邊，每個邊節(jié)點存儲從頂點vi到vj的一條邊(vi,vj)，dest域是該條邊的終點vj在頂點表中的下標(biāo)，weight域存儲邊(vi,vj)的權(quán)值wij，nxet域指向與vi關(guān)聯(lián)的下一條邊。帶權(quán)無向圖的鄰接表表示如圖6-14所示。圖6-13鄰接表元素圖6-14帶權(quán)無向圖的鄰接表表示

3．有向圖的鄰接表表示以鄰接表表示有向圖，需要根據(jù)邊的方向而得到邊表，邊表有兩種：出邊表和入邊表。出邊表：第i行單鏈表存儲以頂點vi為起點的所有邊<vi,vj>，dest域是該條邊的終點vj在頂點表中的下標(biāo)。入邊表：第i行單鏈表存儲以頂點vi為終點的所有邊<vj,vi>，dest域是該條邊的起點vj在頂點表中的下標(biāo)。有向圖的鄰接表表示有兩種，分別是由出邊表構(gòu)成的鄰接表和由入邊表構(gòu)成的逆鄰接表。帶權(quán)有向圖鄰接表的出邊表表示如圖6-15所示。在有向圖的鄰接表或逆鄰接表中，每條邊只存儲一次。圖6-15帶權(quán)有向圖鄰接表的出邊表表示一個有n個頂點、e條邊的圖G，當(dāng)n較小且e較大時，采用鄰接矩陣存儲效率較高；當(dāng)n較大且e<<n時，采用鄰接表存儲效率較高。在實際存儲中，可以根據(jù)需要選擇鄰接矩陣或鄰接表進(jìn)行存儲。6.3任務(wù)三圖的遍歷圖的遍歷指從圖中任意一個頂點V出發(fā)，沿著圖中的邊對其他頂點進(jìn)行訪問，到達(dá)并訪問圖中的所有頂點，且每個頂點僅被訪問一次。圖的遍歷有兩種：深度優(yōu)先搜索遍歷和寬度優(yōu)先搜索遍歷。6.3.1子任務(wù)1圖的深度優(yōu)先搜索遍歷

1．深度優(yōu)先搜索圖的深度優(yōu)先搜索(DepthFirstSearch)策略是，訪問某個頂點vi，接著尋找vi的另一個未被訪問的鄰接頂點vj訪問，如此反復(fù)執(zhí)行，走過一條較長路徑到達(dá)最遠(yuǎn)頂點；若頂點vj沒有未被訪問的其他鄰接頂點，則回到前一個被訪問頂點，再以深度優(yōu)先搜索其他訪問路徑。從一頂點出發(fā)的深度優(yōu)先搜索遍歷序列不是唯一的。如對圖6-1所示的無向圖的深度優(yōu)先搜索遍歷序列可能是：{A，E，D，B，C}、{A，E，B，C，D}、{A，B，C，D，E}等。對圖6-2所示的無向圖的深度優(yōu)先搜索遍歷序列可能是：{A，B，C，D，E}、{A，E，B，C，D}等。對于一個連通無向圖或一個強連通的有向圖，以任何一個頂點為起點，一定存在路徑能夠到達(dá)其他所有頂點。因此，從一個頂點vi出發(fā)的一次遍歷，可以訪問圖中的每個頂點。對于一個非連通無向圖或一個非強連通的有向圖，從一個頂點vi出發(fā)的一次遍歷只能訪問圖中的一個連通分量。因此，遍歷一個非連通圖需要遍歷各個連通分量。

2．圖的深度優(yōu)先搜索遍歷算法從非連通圖中一個頂點vi出發(fā)的一次深度優(yōu)先搜索遍歷算法描述如下：

(1)訪問頂點vi，標(biāo)記vi為被訪問頂點。

(2)選定一個鄰接于vi且未被訪問的頂點vi+1，從vi+1開始進(jìn)行深度優(yōu)先搜索。

(3)若能由vi+1到達(dá)的所有頂點都已被訪問，則回到頂點vi。

(4)若仍有鄰接于vi且未被訪問的頂點，則從該頂點出發(fā)繼續(xù)搜索其他路徑，否則由頂點vi出發(fā)的一次搜索過程結(jié)束。圖深度優(yōu)先遍歷操作程序?qū)崿F(xiàn)詳見AbstractCraph.java中的depthFirstSearchGraph()方法和depthFirstSearchVi()方法。6.3.2子任務(wù)2圖的廣度優(yōu)先搜索遍歷

1．廣度優(yōu)先搜索廣度優(yōu)先搜索(BreadthFirstSearch)方法是，訪問某個頂點vi，接著依次訪問頂點vi所有未被訪問的鄰接頂點vj,vj+1,…，vk，再以廣度優(yōu)先訪問頂點vj,vj+1,…，vk所有未被訪問的其他鄰接頂點，如此反復(fù)執(zhí)行，直到訪問完圖中所有頂點。從一頂點出發(fā)的廣度優(yōu)先搜索遍歷序列也不是唯一的。如對圖6-1的無向圖的廣度優(yōu)先搜索遍歷序列可能是：{A，E，B，D，C}、{A，B，E，C，D}、{A，B，E，D，C}等。對圖6-2的無向圖的廣度優(yōu)先搜索遍歷序列可能是：{A，B，E，C，D}、{A，E，B，C，D}等。

2．圖的廣度優(yōu)先搜索遍歷算法在圖的廣度優(yōu)先搜索遍歷中，需要一種數(shù)據(jù)結(jié)構(gòu)記錄各頂點的訪問次序。若vi在vj之前訪問，則vi的所有鄰接頂點在vj的所有鄰接頂點之前訪問。因此，使用隊列記錄各頂點的訪問次序。圖廣度優(yōu)先遍歷程序?qū)崿F(xiàn)詳見AbstractCraph.java中的breadthFirstSearchGraph()方法和breadthFirstSearchVi()方法。6.4任務(wù)四圖的應(yīng)用6.4.1子任務(wù)1最小生成樹

1．生成樹連通的無回路的無向圖稱為無向樹，簡稱樹。生成樹(spanningtree)是一個連通無向圖的一個極小連通生成子圖，它包含原圖中所有頂點(n個)，以及足以構(gòu)成一棵樹的n-1條邊。在生成樹中，任何兩個頂點之間只有唯一的一條路徑。圖的生成樹不是唯一的，從不同頂點開始、采用不同遍歷可以得到不同的生成樹或生成森林。以深度優(yōu)先搜索遍歷得到的生成樹，稱為深度優(yōu)先生成樹；以廣度優(yōu)先搜索遍歷得到的生成樹，稱為廣度優(yōu)先生成樹。

2．最小生成樹設(shè)G是一個帶權(quán)連通無向圖，w(e)是邊e上的權(quán)，T是G的生成樹，T中各邊的權(quán)之和為這稱為生成樹T的權(quán)或耗費(cost)。權(quán)值最小的生成樹稱為最小代價生成樹，簡稱最小生成樹。

3．最小生成樹的構(gòu)造算法按照生成樹的定義，n個頂點的連通無向圖的生成樹有n個頂點和n-1條邊。因此，構(gòu)造最小生成樹有以下三個原則：

(1)必須只使用該圖中的邊來構(gòu)造最小生成樹。

(2)必須使用且僅使用n-1條邊來連接圖中的n個頂點。

(3)不能使用產(chǎn)生回路的邊。構(gòu)造最小生成樹主要有兩種算法：Prim算法和Kruskal算法。這兩種算法都是基于最小生成樹的MST性質(zhì)：設(shè)G=(V,E)是一個帶權(quán)連通無向圖，U是頂點集合V的一個非空真子集。若(u,v)是一條具有最小權(quán)值的邊，其中u∈U,v∈(V-U)，則必存在一棵包含邊(u,v)的最小生成樹。

4．Prim算法

Prim算法是由R.C.Prim于1956年提出的。Prim算法根據(jù)MST特性，采用逐步求解的策略： 設(shè)G=(V,E)是帶權(quán)連通無向圖，T=(U,TE)為G的最小生成樹，則有

(1)最初U={v0}(v0∈V),TE={}。

(2)重復(fù)執(zhí)行以下操作：在所有u∈U,v∈(V-U)的邊(u,v)∈E中，找出一條權(quán)值最小的邊(u0,v0)并入集合TE，同時將v0并入集合U，直至U=V。最終，TE中必有n-1條邊，則T=(V,TE)為G的一棵最小生成樹。對于帶權(quán)無向圖，以Prim算法構(gòu)造其最小生成樹的過程如圖6-16所示。圖6-16Prim算法構(gòu)造最小生成樹

5．Kruskal算法

Kruskal算法也是根據(jù)MST特性采用逐步求解的策略，每次選擇權(quán)值最小且不產(chǎn)生回路的一條邊加入生成樹，直到加入n-1條邊，則構(gòu)造成一棵最小生成樹。Kruskal算法如下:設(shè)G=(V,E)是帶權(quán)連通無向圖，T=(U,TE)為G的最小生成樹，則有

(1)?T的最初狀態(tài)是U=V，TE={}，即T有G的n個頂點而沒有邊，T中每個頂點各自構(gòu)成一個連通分量。

(2)在E(G)中選擇權(quán)值最小一條邊，若該邊的兩個頂點分別在T的兩個不同連通分量中，則將此邊加入T；否則舍去該邊，再選擇下一條權(quán)值最小的邊。T中每加入一條邊，則原來的兩個連通分量連接為一個連通分量。依次類推，重復(fù)執(zhí)行(2)操作，直到T中所有頂點都在同一連通分量中，則T=(V,TE)為G的一棵最小生成樹。對于帶權(quán)無向圖，以Kruskal算法構(gòu)造其最小生成樹的過程如圖6-17所示。圖6-17Kruskal算法構(gòu)造最小生成樹6.4.2子任務(wù)2最短路徑設(shè)G=(V,E)是一個帶權(quán)圖，若G中從頂點v到頂點u的一條路徑(v,v1,…,vi,u)，其路徑長度小于等于從v到u的所有其他路徑的路徑長度，則該路徑是從v到u的最短路徑(shortestpath)，v稱為源點，u稱為終點。求最短路徑問題主要有兩種：求從源點v到圖中其他各頂點的最短路徑稱為單源最短路徑；求圖中每一對頂點之間的最短路徑。單源最短路徑是圖中每一對頂點之間的最短路徑的基礎(chǔ)。求單源最短路徑的最典型算法是Dijkstra算法。

1．Dijkstra算法已知G=(V,E)是一個帶權(quán)圖，且圖中各邊的權(quán)值大于等于0。Dijkstra算法按照路徑長度遞增的順序逐步求得最短路徑。設(shè)G中最短路徑的頂點集合是S，則尚未確定最短路徑的頂點集合是V-S。算法如下：

(1)開始，S={v},v∈V,從源點v到其他頂點的最短路徑設(shè)置為從v到其他頂點的邊。

(2)若求出一條從v到頂點u的最短路徑(v,v1,…,vi,u)，vi∈S，u∈V-S，則將終點u并入S，再根據(jù)最短路徑(v,…,u)調(diào)整從v到V-S中其他頂點的最短路徑及其長度。

(3)反復(fù)執(zhí)行(2)，直到V中所有頂點都并入S。

2．Dijkstra算法實例對于圖6-12所示的帶權(quán)有向圖，表6-1給出了以Dijkstra算法求從頂點D到其余各頂點的最短路徑的過程。表6-1Dijkstra算法求從頂點D到其余各頂點的最短路徑6.4.3子任務(wù)3拓?fù)渑判蛲負(fù)渑判?TopologicalSort)是從工程領(lǐng)域中抽象出來的問題求解方法。一般來說，一個工程大多由若干項子工程(或活動，后面就用活動來代替子工程)組成，各項活動之間存在一定的制約關(guān)系。

1．AOV網(wǎng)

AOV網(wǎng)(ActivityonVertex)用頂點表示活動，用邊來表示活動時間的制約關(guān)系。AOV網(wǎng)常用來描述和分析一項工程的計劃和實施過程。一個工程中有A、B、C共3件事要做，但互相間存在這樣的制約關(guān)系：A完成之后才能到B，B完成之后才能到C，C完成之后才能到A。很顯然，這種關(guān)系將導(dǎo)致工程無法進(jìn)行。

2．拓?fù)渑判蚺袛喙こ棠芊襁M(jìn)行的問題就變成了判斷AOV網(wǎng)中是否存在有向回路的問題。對這一問題的求解是通過產(chǎn)生滿足如下條件的(包含所有頂點的)頂點序列來實現(xiàn)的：若AOV網(wǎng)中頂點vi到頂點vj之間存在路徑，則在序列中頂點vi領(lǐng)先于頂點vj滿足上述條件的頂點序列稱為拓?fù)湫蛄校a(chǎn)生這一序列的過程稱為拓?fù)渑判?。這樣，判斷AOV網(wǎng)中是否存在有向回路的問題變成了拓?fù)渑判虻膯栴}：如果拓?fù)渑判蚰茌敵鏊许旤c，則說明不存在回路，否則就存在回路。

3．拓?fù)渑判蛩惴ㄍ負(fù)渑判蛩惴ㄈ缦拢?/p>

(1)找出一個入度為0的頂點V并輸出。

(2)刪除頂點V及其相關(guān)的弧，因而使其后續(xù)頂點的入度減1，并可能出現(xiàn)新的入度為0的頂點。

(3)重復(fù)(1)、(2)，直到找不到入度為0的頂點為止。經(jīng)過上述操作之后，若所有頂點都被輸出了，則說明AOV網(wǎng)中不存在回路，否則存在回路。由于每次刪除一個頂點后，可能使不止一個頂點的入度為0，因此拓?fù)渑判蜉敵龅慕Y(jié)果不唯一。如圖6-18所示，拓?fù)渑判虻倪^程可得到一個排序序列：{C，A，E，F(xiàn)，D，B，G}。上述AOV網(wǎng)使用拓?fù)渑判蚍椒ǎ梢缘玫酵負(fù)渑判蛐蛄羞€有：{C，A，D，B，E，F(xiàn)，G}、{C，A，D，E，F(xiàn)，B，G}、{C，A，D，E，B，F(xiàn)，G}、{C，E，F(xiàn)，A，D，B，G}、{C，E，A，F(xiàn)，D，B，G}等等。雖然還可以有更多的輸出，但該AOV網(wǎng)的拓?fù)漭敵鲋杏袔c順序必須遵循：

(1)?C必須是第一個輸出。

(2)?G必須是最后一個輸出。

(3)?E必須在F前輸出。

(4)?A必須在D和B前輸出。

(5)?D必須在B前輸出。圖6-18拓?fù)渑判蜻^程6.5任務(wù)五圖的程序?qū)崿F(xiàn)圖的程序?qū)崿F(xiàn)主要步驟如下：

(1)進(jìn)行圖的遍歷抽象類構(gòu)造(可用于鄰接矩陣表示和鄰接表表示的圖)。

(2)定義鄰接矩陣表示的邊(起點，終點，權(quán)重值)、鄰接矩陣表示實現(xiàn)。

(3)定義鄰接表頂點、鄰接表表示實現(xiàn)。

(4)存儲圖信息的文件讀/寫實現(xiàn)。

(5)具體應(yīng)用的程序?qū)崿F(xiàn)。6.5.1子任務(wù)1構(gòu)造圖的遍歷抽象類創(chuàng)建圖的程序?qū)崿F(xiàn)的包，包名為ch6Map，在ch6Map包中創(chuàng)建MapAbstract.java抽象文件。

1．圖的遍歷圖的遍歷是從頂點出發(fā)對全圖進(jìn)行搜索遍歷，可分解算法為從某個頂點出發(fā)進(jìn)行搜索遍歷，有深度優(yōu)先和廣度優(yōu)先兩種方式。

2．圖的遍歷算法

(1)圖的遍歷算法程序?qū)崿F(xiàn)需要如下方法：①從頂點v出發(fā)對全圖進(jìn)行深度優(yōu)先搜索遍歷depthFirstSeardchGraph(intv)。②從頂點vi開始出發(fā)的一次深度優(yōu)先搜索遍歷depthFirstSearchVi(intv,boolean[]visited)。③從頂點v出發(fā)對全圖進(jìn)行廣度優(yōu)先搜索遍歷breadthFirstSearchGraph(intv)。④從頂點vi出發(fā)的一次廣度優(yōu)先搜索遍歷breadthFirstSearchVi(intv,boolean[]visited)。

(2)上述四個方法中需要獲得圖的信息：頂點的個數(shù)、頂點vi的數(shù)據(jù)域、頂點vi的第一個鄰接頂點的序號、vi在vj后的下一個鄰接頂點的序號等四個算法。而鄰接矩陣表示和鄰接表表示采用的存儲方式不同，所以實現(xiàn)的方法也不同。這四個方法聲明為抽象方法，由鄰接矩陣表示和鄰接表表示的子類繼承該類時，進(jìn)行覆蓋(override)。

3．圖的抽象類MapAbstract.java完整代碼

packagech6Map;

importjava.util.ArrayList;

importjava.util.List;

//圖的抽象類，深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷

publicabstractclassMapAbstract<E>{

//下面定義四個抽象方法，由繼承的子類具體實現(xiàn)

publicabstractintvertexCount(); //返回頂點數(shù)

publicabstractEget(inti); //返回頂點vi的數(shù)據(jù)域

//返回頂點vi的第一個鄰接頂點的序號

publicabstractintgetFirstNeighbor(inti);//返回vi在vj后的下一個鄰接頂點的序號

publicabstractintgetNextNeighbor(inti,intj);//從頂點v出發(fā)對全圖進(jìn)行深度優(yōu)先搜索遍歷

publicvoiddepthFirstSeardchGraph(intv){//訪問標(biāo)記數(shù)組，元素初值為false，表示未被訪問

boolean[]visited=newboolean[vertexCount()];

inti=v;do{if(!visited[i]){ //若頂點vi未被訪問

System.out.print("{");//從頂點vi出發(fā)的一次深度優(yōu)先搜索遍歷

depthFirstSearchVi(i,visited);System.out.print("}");}i=(i+1)%vertexCount(); //在其他連通分量中尋找未被訪問頂點

}while(i!=v);System.out.println();}

//從頂點vi開始出發(fā)的一次深度優(yōu)先搜索遍歷，遍歷一個連通分量

privatevoiddepthFirstSearchVi(intv,boolean[]visited){System.out.print(this.get(v)+""); //訪問該頂點

visited[v]=true; //置已訪問標(biāo)記

intw=getFirstNeighbor(v); //獲得第一個鄰接頂點

while(w!=-1){ //若存在鄰接頂點

if(!visited[w]){ //若鄰接頂點w未被訪問

//從w出發(fā)的深度優(yōu)先搜索遍歷，遞歸調(diào)用

depthFirstSearchVi(w,visited);}w=getNextNeighbor(v,w);//返回v在w后的下一個鄰接頂點的序號

}}//從頂點v出發(fā)全圖進(jìn)行廣度優(yōu)先搜索遍歷

publicvoidbreadthFirstSearchGraph(intv){boolean[]visited=newboolean[vertexCount()];//訪問標(biāo)記數(shù)組

inti=v;do{if(!visited[i]){//若頂點vi未被訪問

System.out.print("{");//從頂點vi出發(fā)的一次廣度優(yōu)先搜索遍歷

breadthFirstSearchVi(i,visited);System.out.print("}");}i=(i+1)%vertexCount(); //在其他連通分量中尋找未被訪問的頂點

}while(i!=v);System.out.println();}//從頂點vi出發(fā)的一次廣度優(yōu)先搜索遍歷，遍歷一個連通分量

privatevoidbreadthFirstSearchVi(intv,boolean[]visited){System.out.print(this.get(v)+"");visited[v]=true;List<Integer>que=newArrayList<Integer>(vertexCount()); //創(chuàng)建順序隊列

que.add(v); //訪問過的頂點v的序號入隊

while(!que.isEmpty()){ //當(dāng)隊列不為空時循環(huán)

v=que.remove(0); //出隊

intw=getFirstNeighbor(v); //獲得頂點v的第一個鄰接頂點序號

while(w!=-1){ //當(dāng)鄰接頂點存在時循環(huán)

if(!visited[w]){ //若該頂點未訪問過

System.out.print(this.get(w)+"");//訪問頂點

visited[w]=true;que.add(w); //訪問過的頂點w的序號入隊

}w=getNextNeighbor(v,w); //返回v在w后的下一個鄰接頂點的序號

}}}}6.5.2子任務(wù)2程序?qū)崿F(xiàn)圖的鄰接矩陣表示圖的鄰接矩陣表示方法中，矩陣的行列分別是對應(yīng)頂點的編號，行列的值就是對應(yīng)頂點邊的權(quán)重值，所以要定義一個邊類(起點，終點，權(quán)重值)；鄰接矩陣程序中，在覆蓋圖抽象類中MapAbstract.java四個抽象方法后，接著編寫插入及刪除頂點、插入及刪除邊、最小生成樹的Prim算法、最短路徑的Dijkstra算法等程序?qū)崿F(xiàn)。

1．定義邊

(1)在ch6Map包中創(chuàng)建Edge.java文件，聲明邊的起點序號start、邊的終點序號dest、邊的權(quán)值weight，這三個成員屬性均為私有(private)，并自動構(gòu)造getter()和setter()方法；接著覆蓋系統(tǒng)的toString()和compareTo()方法。

(2)邊的Edge.java完整代碼如下：

packagech6Map;

//鄰接矩陣表示帶權(quán)圖的邊,也適合不帶權(quán)(有路徑的權(quán)置為1即可)

publicclassEdgeimplementsComparable<Edge>{

privateintstart; //邊的起點序號

privateintdest; //邊的終點序號

privateintweight; //邊的權(quán)值

publicEdge(intstart,intdest,intweight){ //帶參構(gòu)造函數(shù)

this.start=start;

this.dest=dest;

this.weight=weight;

}@Override //覆蓋方法toString()publicStringtoString(){Stringw="∞";if(getWeight()!=Integer.MAX_VALUE){w=""+getWeight();}return"("+getStart()+","+getDest()+","+w+")";}@Override//覆蓋方法compareTo(),約定比較兩條邊大小的規(guī)則

publicintcompareTo(Edgee){if(this.getStart()!=e.getStart()){returnthis.getStart()-e.getStart();}else{returnthis.getDest()-e.getDest();}}

//返回起點

publicintgetStart(){returnstart;}//設(shè)置起點

publicvoidsetStart(intstart){this.start=start;}//返回終點

publicintgetDest(){returndest;}//設(shè)置終點

publicvoidsetDest(intdest){this.dest=dest;}//返回權(quán)重值

publicintgetWeight(){returnweight;}//設(shè)置權(quán)重值

publicvoidsetWeight(intweight){this.weight=weight;}}

2．鄰接矩陣表示的程序?qū)崿F(xiàn)

(1)在ch6Map包中創(chuàng)建MapMatrix.java文件。覆蓋四個抽象方法，返回頂點數(shù)vertexCount()、頂點vi的數(shù)據(jù)域get(inti)、頂點vi的第一個鄰接頂點的序號getFirstNeighbor(inti)、vi在vj后的下一個鄰接頂點的序號getNext-Neighbor(inti,intj)。編寫插入頂點insertVertex()及刪除頂點removeVertex()、插入邊insertEdge()及刪除邊removeEdge()、最小生成樹的Prim算法、最短路徑的Dijkstra算法等程序?qū)崿F(xiàn)。

(2)圖的MapMatrix.java完整代碼如下：

packagech6Map;

importjava.util.ArrayList;

importjava.util.List;

//鄰接矩陣表示的圖類，繼承抽象圖類AbstractGraph

publicclassMapMatrix<E>extendsMapAbstract<E>{

privateList<E>vertexlist; //順序表存儲圖的頂點集合

privateint[][]adjmatrix; //圖的鄰接矩陣

privatefinalintMAX_WEIGHT=Integer.MAX_VALUE; //最大權(quán)值(表示無窮大∞)//構(gòu)造方法，n指定最多頂點數(shù)

publicMapMatrix(intn){this.vertexlist=newArrayList<E>(n); //構(gòu)造指定容量的空表

this.adjmatrix=newint[n][n]; //構(gòu)造n行n列的空矩陣

for(inti=0;i<n;i++) //初始化圖的鄰接矩陣

{//邊的初始權(quán)值；頂點到自己的權(quán)值為0，到其他頂點為最大權(quán)值(無窮大∞)for(intj=0;j<n;j++){this.adjmatrix[i][j]=(i==j)?0:MAX_WEIGHT;}}}//以頂點集合和邊集合構(gòu)造一個圖

publicMapMatrix(E[]vertices,Edge[]edges){this(vertices.length);for(inti=0;i<vertices.length;i++){insertVertex(vertices[i]); //插入一個頂點

}for(intj=0;j<edges.length;j++){insertEdge(edges[j]); //插入一條邊

}}//以頂點集合和邊集合構(gòu)造一個圖

publicMapMatrix(List<E>list,Edge[]edges){this(list.size()); //list的容量

this.vertexlist=list;for(intj=0;j<edges.length;j++){insertEdge(edges[j]); //插入一條邊

}}@Override //返回頂點數(shù)

publicintvertexCount(){returnthis.vertexlist.size(); //返回頂點順序表的元素個數(shù)

}@Override //返回頂點vi的數(shù)據(jù)元素

publicEget(inti){returnthis.vertexlist.get(i);}//插入一個頂點，若插入成功，則返回trueprivatebooleaninsertVertex(Evertex){//在順序表最后插入一個元素，并返回

returnthis.vertexlist.add(vertex);}//插入一條給定頂點vi到vj(i、j指定頂點序號)、權(quán)值為weight的邊(方法重載)publicbooleaninsertEdge(inti,intj,intweight){//若該邊已存在，則不插入

if(i>=0&&i<vertexCount()&&j>=0&&j<vertexCount()&&i!=j&&adjmatrix[i][j]==MAX_WEIGHT){this.adjmatrix[i][j]=weight;returntrue;}returnfalse;}//插入一條給定的邊(方法重載)privatebooleaninsertEdge(Edgeedge){if(edge!=null){returninsertEdge(edge.getStart(),edge.getDest(),edge.getWeight());}returnfalse;}@Override//輸出鄰接矩陣(邊<vi,vj>權(quán)重)publicStringtoString(){Stringstr="頂點集合："+vertexlist.toString()+"\n";str+="鄰接矩陣:\n";intn=vertexCount(); //頂點數(shù)for(inti=0;i<n;i++){for(intj=0;j<n;j++){if(adjmatrix[i][j]==MAX_WEIGHT){str+="∞";}else{str+=""+adjmatrix[i][j];}}str+="\n";}returnstr;}//刪除邊〈vi,vj〉，i、j指定頂點序號

publicbooleanremoveEdge(inti,intj){//若刪除成功，則返回trueif(i>=0&&i<vertexCount()&&j>=0&&j<vertexCount()&&i!=j&&this.adjmatrix[i][j]!=MAX_WEIGHT){this.adjmatrix[i][j]=MAX_WEIGHT;//設(shè)置該邊的權(quán)值為無窮大

returntrue;}returnfalse;}//刪除序號為v的頂點及其關(guān)聯(lián)的邊

publicbooleanremoveVertex(intv){//若刪除成功，則返回trueintn=vertexCount(); //刪除之前的頂點數(shù)

if(v>=0&&v<n){//刪除順序表的第i個元素，頂點數(shù)已減一

this.vertexlist.remove(v);for(inti=v;i<n-1;i++){System.arraycopy(this.adjmatrix[i+1],0,this.adjmatrix[i],0,n);//上行arraycopy是系統(tǒng)復(fù)制數(shù)組方法，相當(dāng)于下面循環(huán)//for(intj=0;j<n;j++){//this.adjmatrix[i][j]=this.adjmatrix[i+1][j];//}}for(intj=v;j<n-1;j++){for(inti=0;i<n-1;i++){//元素向前一列移動

this.adjmatrix[i][j]=this.adjmatrix[i][j+1];}}returntrue;}returnfalse;}@Override//返回頂點v的第一個鄰接頂點的序號

publicintgetFirstNeighbor(intv){//若不存在第一個鄰接頂點，則返回-1returngetNextNeighbor(v,-1);}@Override//返回v在w后的下一個鄰接頂點的序號

publicintgetNextNeighbor(intv,intw){//若不存在下一個鄰接頂點，則返回-1if(v>=0&&v<vertexCount()&&w>=-1&&w<vertexCount()&&v!=w){//w=-1時，j從0開始尋找下一個鄰接頂點

for(intj=w+1;j<vertexCount();j++){if(adjmatrix[v][j]>0&&adjmatrix[v][j]<MAX_WEIGHT){returnj;}}}return-1;}//構(gòu)造帶權(quán)圖最小生成樹的Prim算法,返回最小生成樹相應(yīng)的圖對象

publicMapMatrixPrim(){//n個頂點最小生成樹有n-1條邊

Edge[]mst=newEdge[vertexCount()-1];//初始化mst數(shù)組，從頂點v0出發(fā)構(gòu)造最小生成樹

for(inti=0;i<mst.length;i++){//保存從頂點v0到其他各頂點的邊的權(quán)

mst[i]=newEdge(0,i+1,adjmatrix[0][i+1]);}System.out.print("mst數(shù)組初值：");//顯示mst數(shù)組的變化過程

for(intj=0;j<mst.length;j++){System.out.print(mst[j].toString());}for(inti=0;i<mst.length;i++){ //共選出n-1條邊

intminweight=MAX_WEIGHT; //求最小權(quán)值

intmin=i;for(intj=i;j<mst.length;j++){//尋找當(dāng)前最小權(quán)值的邊的頂點

if(mst[j].getWeight()<minweight){minweight=mst[j].getWeight(); //更新最小權(quán)值

min=j; //保存當(dāng)前最小權(quán)值邊的終點序號

}}Edgetemp=mst[i]; //交換最小權(quán)值的邊

mst[i]=mst[min];mst[min]=temp;intu=mst[i].getDest(); //剛并入U的頂點

//調(diào)整mst[i+1]及其后元素為權(quán)值最小的邊

for(intj=i+1;j<mst.length;j++){intv=mst[j].getDest(); //原邊在V-U中的終點

//若有權(quán)值更小的邊(u,v)，則用(u,v)邊替換原邊

if(adjmatrix[u][v]<mst[j].getWeight()){mst[j].setWeight(adjmatrix[u][v]);mst[j].setStart(u);}}System.out.print("\nmst數(shù)組：");for(intj=0;j<mst.length;j++){//顯示mst數(shù)組的變化過程

System.out.print(mst[j].toString());}}//構(gòu)造最小生成樹相應(yīng)的圖對象，并返回

returnnewMapMatrix(this.vertexlist,mst);}//輸出table的內(nèi)容

privateStringtoString(int[]table){if(table!=null&&table.length>0){Stringstr="{";for(inti=0;i<table.length-1;i++){str+=table[i]+",";}returnstr+table[table.length-1]+"}";}returnnull;}//以Dijkstra算法求帶權(quán)圖中頂點v的單源最短路徑

publicvoidDijkstra(intv){intn=this.vertexCount(); //頂點個數(shù)

int[]dist=newint[n]; //最短路徑長度

intpath[]=newint[n]; //最短路徑的終點的前一個頂點

int[]s=newint[n];

//已求出最短路徑的頂點集合，初值全為0s[v]=1;

//源點在集合S中的標(biāo)記

for(inti=0;i<n;i++){ //初始化dist和path數(shù)組

dist[i]=this.adjmatrix[v][i];if(i!=v&&dist[i]<MAX_WEIGHT){path[i]=v;}else{path[i]=-1;}}System.out.print("\ns數(shù)組"+toString(s));System.out.print("\tpath數(shù)組"+toString(path));System.out.print("\tdist數(shù)組"+toString(dist));for(inti=1;i<n;i++){//尋找從頂點v到頂點u的最短路徑，u在V-S集合中

intmindist=MAX_WEIGHT,u=0;for(intj=0;j<n;j++){if(s[j]==0&&dist[j]<mindist){u=j;mindist=dist[j];}}s[u]=1; //確定一條最短路徑的終點u并入集合Sfor(intj=0;j<n;j++){//調(diào)整從v到V-S中其他頂點的最短路徑及長度

if(s[j]==0&&this.adjmatrix[u][j]<MAX_WEIGHT&&dist[u]+this.adjmatrix[u][j]<dist[j]){dist[j]=dist[u]+this.adjmatrix[u][j];path[j]=u;}}System.out.print("\ns數(shù)組"+toString(s));System.out.print("\tpath數(shù)組"+toString(path));System.out.print("\tdist數(shù)組"+toString(dist));}System.out.println("\n從頂點"+get(v)+"到其他頂點最短路徑如下：");inti=(v+1)%(this.vertexCount()); //防止最大序號頂點加1而溢出

while(i!=v){intj=i;Stringpathstr="";while(path[j]!=-1){pathstr=","+get(j)+pathstr;j=path[j];}pathstr="("+get(v)+pathstr+")，路徑長度為"+dist[i];System.out.println(pathstr);i=(i+1)%n;}}}6.5.3子任務(wù)3程序?qū)崿F(xiàn)圖的鄰接表表示圖的鄰接表表示需要定義鄰接表頂點、頂點數(shù)據(jù)域、頂點的邊單鏈表。鄰接表表示實現(xiàn)程序中，在覆蓋圖抽象類中MapAbstract.java四個抽象方法后，再實現(xiàn)插入及刪除頂點、插入及刪除邊等。

1．定義頂點類

(1)在ch6Map包中創(chuàng)建鄰接表的頂點類Vertex.java文件，聲明頂點數(shù)據(jù)域data、頂點的邊單鏈表edgeLink，這兩個成員屬性均為私有(private)，并自動構(gòu)造getter()和setter()方法；接著覆蓋系統(tǒng)的toString()方法。(2)頂點類Vertex.java的完整代碼如下：

packagech6Map;

importjava.util.LinkedList;

//圖的鄰接表表示的頂點類

publicclassVertex<E>{

privateEdata;//頂點數(shù)據(jù)域

privateLinkedList<Edge>edgeLink;//該頂點的邊單鏈表

//構(gòu)造方法：頂點及其邊鏈表

publicVertex(Edata,LinkedList<Edge>edgeLink){

this.data=data;//頂點

this.edgeLink=edgeLink;//邊鏈表

}

publicVertex(Edata){//構(gòu)造方法：創(chuàng)建頂點空單鏈表

//構(gòu)造頂點時創(chuàng)建空單鏈表

this(data,newLinkedList<Edge>());

}

@Override

publicStringtoString(){//輸出頂點數(shù)據(jù)

//returnthis.getData().toString();

Stringtemp=this.getData().toString().trim();

if(Integer.parseInt(temp)==Integer.MAX_VALUE){

temp=