數(shù)據(jù)結(jié)構(gòu)的第八講課件

1引言現(xiàn)實(shí)世界存在許多不同類(lèi)型的模擬系統(tǒng)。例如：交通流量就是其中一個(gè)實(shí)例。頂點(diǎn)表示街道的十字路口，同時(shí)邊表示街道本身。加權(quán)邊可以用來(lái)表示車(chē)速限制或者車(chē)道數(shù)量。模型可以使用系統(tǒng)來(lái)確定最佳路線(xiàn)和可能遭受交通堵塞的街道。每一個(gè)飛機(jī)場(chǎng)就是一個(gè)頂點(diǎn)，而從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的航線(xiàn)就是一條邊。加權(quán)的邊可以表示從一個(gè)機(jī)場(chǎng)到另一個(gè)機(jī)場(chǎng)飛行的費(fèi)用，或者表示從一個(gè)機(jī)場(chǎng)到另一個(gè)機(jī)場(chǎng)的大概距離，這取決于模擬的內(nèi)容。

由圖模擬真實(shí)世界系統(tǒng)第八講圖和圖的算法主要內(nèi)容8.1圖的定義8.2圖的存儲(chǔ)表示8.3圖的第一個(gè)應(yīng)用：拓?fù)渑判?.4圖的搜索8.5最小生成樹(shù)8.6查找最短路徑

5圖的定義圖是由頂點(diǎn)集合(vertex)及頂點(diǎn)間的關(guān)系集合組成的一種數(shù)據(jù)結(jié)構(gòu)：Graph＝(V,E)

其中：V={vi|vi

某個(gè)數(shù)據(jù)對(duì)象}是頂點(diǎn)的有窮非空集合；E={(vi,vj)|vi,vj

V}或

E={<vi,vj>|vi,vj

V&&Path(vi,vj)}

是頂點(diǎn)之間關(guān)系的有窮集合，也叫做邊(edge)集合。

Path(vi,vj)表示從vi到vj的一條單向通路,它是有方向的。0213圖是由一組頂點(diǎn)和一組邊構(gòu)成的6圖的定義無(wú)向圖:

(vi,vj)=(vj,vi)同一條邊.有向圖:

<

vi,vj>::=<vj,vi>不同邊vivjtailhead7圖的定義vivjvi

和vj

是互為鄰接頂點(diǎn);(vi,vj)依附于vi

和vj

vivjvi

鄰接到vj

;vj

鄰接自vi

;<vi,vj>相關(guān)聯(lián)于viandvj

子圖G’G:

V(G’)V(G)&&E(G’)E(G)

0123子圖01301230239圖的定義路徑的長(zhǎng)度：從路徑中第一個(gè)頂點(diǎn)到最后一個(gè)頂點(diǎn)的邊的數(shù)量。

討論的圖對(duì)象的限制:

(1)自身環(huán)不討論.(2)與兩個(gè)特定頂點(diǎn)相關(guān)聯(lián)的邊不能多于一條，多重圖也不討論。0101210圖的定義簡(jiǎn)單路徑：

若路徑上各頂點(diǎn)v1,v2,...,vm均不互相重復(fù),則稱(chēng)這樣的路徑為簡(jiǎn)單路徑?；芈罚?/p>

若路徑上第一個(gè)頂點(diǎn)v1與最后一個(gè)頂點(diǎn)vm重合,則稱(chēng)這樣的路徑為回路或環(huán)（loop）。

環(huán)的長(zhǎng)度為0。在有向圖中路徑至少為1以便于初始定點(diǎn)也是結(jié)束定點(diǎn)。

在有向圖中，邊可能是相同的，但是在無(wú)向圖中，邊必須是不同的。11圖的定義權(quán)：

某些圖的邊具有與它相關(guān)的數(shù)值,稱(chēng)之為權(quán)。這種帶權(quán)圖叫做網(wǎng)絡(luò)。代價(jià)：

頂點(diǎn)還可以有權(quán)值，被稱(chēng)為代價(jià)。13圖的定義vID(v)=3OD(v)=1TD(v)=4注意

圖G有n個(gè)頂點(diǎn)和e條邊,那么14圖的定義路徑長(zhǎng)度：

非帶權(quán)圖的路徑長(zhǎng)度是指此路徑上邊的條數(shù)。

帶權(quán)圖的路徑長(zhǎng)度是指路徑上各邊的權(quán)之和。ABECF從A到F長(zhǎng)度為3的路徑{A,B,C,F}15圖的定義連通圖與連通分量：

在無(wú)向圖中,若從頂點(diǎn)v1到頂點(diǎn)v2有路徑,則稱(chēng)頂點(diǎn)v1與v2是連通的。如果圖中任意一對(duì)頂點(diǎn)都是連通的,則稱(chēng)此圖是連通圖。非連通圖的極大連通子圖叫做連通分量。強(qiáng)連通圖與強(qiáng)連通分量：

在有向圖中,若對(duì)于每一對(duì)頂點(diǎn)vi和vj,都存在一條從vi到vj和從vj到vi的路徑,則稱(chēng)此圖是強(qiáng)連通圖。非強(qiáng)連通圖的極大強(qiáng)連通子圖叫做強(qiáng)連通分量。17圖的定義有向圖，若任意兩個(gè)頂點(diǎn)之間都存在一條有向路徑，則稱(chēng)此有向圖為強(qiáng)連通圖。否則，其各個(gè)強(qiáng)連通子圖稱(chēng)作它的強(qiáng)連通分量。ABECFABECF18圖的定義如果存在從任意頂點(diǎn)到其他任意頂點(diǎn)的路徑，就認(rèn)為無(wú)向圖是連通的（connected）在有向圖中，這個(gè)條件被稱(chēng)為是強(qiáng)連通（stronglyconnected）如果有向圖不是強(qiáng)連通的，但是又認(rèn)為連通了，這就被稱(chēng)為弱連通（weaklyconnected）

19圖的定義完全圖:邊數(shù)最大的圖02130213每組頂點(diǎn)之間都有邊21圖的定義有n個(gè)頂點(diǎn)，n-1條邊的圖必定是生成樹(shù)嗎？對(duì)非連通圖，則稱(chēng)由各個(gè)連通分量的生成樹(shù)的集合為此非連通圖的生成森林。BACDFEBACDFE主要內(nèi)容8.1圖的定義8.2圖的存儲(chǔ)表示8.3圖的第一個(gè)應(yīng)用：拓?fù)渑判?.4圖的搜索8.5最小生成樹(shù)8.6查找最短路徑

8.2圖的存儲(chǔ)表示25鄰接矩陣舉例0123G101230123分析1：

無(wú)向圖的鄰接矩陣是對(duì)稱(chēng)的；分析2：

頂點(diǎn)i

的度＝第i

行(列)中1的個(gè)數(shù)；特別：

完全圖的鄰接矩陣中，對(duì)角元素為0，其余全1。26鄰接矩陣舉例012G2012012注：在有向圖的鄰接矩陣中，第i行含義：以結(jié)點(diǎn)vi為尾的弧(即出度邊）；第j列含義：以結(jié)點(diǎn)vj為頭的弧(即入度邊）。29頂點(diǎn)的表示要開(kāi)始構(gòu)造Graph類(lèi)的第一步是構(gòu)造存儲(chǔ)圖內(nèi)頂點(diǎn)的Vertex類(lèi)。這個(gè)類(lèi)與LinkedList類(lèi)和BinarySearchTree類(lèi)中的Node類(lèi)具有相同的功效。Vertex類(lèi)需要兩個(gè)數(shù)據(jù)成員：一個(gè)用來(lái)識(shí)別頂點(diǎn)數(shù)據(jù)一個(gè)布爾型成員則用來(lái)跟蹤頂點(diǎn)的“訪(fǎng)問(wèn)”30頂點(diǎn)的表示這兩種數(shù)據(jù)成員分別命名為L(zhǎng)abelwasVisited此類(lèi)需要的唯一方法就是允許設(shè)置數(shù)據(jù)成員label和wasVisited的構(gòu)造器方法。在這個(gè)實(shí)現(xiàn)中將不使用默認(rèn)的構(gòu)造器，這是因?yàn)槊看伍_(kāi)始引用頂點(diǎn)對(duì)象時(shí)都會(huì)進(jìn)行一次實(shí)例化操作。頂點(diǎn)列表會(huì)存儲(chǔ)在數(shù)組內(nèi)，而且在Graph類(lèi)中會(huì)通過(guò)它們?cè)跀?shù)組內(nèi)的位置對(duì)其進(jìn)行引用。31邊的表示邊描述了圖的結(jié)構(gòu)，所以關(guān)于圖的真實(shí)信息是存儲(chǔ)在邊內(nèi)的。選擇用來(lái)表示圖中邊的方法稱(chēng)為是鄰接矩陣。鄰接矩陣是一個(gè)二維數(shù)組，數(shù)組內(nèi)的元素表示了兩個(gè)頂點(diǎn)之間是否存在邊。把頂點(diǎn)作為矩陣內(nèi)行和列的標(biāo)頭羅列出來(lái)。如果在兩個(gè)頂點(diǎn)之間存在一條邊，那么就把1放在這個(gè)位置上。如果邊不存在，那么就賦值為0。很顯然這里也可以使用布爾型的數(shù)值。32圖的構(gòu)造有了表示頂點(diǎn)和邊的方法，接下來(lái)就準(zhǔn)備構(gòu)造圖了。首先，需要建立一個(gè)圖中頂點(diǎn)的列表。最后，需要添加連接頂點(diǎn)的邊。33Graph類(lèi)的初步定義構(gòu)造器方法重新構(gòu)建了頂點(diǎn)數(shù)組和在常量NUM-VERTICES中指定數(shù)值的鄰接矩陣。既然數(shù)組是基于零的，所以數(shù)據(jù)成員numVerts存儲(chǔ)著頂點(diǎn)列表內(nèi)當(dāng)前的數(shù)量以便于把列表初始設(shè)置為0。AddVertex方法會(huì)為頂點(diǎn)標(biāo)簽取走一個(gè)字符串參數(shù)，實(shí)例化一個(gè)新的Vertex對(duì)象，并且把它添加到頂點(diǎn)數(shù)組內(nèi)。AddEdge方法則會(huì)取走兩個(gè)整型值參數(shù)。這些整數(shù)表示頂點(diǎn)，并且說(shuō)明在它們之間存在一條邊。showVertex方法會(huì)顯示出指定頂點(diǎn)的標(biāo)簽。34鄰接表(AdjacencyList)鄰接表:是圖的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。邊的結(jié)點(diǎn)結(jié)構(gòu)

adjvex;//該邊所指向的頂點(diǎn)的位置

nextarc;//指向下一條邊指針

info;//該邊相關(guān)信息的指針35鄰接表(AdjacencyList)頂點(diǎn)的結(jié)點(diǎn)結(jié)構(gòu)data;//頂點(diǎn)信息firstarc;//指向第一條依附該頂點(diǎn)的邊adjvexnextarcinfodatafirstarc36無(wú)向圖的鄰接表

同一個(gè)頂點(diǎn)發(fā)出的邊鏈接在同一個(gè)邊鏈表中，每一個(gè)鏈結(jié)點(diǎn)代表一條邊(邊結(jié)點(diǎn)),結(jié)點(diǎn)中有另一頂點(diǎn)的下標(biāo)dest和指針link。ABCDdataadjABCD0123destlink32destlink101037有向圖的鄰接表和逆鄰接表ABC鄰接表(出邊表)逆鄰接表(入邊表)dataadjABC012destlinkdestlink102dataadjABC012destlink01138網(wǎng)絡(luò)(帶權(quán)圖)的鄰接表BACD69528dataadjABCD0123destcostlink1

53

62

83

21

9(出邊表)(頂點(diǎn)表)39鄰接表存儲(chǔ)法的特點(diǎn)它其實(shí)是對(duì)鄰接矩陣法的一種改進(jìn)分析1:對(duì)于n個(gè)頂點(diǎn)e條邊的無(wú)向圖，鄰接表中除了n個(gè)頭結(jié)點(diǎn)外，只有2e個(gè)表結(jié)點(diǎn),空間效率為O(n+2e)。若是稀疏圖(e<<n2)，則比鄰接矩陣表示法O(n2)省空間。分析2:在有向圖中，鄰接表中除了n個(gè)頭結(jié)點(diǎn)外，只有e個(gè)表結(jié)點(diǎn),空間效率為O(n+e)。若是稀疏圖，則比鄰接矩陣表示法合適。40鄰接表度的計(jì)算怎樣計(jì)算無(wú)向圖頂點(diǎn)的度？TD(Vi)=單鏈表中鏈接的結(jié)點(diǎn)個(gè)數(shù)怎樣計(jì)算有向圖頂點(diǎn)的出度？怎樣計(jì)算有向圖頂點(diǎn)的入度？怎樣計(jì)算有向圖頂點(diǎn)Vi的度：OD(Vi)＝單鏈出邊表中鏈接的結(jié)點(diǎn)數(shù)ID(Vi)＝鄰接點(diǎn)為Vi的邊個(gè)數(shù)TD(Vi)=OD(Vi)+ID(Vi)41鄰接表的優(yōu)缺點(diǎn)鄰接表的缺點(diǎn)：鄰接表的優(yōu)點(diǎn)：空間效率高；容易尋找頂點(diǎn)的鄰接點(diǎn)；判斷兩頂點(diǎn)間是否有邊或弧，需搜索兩結(jié)點(diǎn)對(duì)應(yīng)的單鏈表，沒(méi)有鄰接矩陣方便。42鄰接表與鄰接矩陣有什么異同之處1.聯(lián)系：鄰接表中每個(gè)鏈表對(duì)應(yīng)于鄰接矩陣中的一行，鏈表中結(jié)點(diǎn)個(gè)數(shù)等于一行中非零元素的個(gè)數(shù)。2.區(qū)別：

①對(duì)于任一確定的無(wú)向圖，鄰接矩陣是唯一的（行列號(hào)與頂點(diǎn)編號(hào)一致），但鄰接表不唯一（鏈接次序與頂點(diǎn)編號(hào)無(wú)關(guān)）。②鄰接矩陣的空間復(fù)雜度為O(n2),而鄰接表的空間復(fù)雜度為O(n+e)。3.用途：鄰接矩陣多用于稠密圖的存儲(chǔ)（e接近n(n-1)/2)；鄰接表多用于稀疏圖的存儲(chǔ)（e<<n2)主要內(nèi)容8.1圖的定義8.2圖的存儲(chǔ)表示8.3圖的第一個(gè)應(yīng)用：拓?fù)渑判?.4圖的搜索8.5最小生成樹(shù)8.6查找最短路徑

8.3圖的第一個(gè)應(yīng)用：拓?fù)渑判?5活動(dòng)網(wǎng)絡(luò)(ActivityNetwork)計(jì)劃、施工過(guò)程、生產(chǎn)流程、程序流程等都是“工程”。除了很小的工程外，一般都把工程分為若干個(gè)叫做“活動(dòng)”的子工程。完成了這些活動(dòng)，這個(gè)工程就可以完成了。例如，計(jì)算機(jī)專(zhuān)業(yè)學(xué)生的學(xué)習(xí)就是一個(gè)工程，每一門(mén)課程的學(xué)習(xí)就是整個(gè)工程的一些活動(dòng)。其中有些課程要求先修課程，有些則不要求。這樣在有的課程之間有領(lǐng)先關(guān)系，有的課程可以并行地學(xué)習(xí)。用頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)(AOV網(wǎng)絡(luò))46舉例

C1

高等數(shù)學(xué)

C2

程序設(shè)計(jì)基礎(chǔ)

C3

離散數(shù)學(xué)C1,C2

C4

數(shù)據(jù)結(jié)構(gòu)C3,C2C5

高級(jí)語(yǔ)言程序設(shè)計(jì)C2C6

編譯方法C5,C4C7

操作系統(tǒng)C4,C9C8

普通物理C1C9

計(jì)算機(jī)原理C8

課程代號(hào)課程名稱(chēng)先修課程47建圖學(xué)生課程學(xué)習(xí)工程圖C8C3C5C4C9C6C7C1C248AOV網(wǎng)絡(luò)用有向圖表示一個(gè)工程。在這種有向圖中，用頂點(diǎn)表示活動(dòng)，用有向邊<Vi,Vj>表示活動(dòng)Vi必須先于活動(dòng)Vj進(jìn)行。這種有向圖叫做頂點(diǎn)表示活動(dòng)的AOV網(wǎng)絡(luò)

(ActivityOnVertices)。在AOV網(wǎng)絡(luò)中不能出現(xiàn)有向回路,即有向環(huán)。如果出現(xiàn)了有向環(huán)，則意味著某項(xiàng)活動(dòng)應(yīng)以自己作為先決條件。對(duì)給定的AOV網(wǎng)絡(luò)，必須先判斷它是否存在有向環(huán)。49拓?fù)渑判驒z測(cè)有向環(huán)的一種方法是對(duì)AOV網(wǎng)絡(luò)構(gòu)造它的拓?fù)溆行蛐蛄?。即將各個(gè)頂點(diǎn)(代表各個(gè)活動(dòng))排列成一個(gè)線(xiàn)性有序的序列，使得AOV網(wǎng)絡(luò)中所有應(yīng)存在的前驅(qū)和后繼關(guān)系都能得到滿(mǎn)足。這種構(gòu)造AOV網(wǎng)絡(luò)全部頂點(diǎn)的拓?fù)溆行蛐蛄械倪\(yùn)算就叫做拓?fù)渑判?。如果通過(guò)拓?fù)渑判蚰軐OV網(wǎng)絡(luò)的所有頂點(diǎn)都排入一個(gè)拓?fù)溆行虻男蛄兄?則該網(wǎng)絡(luò)中必定不會(huì)出現(xiàn)有向環(huán)。50拓?fù)渑判蛉绻鸄OV網(wǎng)絡(luò)中存在有向環(huán)，此AOV網(wǎng)絡(luò)所代表的工程是不可行的。例如,對(duì)學(xué)生選課工程圖進(jìn)行拓?fù)渑判?得到的拓?fù)溆行蛐蛄袨?/p>

C1,C2,C3,C4,C5,C6,C8,C9,C7

或C1,C8,C9,C2,C5,C3,C4,C7,C6C8C3C5C4C9C6C7C1C251拓?fù)渑判虻姆椒á?/p>

輸入AOV網(wǎng)絡(luò)。令n為頂點(diǎn)個(gè)數(shù)。 ②在AOV網(wǎng)絡(luò)中選一個(gè)沒(méi)有直接前驅(qū)的頂點(diǎn),并輸出之;③從圖中刪去該頂點(diǎn),同時(shí)刪去所有它發(fā)出的有向邊;④重復(fù)以上②、③步,直到全部頂點(diǎn)均已輸出，拓?fù)溆行蛐蛄行纬?，拓?fù)渑判蛲瓿桑换驁D中還有未輸出的頂點(diǎn),但已跳出處理循環(huán)。說(shuō)明圖中還剩下一些頂點(diǎn),它們都有直接前驅(qū)。這時(shí)網(wǎng)絡(luò)中必存在有向環(huán)。52C0C1C2C3C4C5(a)有向無(wú)環(huán)圖C2C5C1C0C3(b)輸出頂點(diǎn)C4C4C1C2C5C3(c)輸出頂點(diǎn)C0C0C2C5C1C3(d)輸出頂點(diǎn)C3拓?fù)渑判虻倪^(guò)程53C1C2C5(e)輸出頂點(diǎn)C2C5C1(f)輸出頂點(diǎn)C1C5(g)輸出頂點(diǎn)C5

最后得到的拓?fù)溆行蛐蛄袨镃4,C0,C3,C2,C1,C5

。它滿(mǎn)足圖中給出的所有前驅(qū)和后繼關(guān)系，對(duì)于本來(lái)沒(méi)有這種關(guān)系的頂點(diǎn)，如C4和C2，也排出了先后次序關(guān)系。(h)拓?fù)渑判蛲瓿赏負(fù)渑判虻倪^(guò)程54C0C1C2C3C4C5

C0C1C2C30C4C50012345countdataadj

130103

1

destlink

30

5

1

50

0

1

50AOV網(wǎng)絡(luò)及其鄰接表表示55拓?fù)渑判蛩惴ㄊ褂靡粋€(gè)存放入度為零的頂點(diǎn)的鏈?zhǔn)綏?供選擇和輸出無(wú)前驅(qū)的頂點(diǎn)。拓?fù)渑判蛩惴擅枋鋈缦拢航⑷攵葹榱愕捻旤c(diǎn)棧;當(dāng)入度為零的頂點(diǎn)棧不空時(shí),重復(fù)執(zhí)行

從頂點(diǎn)棧中退出一個(gè)頂點(diǎn),并輸出之;

從AOV網(wǎng)絡(luò)中刪去這個(gè)頂點(diǎn)和它發(fā)出的邊,邊的終頂點(diǎn)入度減一;

如果邊的終頂點(diǎn)入度減至0,則該頂點(diǎn)進(jìn)入度為零的頂點(diǎn)棧;

如果輸出頂點(diǎn)個(gè)數(shù)少于AOV網(wǎng)絡(luò)的頂點(diǎn)個(gè)數(shù),則報(bào)告網(wǎng)絡(luò)中存在有向環(huán)。56拓?fù)渑判蛩惴?.找到一個(gè)沒(méi)有后繼頂點(diǎn)的頂點(diǎn)。2.把此頂點(diǎn)添加到頂點(diǎn)列表內(nèi)。3.從圖中移除掉此頂點(diǎn)。4.重復(fù)步驟1直到把所有頂點(diǎn)從圖中移除掉。在實(shí)現(xiàn)的細(xì)節(jié)上存在挑戰(zhàn)，但這正是拓?fù)渑判虻年P(guān)鍵所在。57拓?fù)渑判蛩惴ǖ膶?shí)現(xiàn)拓?fù)渑判蛐枰獌蓚€(gè)方法。一個(gè)方法用來(lái)確定頂點(diǎn)是否有后繼頂點(diǎn)另一方法則是把頂點(diǎn)從圖中刪除下面先來(lái)看看確定沒(méi)有后繼頂點(diǎn)的方法。在鄰接矩陣中可以找到?jīng)]有后繼的頂點(diǎn)，這種頂點(diǎn)所在行對(duì)應(yīng)的所有列都為零。方法會(huì)用嵌套的for循環(huán)來(lái)逐行檢查每組列的內(nèi)容。如果在某列發(fā)現(xiàn)1，就跳出內(nèi)部循環(huán)，并對(duì)下一行進(jìn)行檢查。如果找到一行對(duì)應(yīng)的所有列都為零，那么返回這個(gè)行號(hào)。如果兩層循環(huán)結(jié)束且沒(méi)有行號(hào)返回，那么返回-1，這表示不存在無(wú)后繼的頂點(diǎn)。58拓?fù)渑判蛩惴ǖ膶?shí)現(xiàn)接下來(lái)需要明白如何從圖中移除頂點(diǎn)。需要做的第一件事就是從頂點(diǎn)列表中移除掉該頂點(diǎn)。這是很容易的。然后，就需要從鄰接矩陣中移除掉相應(yīng)的行和列，同時(shí)還要把移除行上面的行向下移動(dòng)并且把移除列右側(cè)的列向左移動(dòng)，以此來(lái)填充移除頂點(diǎn)留下的行和列的空白。為了實(shí)現(xiàn)這個(gè)操作，這里編寫(xiě)了名為delVertex的方法，它包括兩個(gè)助手方法moveRow和moveCol

59拓?fù)渑判蛩惴ǖ膶?shí)現(xiàn)需要一個(gè)TopSort方法來(lái)控制排序的過(guò)程。

TopSort方法循環(huán)遍歷圖內(nèi)頂點(diǎn)，找到一個(gè)無(wú)后繼的頂點(diǎn)就把它刪除，然后再移動(dòng)到下一個(gè)頂點(diǎn)上。每次刪除頂點(diǎn)時(shí)，會(huì)把它的標(biāo)簽壓進(jìn)一個(gè)棧內(nèi)。棧是一種使用便利的數(shù)據(jù)結(jié)構(gòu)，因?yàn)檎业降谝粋€(gè)頂點(diǎn)實(shí)際上就是圖內(nèi)的最后一個(gè)頂點(diǎn)（或者是最后中的一個(gè)）。當(dāng)TopSort方法運(yùn)行完成的時(shí)候，棧內(nèi)的內(nèi)容將包括壓入棧底的最后一個(gè)頂點(diǎn)和在棧頂?shù)膱D的第一個(gè)頂點(diǎn)。這時(shí)只需要循環(huán)遍歷棧來(lái)彈出每個(gè)元素進(jìn)行顯示就是圖的正確拓?fù)漤樞蛄恕Ｖ饕獌?nèi)容8.1圖的定義8.2圖的存儲(chǔ)表示8.3圖的第一個(gè)應(yīng)用：拓?fù)渑判?.4圖的搜索8.5最小生成樹(shù)8.6查找最短路徑

8.4圖的搜索62引言圖的搜索是在圖上經(jīng)常執(zhí)行的一種操作，通過(guò)該操作確定從一個(gè)頂點(diǎn)能到達(dá)哪些頂點(diǎn)是。例如：人們可能需要知道在地圖上哪些路可以從一個(gè)城鎮(zhèn)到達(dá)其他城鎮(zhèn)，或者從一個(gè)機(jī)場(chǎng)到其他機(jī)場(chǎng)可以走哪條航線(xiàn)。

在圖上執(zhí)行這些操作都用到了查找算法。圖上可以執(zhí)行兩種基礎(chǔ)查找：深度優(yōu)先（depth-first）搜索廣度優(yōu)先（breadth-first）搜索深度優(yōu)先搜索深度優(yōu)先搜索的含義是沿著一條路徑從開(kāi)始頂點(diǎn)到達(dá)最后的頂點(diǎn)，然后原路返回，并且沿著下一條路徑達(dá)到最后的頂點(diǎn)，如此繼續(xù)直到走過(guò)所有路徑。63深度優(yōu)先搜索算法的工作過(guò)程首先，選取一個(gè)起始點(diǎn)，它可能是任何頂點(diǎn)。訪(fǎng)問(wèn)這個(gè)頂點(diǎn)，把它壓入一個(gè)棧內(nèi)，并且標(biāo)記為已訪(fǎng)問(wèn)的。接著轉(zhuǎn)到下一個(gè)未訪(fǎng)問(wèn)的頂點(diǎn)，也把它壓入棧內(nèi)，并且做好標(biāo)記。繼續(xù)這樣的操作直到到達(dá)最后一個(gè)頂點(diǎn)為止。然后，檢查棧頂?shù)捻旤c(diǎn)是否還有其他未訪(fǎng)問(wèn)的相鄰頂點(diǎn)。如果沒(méi)有，就把它從棧內(nèi)彈出，并且檢查下一個(gè)頂點(diǎn)。如果找到一個(gè)這樣的頂點(diǎn)，那么就開(kāi)始訪(fǎng)問(wèn)相鄰頂點(diǎn)直到?jīng)]有未訪(fǎng)問(wèn)的為止，還要檢查更多未訪(fǎng)問(wèn)的相鄰頂點(diǎn)并且繼續(xù)此過(guò)程。當(dāng)最終到達(dá)棧內(nèi)最后一個(gè)頂點(diǎn)并且沒(méi)有相鄰的未訪(fǎng)問(wèn)頂點(diǎn)的時(shí)候，才算完成深度優(yōu)先搜索。64深度優(yōu)先搜索65算法DFS輸入：有向或無(wú)向圖G=(V,E)輸出：深度優(yōu)先遍歷序列Step1.predfn=0;postdfn=0;Step2.for每個(gè)頂點(diǎn)vV

標(biāo)記v未訪(fǎng)問(wèn)

endforStep3.for每個(gè)頂點(diǎn)vVifv未訪(fǎng)問(wèn)thendfs(v)endfor0123456dfs(0)Tp=O(n+e)(鄰接表)Tp=O(n2).(鄰接矩陣)練習(xí)66對(duì)下列非連通圖G進(jìn)行深度優(yōu)先搜索遍歷，得到頂點(diǎn)的訪(fǎng)問(wèn)序列為：

計(jì)算機(jī)如何實(shí)現(xiàn)DFS67123456100000020000003000000400000050000006000000000000123456010000110000111000111010111110111111DFS結(jié)果鄰接矩陣A輔助數(shù)組visited[n]起點(diǎn)v2→v1→v3→v5→v4→v6——開(kāi)輔助數(shù)組visited[n]！例：123456101110021000103100010410000150110006000100在圖的鄰接表中如何進(jìn)行DFS—照樣借用visited[n]！v0→v1→v2→v3DFS結(jié)果00000123輔助數(shù)組visited[n]1000110011101111例：起點(diǎn)0123注意：在鄰接表中，并非每個(gè)鏈表元素（表結(jié)點(diǎn)）都被掃描到,遍歷速度很快。DFS算法效率分析69（設(shè)圖中有n個(gè)頂點(diǎn)，e條邊）如果用鄰接矩陣來(lái)表示圖，遍歷圖中每一個(gè)頂點(diǎn)都要從頭掃描該頂點(diǎn)所在行，因此遍歷全部頂點(diǎn)所需的時(shí)間為O(n2)。如果用鄰接表來(lái)表示圖，雖然有2e

個(gè)表結(jié)點(diǎn)，但只需掃描e個(gè)結(jié)點(diǎn)即可完成遍歷，加上訪(fǎng)問(wèn)n個(gè)頭結(jié)點(diǎn)的時(shí)間，因此遍歷圖的時(shí)間復(fù)雜度為O(n+e)。結(jié)論：稠密圖適于在鄰接矩陣上進(jìn)行深度遍歷；稀疏圖適于在鄰接表上進(jìn)行深度遍歷。廣度優(yōu)先搜索廣度優(yōu)先搜索算法會(huì)從第一個(gè)頂點(diǎn)開(kāi)始嘗試訪(fǎng)問(wèn)所有可能在第一個(gè)頂點(diǎn)附近的頂點(diǎn)。從本質(zhì)上說(shuō)，這種搜索在圖上的移動(dòng)是逐層進(jìn)行的，首先會(huì)檢查與第一個(gè)頂點(diǎn)相鄰的層，然后逐步向下檢查遠(yuǎn)離初始頂點(diǎn)的層。70廣度優(yōu)先搜索算法1.找到一個(gè)與當(dāng)前頂點(diǎn)相鄰的未訪(fǎng)問(wèn)過(guò)的頂點(diǎn)，把它標(biāo)記為已訪(fǎng)問(wèn)的，然后把它添加到隊(duì)列中。

2.如果找不到一個(gè)未訪(fǎng)問(wèn)過(guò)的相鄰頂點(diǎn)，那么從隊(duì)列中移除掉一個(gè)頂點(diǎn)（只要隊(duì)列中有頂點(diǎn)可以移除掉），把它作為當(dāng)前頂點(diǎn)，然后重新開(kāi)始。

3.如果由于隊(duì)列為空而無(wú)法執(zhí)行第二步操作，那么此算法就此結(jié)束。71廣度優(yōu)先搜索72算法BFS輸入：有向或無(wú)向圖G=(V,E)輸出：廣度優(yōu)先遍歷序列Step1.bfn=0;Step2.for每個(gè)頂點(diǎn)vV

標(biāo)記v未訪(fǎng)問(wèn)

endforStep3.for每個(gè)頂點(diǎn)vVifv未訪(fǎng)問(wèn)thenbfs(v)endfor0123456bfs(0)Tp=O(n+e)(鄰接表)Tp=O(n2).(鄰接矩陣)計(jì)算機(jī)如何實(shí)現(xiàn)BFS73——除輔助數(shù)組visited[n]外，還需再開(kāi)一輔助隊(duì)列！鄰接表例：起點(diǎn)輔助隊(duì)列v2已訪(fǎng)問(wèn)過(guò)了BFS遍歷結(jié)果入隊(duì)！初始f=n-1,r=0BFS算法效率分析74DFS與BFS之比較：空間復(fù)雜度相同，都是O(n)(借用了堆棧或隊(duì)列）；時(shí)間復(fù)雜度只與存儲(chǔ)結(jié)構(gòu)（鄰接矩陣或鄰接表）有關(guān)，而與搜索路徑無(wú)關(guān)。如果使用鄰接表來(lái)表示圖，則BFS循環(huán)的總時(shí)間代價(jià)為

d0+d1+…+dn-1=O(e)，其中的

di是頂點(diǎn)

i的度。如果使用鄰接矩陣，則BFS對(duì)于每一個(gè)被訪(fǎng)問(wèn)到的頂點(diǎn)，都要循環(huán)檢測(cè)矩陣中的整整一行（

n個(gè)元素），總的時(shí)間代價(jià)為O(n2)。（設(shè)圖中有n個(gè)頂點(diǎn)，e條邊）練習(xí)75對(duì)下列連通圖G進(jìn)行廣度優(yōu)先搜索遍歷，得到頂點(diǎn)的訪(fǎng)問(wèn)序列為：主要內(nèi)容8.1圖的定義8.2圖的存儲(chǔ)表示8.3圖的第一個(gè)應(yīng)用：拓?fù)渑判?.4圖的搜索8.5最小生成樹(shù)8.6查找最短路徑

8.5最小生成樹(shù)最小生成樹(shù)當(dāng)設(shè)計(jì)網(wǎng)絡(luò)的時(shí)候，網(wǎng)絡(luò)節(jié)點(diǎn)之間的連接數(shù)量很可能會(huì)多于最小連接數(shù)量。額外的連接是一種資源浪費(fèi)，應(yīng)該盡可能地消除它。額外的連接也會(huì)使其他人對(duì)網(wǎng)絡(luò)的研究和理解變得不必要的復(fù)雜。因此需要使得網(wǎng)絡(luò)只包含對(duì)節(jié)點(diǎn)連接而言最小數(shù)量的必要連接。當(dāng)把這種網(wǎng)絡(luò)應(yīng)用到圖上的時(shí)候，這樣的網(wǎng)絡(luò)就被稱(chēng)為是最小生成樹(shù)。

最小生成樹(shù)的得名源于覆蓋每個(gè)頂點(diǎn)（范圍）所必需的最少數(shù)量的構(gòu)造邊，而且說(shuō)它是樹(shù)是因?yàn)榻Y(jié)果圖是非循環(huán)的。需要牢記一個(gè)重要的內(nèi)容：一張圖可能包含多個(gè)最小生成樹(shù)。創(chuàng)建的最小生成樹(shù)完全依賴(lài)于初始頂點(diǎn)。78最小生成樹(shù)算法79畫(huà)出下圖的生成樹(shù)02130213最小生成樹(shù)80首先明確：使用不同的遍歷圖的方法，可以得到不同的生成樹(shù)；從不同的頂點(diǎn)出發(fā)，也可能得到不同的生成樹(shù)。按照生成樹(shù)的定義，n個(gè)頂點(diǎn)的連通網(wǎng)絡(luò)的生成樹(shù)有n個(gè)頂點(diǎn)、n-1條邊。即有權(quán)圖目標(biāo)：在網(wǎng)絡(luò)的多個(gè)生成樹(shù)中，尋找一個(gè)各邊權(quán)值之和最小的生成樹(shù)。構(gòu)造最小生成樹(shù)的準(zhǔn)則必須只使用該網(wǎng)絡(luò)中的邊來(lái)構(gòu)造最小生成樹(shù)；必須使用且僅使用n-1條邊來(lái)聯(lián)結(jié)網(wǎng)絡(luò)中的n個(gè)頂點(diǎn)；不能使用產(chǎn)生回路的邊。典型用途81欲在n個(gè)城市間建立通信網(wǎng)，則n個(gè)城市應(yīng)鋪n-1條線(xiàn)路；但因?yàn)槊織l線(xiàn)路都會(huì)有對(duì)應(yīng)的經(jīng)濟(jì)成本，而n個(gè)城市可能有n(n-1)/2條線(xiàn)路，那么，如何選擇n–1條線(xiàn)路，使總費(fèi)用最少？數(shù)學(xué)模型：頂點(diǎn)———表示城市，有n個(gè)；邊————表示線(xiàn)路，有n–1條；邊的權(quán)值—表示線(xiàn)路的經(jīng)濟(jì)代價(jià)；連通網(wǎng)——表示n個(gè)城市間通信網(wǎng)。顯然此連通網(wǎng)是一個(gè)生成樹(shù)！問(wèn)題抽象：n個(gè)頂點(diǎn)的生成樹(shù)很多，需要從中選一棵代價(jià)最小的生成樹(shù)，即該樹(shù)各邊的代價(jià)之和最小。此樹(shù)便稱(chēng)為最小生成樹(shù)MST(MinimumcostSpanningTree)如何求得最小生成樹(shù)82——有多種算法，但最常用的是以下兩種：最小生成樹(shù)的MST性質(zhì)如下：Kruskal（克魯斯卡爾）算法Prim（普里姆）算法Kruskal算法特點(diǎn)：將邊歸并，適于求稀疏網(wǎng)的最小生成樹(shù)。Prime算法特點(diǎn):

將頂點(diǎn)歸并，與邊數(shù)無(wú)關(guān)，適于稠密網(wǎng)。這兩個(gè)算法，都是利用MST性質(zhì)來(lái)構(gòu)造最小生成樹(shù)的。若U集是V的一個(gè)非空子集，若(u0,v0)是一條最小權(quán)值的邊，其中u0U，v0V-U；則：(u0,v0)必在最小生成樹(shù)上。

克魯斯卡爾（Kruskal）算法83步驟：(1)首先構(gòu)造一個(gè)只有n個(gè)頂點(diǎn)但沒(méi)有邊的非連通圖T={V,},

圖中每個(gè)頂點(diǎn)自成一個(gè)連通分量。(2)當(dāng)在邊集

E

中選到一條具有最小權(quán)值的邊時(shí),若該邊的兩個(gè)頂點(diǎn)落在T中不同的連通分量上，則將此邊加入到生成樹(shù)的邊集合T

中；否則將此邊舍去，重新選擇一條權(quán)值最小的邊。(3)如此重復(fù)下去，直到所有頂點(diǎn)在同一個(gè)連通分量上為止。此時(shí)的T即為所求（最小生成樹(shù)）。設(shè)N={V,E}是有n個(gè)頂點(diǎn)的連通網(wǎng)，Kruskal算法采用鄰接表作為圖的存儲(chǔ)表示Kruskal算法84例：1465231565546362154321352461、初始連通分量：{1},{2},{3},{4},{5},{6}2、反復(fù)執(zhí)行添加、放棄動(dòng)作。條件：邊數(shù)不等于n-1時(shí)邊 動(dòng)作 連通分量

(1,3)添加 {1,3},{4},{5},{6},{2}(4,6)添加 {1,3},{4,6},{2},{5}(2,5)添加 {1,3},{4,6},{2,5}(3,6)添加 {1,3,4,6},{2,5}(1,4)放棄 因構(gòu)成回路

(3,4)放棄 因構(gòu)成回路

(2,3)添加 {1,3,4,5,6,2}普里姆(Prim)算法普里姆算法的基本思想：從連通網(wǎng)絡(luò)N={V,E}中的某一頂點(diǎn)u0出發(fā),選擇與它關(guān)聯(lián)的具有最小權(quán)值的邊(u0,v),將其頂點(diǎn)加入到生成樹(shù)頂點(diǎn)集合U中。以后每一步從一個(gè)頂點(diǎn)在U中,而另一個(gè)頂點(diǎn)不在U中的各條邊中選擇權(quán)值最小的邊(u,v),把它的頂點(diǎn)加入到集合U中。

如此繼續(xù)下去,直到網(wǎng)絡(luò)中的所有頂點(diǎn)都加入到生成樹(shù)頂點(diǎn)集合U中為止。采用鄰接矩陣作為圖的存儲(chǔ)表示。85Prim算法86例：1465231565546362364251[注]：在最小生成樹(shù)的生成過(guò)程中，所選的邊都是一端在V-U中，另一端在U中。50461322810251424221618原圖1204613210255邊(0,5,10)

加入生成樹(shù)操作演示-12810lowcostcloseVertex0123456選v=5選邊(0,5)00000000000000-12825-1lowcostcloseVertex01234560500000-1100000050461322810251424221618原圖12選v=4選邊(5,4)5046132102522邊(5,4,25)

加入生成樹(shù)操作演示-1282225-124lowcostcloseVertex0123