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

第六章回顧樹(shù)的定義和基本術(shù)語(yǔ)子樹(shù)孩子葉子兄弟

度……二叉樹(shù)的性質(zhì)

2k-12k-1n0=n2+1[log2n]+1i的雙親[i/2]；2i>n，i無(wú)左孩子；2i+1>n，i無(wú)右孩子二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉鏈表、三叉鏈表二叉樹(shù)的遍歷先序遍歷、中序遍歷、后序遍歷線(xiàn)索二叉樹(shù)在二叉鏈表的基礎(chǔ)上增加兩個(gè)標(biāo)志域，表示按某種次序遍歷時(shí)的前驅(qū)和后繼樹(shù)的三種存儲(chǔ)結(jié)構(gòu)雙親表示法孩子鏈表表示法孩子兄弟表示法森林和二叉樹(shù)的轉(zhuǎn)換由森林轉(zhuǎn)換為二叉樹(shù)由二叉樹(shù)轉(zhuǎn)換為森林樹(shù)和森林的遍歷樹(shù)的先根遍歷（=

二叉樹(shù)的先序遍歷）樹(shù)的后根遍歷（=

二叉樹(shù)的中序遍歷）森林的先序遍歷（=

二叉樹(shù)的先序遍歷）森林的中序遍歷（=

二叉樹(shù)的中序遍歷）赫夫曼樹(shù)和赫夫曼編碼課前思考1、如何確定一項(xiàng)工程的工期？最佳工期如何計(jì)算？（關(guān)鍵路徑問(wèn)題）2、如何以最低造價(jià)架構(gòu)城市之間的通信網(wǎng)？幾個(gè)小區(qū)之間要建一個(gè)供水站，建在什么位置最合適？（最小生成樹(shù)問(wèn)題）3、如何合理安排大一到大四的教學(xué)計(jì)劃？（拓?fù)渑判騿?wèn)題）4、從上海到北京怎么走最省時(shí)間或金錢(qián)？如何花費(fèi)最少周游所有城市？（最短路徑問(wèn)題）課前導(dǎo)學(xué)7.1圖的定義和術(shù)語(yǔ)7.2圖的存儲(chǔ)結(jié)構(gòu)7.3圖的遍歷7.4圖的連通性問(wèn)題7.5有向無(wú)環(huán)圖及其應(yīng)用7.6最短路徑知識(shí)點(diǎn)小結(jié)第七章圖【學(xué)習(xí)目標(biāo)】

1．領(lǐng)會(huì)圖的類(lèi)型定義。

2．熟悉圖的各種存儲(chǔ)結(jié)構(gòu)及其構(gòu)造算法，了解各種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)及其選用原則。

3．熟練掌握?qǐng)D的兩種遍歷算法。

4．理解各種圖的應(yīng)用問(wèn)題的算法。

【重點(diǎn)和難點(diǎn)】理解各種圖的算法及其應(yīng)用場(chǎng)合。

【知識(shí)點(diǎn)】圖的類(lèi)型定義、圖的存儲(chǔ)表示、圖的深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷、無(wú)向網(wǎng)的最小生成樹(shù)、最短路徑、拓?fù)渑判?、關(guān)鍵路徑7.1圖的定義和術(shù)語(yǔ)

1.基本定義和術(shù)語(yǔ)圖(Graph)——圖G是由兩個(gè)集合V(G)和E(G)組成的,記為G=(V,E)，其中：V(G)是頂點(diǎn)(Vertex)的非空有限集E(G)是邊(Edge)的有限集合，邊是頂點(diǎn)的無(wú)序?qū)?即：無(wú)方向的，（v0,v2）)或有序?qū)Γ矗河蟹较虻?<v0,v2>）。V0001V11V22243V3V0V2V1V3

有向圖(Digraph)有向圖G是由兩個(gè)集合V(G)和E(G)組成的，其中：V(G)是頂點(diǎn)的非空有限集，E(G)是有向邊（也稱(chēng)?。┑挠邢藜?，弧是頂點(diǎn)的有序?qū)?，記?lt;v,w>，v,w是頂點(diǎn)，v為弧尾，w為弧頭例245136G1圖G1中：V(G1)={1,2,3,4,5,6}E(G1)={<1,2>,<2,1>,<2,3>,<2,4>,<3,5>,<5,6>,<6,3>}無(wú)向圖(Undigraph)無(wú)向圖G是由兩個(gè)集合V(G)和E(G)組成的，其中：V(G)是頂點(diǎn)的非空有限集，E(G)是邊的有限集合，邊是頂點(diǎn)的無(wú)序?qū)?，記為（v,w）或（w,v)，并且(v,w)=(w,v)例157324G26圖G2中：V(G2)={1,2,3,4,5,6,7}E(G1)={(1,2),(1,3),(2,3),(2,4),(2,5),(5,6),(5,7)}有向完備圖——n個(gè)頂點(diǎn)的有向圖最大邊數(shù)是n(n-1)無(wú)向完備圖——n個(gè)頂點(diǎn)的無(wú)向圖最大邊數(shù)是n(n-1)/2例213213有向完備圖無(wú)向完備圖稀疏圖——有很少條邊或弧的圖（e<nlogn)粗略：e<(n-1)稠密圖——有很多條邊或弧的圖例G21573246例157324G26稀疏圖稠密圖頂點(diǎn)的度無(wú)向圖中，頂點(diǎn)的度為與每個(gè)頂點(diǎn)相連的邊數(shù)有向圖中，頂點(diǎn)的度分成入度與出度入度：以該頂點(diǎn)為頭的弧的數(shù)目出度：以該頂點(diǎn)為尾的弧的數(shù)目例245136G1頂點(diǎn)2入度：1出度：3頂點(diǎn)4入度：1出度：0例157324G26頂點(diǎn)5的度：3頂點(diǎn)2的度：4子圖——如果圖G(V,E)和圖G’(V’,E’),滿(mǎn)足：V’VE’E

則稱(chēng)G‘為G的子圖0123子圖0130123023356例245136圖與子圖權(quán)(Weight)——與圖的邊或弧相關(guān)的數(shù),可以表示兩個(gè)頂點(diǎn)之間的距離或耗費(fèi)網(wǎng)——帶權(quán)的圖上海→北京怎么走最優(yōu)?

例北京上海南京濟(jì)南徐州280500320180160600260200青島大連200路徑——路徑是頂點(diǎn)的序列V={Vi，0,Vi，1,……Vi，n}，滿(mǎn)足(Vi，j-1,Vi，j)E或<Vi，j-1,Vi，j>E,(1<jn)路徑長(zhǎng)度——沿路徑邊的數(shù)目或沿路徑各邊權(quán)值之和回路——第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑簡(jiǎn)單路徑——序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑簡(jiǎn)單回路——除了第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)外，其余頂點(diǎn)不重復(fù)出現(xiàn)的回路例245136G1路徑：1，2，3，5，6，3路徑長(zhǎng)度：5簡(jiǎn)單路徑：1，2，3，5回路：1，2，3，5，6，3，1簡(jiǎn)單回路：3，5，6，3例157324G26路徑：1，2，5，7，6，5，2，3路徑長(zhǎng)度：7簡(jiǎn)單路徑：1，2，5，7，6回路：1，2，5，7，6，5，2，1簡(jiǎn)單回路：1，2，3，1連通——從頂點(diǎn)V到頂點(diǎn)W有一條路徑，則說(shuō)V和W是連通的連通圖——圖中任意兩個(gè)頂點(diǎn)都是連通連通分量——非連通圖的每一個(gè)連通部分（連通的子圖）強(qiáng)連通圖——有向圖中，如果對(duì)每一對(duì)Vi,VjV,ViVj,從Vi到Vj

和從Vj到

Vi都存在路徑，則稱(chēng)G是~強(qiáng)連通圖（有向圖）356例連通圖例245136非強(qiáng)連通圖例2413例2413非強(qiáng)連通圖的兩個(gè)強(qiáng)連通分量2.圖的抽象數(shù)據(jù)類(lèi)型

ADTGraph{

數(shù)據(jù)對(duì)象V：V是具有相同特性的數(shù)據(jù)元素的集合，稱(chēng)為頂點(diǎn)集。

數(shù)據(jù)關(guān)系R：R＝{VR}VR＝{<v,w>|v,w∈V且P(v,w)，<v,w>表示從v到w的弧，謂詞P(v,w)定義了弧<v,w>的意義或信息}

基本操作P：

結(jié)構(gòu)的建立和銷(xiāo)毀:

CreateGraph(&G,V,VR);//按V和VR的定義構(gòu)造圖G

DestroyGraph(&G);//銷(xiāo)毀圖G對(duì)頂點(diǎn)的訪(fǎng)問(wèn)操作:

LocateVex(G,u);//若G中存在頂點(diǎn)u，則返回該頂點(diǎn)在圖中位置；否則返回其它信息。

GetVex(G,v);//返回v的值

PutVex(&G,v,value);//對(duì)v賦值value

對(duì)鄰接點(diǎn)的操作:

FirstAdjVex(G,v);//返回v的第一個(gè)鄰接點(diǎn)。若該頂點(diǎn)在G中沒(méi)有鄰接點(diǎn)，則返回“空”

NextAdjVex(G,v,w);//返回v的（相對(duì)于w的）下一個(gè)鄰接點(diǎn)若w是v的最后一個(gè)鄰接點(diǎn)，則返回“空”

插入或刪除頂點(diǎn):

InsertVex(&G,v);//在圖G中增添新頂點(diǎn)v

DeleteVex(&G,v);//刪除G中頂點(diǎn)v及其相關(guān)的弧插入和刪除弧:

InsertArc(&G,v,w);//在G中增添弧<v,w>，若G是無(wú)向的，則還增添對(duì)稱(chēng)弧<w,v>

DeleteArc(&G,v,w);//在G中刪除弧<v,w>，若G是無(wú)向的，則還刪除對(duì)稱(chēng)弧<w,v>

遍歷:

DFSTraverse(G,v,Visit());//從頂點(diǎn)v起深度優(yōu)先遍歷圖G，并對(duì)每個(gè)頂點(diǎn)調(diào)用函數(shù)Visit一次且僅一次

BFSTraverse(G,v,Visit());//從頂點(diǎn)v起廣度優(yōu)先遍歷圖G，并對(duì)每個(gè)頂點(diǎn)調(diào)用函數(shù)Visit一次且僅一次7.2圖的存儲(chǔ)結(jié)構(gòu)

（1）鄰接矩陣——表示頂點(diǎn)間相聯(lián)關(guān)系的矩陣定義：設(shè)G=(V,E)是有n1個(gè)頂點(diǎn)的圖，G的鄰接矩陣A是具有以下性質(zhì)的n階方陣?yán)鼼12413例15324G2特點(diǎn)：無(wú)向圖的鄰接矩陣對(duì)稱(chēng)，可壓縮存儲(chǔ)；有n個(gè)頂點(diǎn)的無(wú)向圖需存儲(chǔ)空間為n(n+1)/2有向圖鄰接矩陣不一定對(duì)稱(chēng)；有n個(gè)頂點(diǎn)的有向圖需存儲(chǔ)空間為n2無(wú)向圖中頂點(diǎn)Vi的度TD(Vi)是鄰接矩陣A中第i行元素之和有向圖中，頂點(diǎn)Vi的出度是A中第i行元素之和頂點(diǎn)Vi的入度是A中第i列元素之和例1452375318642帶權(quán)的無(wú)向圖的鄰接矩陣網(wǎng)絡(luò)的鄰接矩陣可定義為：（2）鄰接表實(shí)現(xiàn)：為圖中每個(gè)頂點(diǎn)建立一個(gè)單鏈表，第i個(gè)單鏈表中的結(jié)點(diǎn)表示依附于頂點(diǎn)Vi的邊（有向圖中指以Vi為尾的?。├鼼1bdac例aecbdG21234acdbdatafirstarc3241^^^^adjvex

nextarc1234acdbdatafirstarc4212^^^adjvex

nextarc5e435^15323^特點(diǎn)無(wú)向圖中頂點(diǎn)Vi的度為第i個(gè)單鏈表中的結(jié)點(diǎn)數(shù)有向圖中頂點(diǎn)Vi的出度為第i個(gè)單鏈表中的結(jié)點(diǎn)個(gè)數(shù)頂點(diǎn)Vi的入度為整個(gè)單鏈表中鄰接點(diǎn)域值是i的結(jié)點(diǎn)個(gè)數(shù)逆鄰接表：有向圖中對(duì)每個(gè)結(jié)點(diǎn)建立以Vi為頭的弧的單鏈表例G1bdac1234acdbvexdatafirstarc41^1^^3^adjvexnext逆鄰接表網(wǎng)絡(luò)的鄰接矩陣可定義為：7.1圖的定義和術(shù)語(yǔ)7.2圖的存儲(chǔ)結(jié)構(gòu)7.3圖的遍歷7.4圖的連通性問(wèn)題7.5有向無(wú)環(huán)圖及其應(yīng)用7.6最短路徑知識(shí)點(diǎn)小結(jié)第七章圖例G1bdac例aecbdG2內(nèi)容回顧：1、圖、子圖、（強(qiáng)）連通圖、網(wǎng)2、（簡(jiǎn)單）路徑，（簡(jiǎn)單）回路、長(zhǎng)度3、度、入度、出度4、鄰接矩陣、鄰接表、鄰接多重表1234acdbdatafirstarc3241^^^^adjvex

nextarc1234acdbdatafirstarc4212^^^adjvex

nextarc5e435^15323^（3）鄰接多重表鄰接多重表是無(wú)向圖的另一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，由于用鄰接表存儲(chǔ)無(wú)向圖時(shí)，雖然容易求出頂點(diǎn)和邊的各種信息，但在鄰接表中每一條邊有兩個(gè)結(jié)點(diǎn)，分別在第i和第j個(gè)鏈表中，給圖的某些操作帶來(lái)不便。在鄰接多重表中,每一條邊只有一個(gè)邊結(jié)點(diǎn),為有關(guān)邊的處理提供了方便。

markivex

ilink

jvex

jlinkinfo邊結(jié)點(diǎn)的結(jié)構(gòu)：

dataFirstout頂點(diǎn)結(jié)點(diǎn)的結(jié)構(gòu)：頂點(diǎn)結(jié)點(diǎn)的結(jié)構(gòu)

存儲(chǔ)頂點(diǎn)信息的結(jié)點(diǎn)表以順序表方式組織,每一個(gè)頂點(diǎn)結(jié)點(diǎn)有兩個(gè)數(shù)據(jù)成員：其中，data存放與該頂點(diǎn)相關(guān)的信息，F(xiàn)irstout

是指示第一條依附該頂點(diǎn)的邊的指針。在鄰接多重表中,所有依附同一個(gè)頂點(diǎn)的邊都鏈接在同一個(gè)單鏈表中。

從頂點(diǎn)i

出發(fā),可以循環(huán)鏈找到所有依附于該頂點(diǎn)的邊，也可以找到它的所有鄰接頂點(diǎn)。

dataFirstout例aecbd1234acdb5e1214

34323552^^^^^

markivex

ilink

jvex

jlinkinfo邊結(jié)點(diǎn)的結(jié)構(gòu)Mark：標(biāo)志位Ivex、jvex：該邊兩頂點(diǎn)位置。

ilink、

jlink：分別指向下一條依附頂點(diǎn)ivex

或jvex：的邊,Info：存放與該邊相關(guān)的權(quán)值。鄰接表、鄰接矩陣、鄰接多重表的比較：在邊稀疏（e<<n（n-1）/2）的情況下，用鄰接表、鄰接多重表表示圖比鄰接矩陣節(jié)省存儲(chǔ)空間，當(dāng)和邊相關(guān)的信息較多時(shí)更是如此。在鄰接表上容易找到任何一頂點(diǎn)的第一個(gè)鄰接點(diǎn)和下一個(gè)鄰接點(diǎn)，但要判定任意兩個(gè)頂點(diǎn)（vi和vj）之間是否有邊或弧相連，則需搜索第i個(gè)或第j個(gè)鏈表，因此，不及鄰接矩陣和方便。鄰接表、鄰接矩陣：無(wú)（有）向圖；鄰接多重表：無(wú)向圖；7.3

圖的遍歷圖的遍歷(TraveringGraph)：從圖的某一頂點(diǎn)出發(fā)，訪(fǎng)遍圖中的其余頂點(diǎn)，且每個(gè)頂點(diǎn)僅被訪(fǎng)問(wèn)一次。圖的遍歷算法是各種圖的操作的基礎(chǔ)。

◆復(fù)雜性：圖的任意頂點(diǎn)可能和其余的頂點(diǎn)相鄰接，可能在訪(fǎng)問(wèn)了某個(gè)頂點(diǎn)后，沿某條路徑搜索后又回到原頂點(diǎn)。

◆解決辦法：在遍歷過(guò)程中記下已被訪(fǎng)問(wèn)過(guò)的頂點(diǎn)。設(shè)置一個(gè)輔助向量Visited[1…n](n為頂點(diǎn)數(shù))，其初值為0，一旦訪(fǎng)問(wèn)了頂點(diǎn)vi后，使Visited[i]為1或?yàn)樵L(fǎng)問(wèn)的次序號(hào)。圖的遍歷算法有深度優(yōu)先搜索算法和廣度優(yōu)先搜索算法。采用的數(shù)據(jù)結(jié)構(gòu)是(正)鄰接鏈表。7.3.1深度優(yōu)先搜索算法

深度優(yōu)先搜索(DepthFirstSearch--DFS)遍歷類(lèi)似樹(shù)的先序遍歷，是樹(shù)的先序遍歷的推廣。算法思想:1)從圖中某個(gè)頂點(diǎn)v出發(fā)，訪(fǎng)問(wèn)v；然后找到v的一個(gè)鄰接頂點(diǎn)v12)從v1出發(fā)，深度優(yōu)先訪(fǎng)問(wèn)和v1相鄰接未被訪(fǎng)問(wèn)的所有頂點(diǎn)；3)轉(zhuǎn)1)，直到和vi相鄰接的所有頂點(diǎn)都被訪(fǎng)問(wèn)為止V1V2V4V5V3V7V6V8例深度遍歷：V1V2V4V8V5V3V6V7V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8深度遍歷：V1V2V4V8V5V6V3V7深度遍歷：V1V2V4V8V5V6V3V7深度遍歷：V11234v1v3v4v2vexdatafirstarc2783^^^adjvexnext5v5641^51282^v6v7v8678736354^^^V3V7V6V2V5V8V4當(dāng)以鄰接表作存儲(chǔ)結(jié)構(gòu)時(shí)，深度優(yōu)先搜索遍歷圖的時(shí)間復(fù)雜度為O（n+e）V1V2V4V5V3V7V6V8例深度遍歷：V11234v1v3v4v2vexdatafirstarc2783^^^adjvexnext5v5641^51282^v6v7v8678736354^^^V3V7V6V2V5V8V4當(dāng)以鄰接表作存儲(chǔ)結(jié)構(gòu)時(shí)，深度優(yōu)先搜索遍歷圖的時(shí)間復(fù)雜度為O（n+e）V1V2V4V5V3V7V6V8例12341342vexdatafirstarc2783^^^adjvexnext556^482^6786787^^^深度遍歷：V1V3V7V6V2V4V8V52.廣度優(yōu)先遍歷(BFS)方法：從圖的某一頂點(diǎn)V0出發(fā)，訪(fǎng)問(wèn)此頂點(diǎn)后，依次訪(fǎng)問(wèn)V0的各個(gè)未曾訪(fǎng)問(wèn)過(guò)的鄰接點(diǎn)；然后分別從這些鄰接點(diǎn)出發(fā)，廣度優(yōu)先遍歷圖，直至圖中所有已被訪(fǎng)問(wèn)的頂點(diǎn)的鄰接點(diǎn)都被訪(fǎng)問(wèn)到；若此時(shí)圖中尚有頂點(diǎn)未被訪(fǎng)問(wèn)，則另選圖中一個(gè)未被訪(fǎng)問(wèn)的頂點(diǎn)作起點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪(fǎng)問(wèn)為止。V1V2V4V5V3V7V6V8例廣度遍歷：V1V2V3V4V5V6V7V87.3.2廣度優(yōu)先搜索算法

廣度優(yōu)先搜索(BreadthFirstSearch--BFS)遍歷類(lèi)似樹(shù)的按層次遍歷的過(guò)程。

算法思想:⑴從圖中某個(gè)頂點(diǎn)vi出發(fā)，訪(fǎng)問(wèn)vi；⑵訪(fǎng)問(wèn)vi的所有相鄰接且未被訪(fǎng)問(wèn)的所有頂點(diǎn)vi1，vi2，…vim⑶以vi1，vi2，…vim的次序，以vij(1≦j≦m)依次作為vi，轉(zhuǎn)1⑴；V1V2V4V5V3V7V6V8例廣度遍歷：V1V2V3V4V5V6V7V8V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8廣度遍歷：V1V2V3V4V5V6V7V8廣度遍歷：V1V2V3V4V5V6V7V8V1V2V4V5V3V7V6V8例廣度遍歷：V1V2V3V4V6V7V8V5例adbce1234acdbvexdatafirstarc5543^^^adjvexnext5e1^51143^22遍歷序列：adcbe例：有向圖廣度優(yōu)先搜索遍歷鄰接鏈表結(jié)構(gòu)13?014?2?3?01234MAX_VEX-1v12v20?v33v41┇┇┇v51(a)有向圖G’v1v2v3v4v5圖的遍歷有兩條路徑：深度優(yōu)先搜索和廣度優(yōu)先搜索

當(dāng)用鄰接矩陣作圖的存儲(chǔ)結(jié)構(gòu)時(shí)，查找每個(gè)頂點(diǎn)的鄰接點(diǎn)所需要時(shí)間為O（n2），n為圖中頂點(diǎn)數(shù)；而當(dāng)以鄰接表作圖的存儲(chǔ)結(jié)構(gòu)時(shí)，找鄰接點(diǎn)所需時(shí)間為O（e），e為無(wú)向圖中邊的數(shù)或有向圖中弧的數(shù)。7.1

圖的定義和術(shù)語(yǔ)7.2圖的存儲(chǔ)結(jié)構(gòu)7.3圖的遍歷7.4最小生成樹(shù)7.5最短路徑小結(jié)第七章圖欲在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)是一棵生成樹(shù)！問(wèn)題抽象：

n個(gè)頂點(diǎn)的生成樹(shù)很多，需要從中選一棵代價(jià)最小的生成樹(shù)，即該樹(shù)各邊的代價(jià)之和最小。此樹(shù)便稱(chēng)為最小生成樹(shù)MST。MinimumcostSpanningTree問(wèn)題導(dǎo)入1、如何以最低造價(jià)架構(gòu)城市之間的通信網(wǎng)？幾個(gè)小區(qū)之間要建一個(gè)供水站，建在什么位置最合適？（最小生成樹(shù)問(wèn)題）2、從上海到北京怎么走最省時(shí)間或金錢(qián)？如何花費(fèi)最少周游所有城市？（最短路徑問(wèn)題）例北京上海南京濟(jì)南徐州280400320180160600260250青島連200生成樹(shù)所有頂點(diǎn)均由邊連接在一起，但不存在回路的圖生成樹(shù)的種類(lèi)深度優(yōu)先生成樹(shù)與廣度優(yōu)先生成樹(shù)生成森林非連通圖每個(gè)連通分量的生成樹(shù)一起組成非連通圖的生成森林首先明確：使用不同的遍歷圖的方法，可以得到不同的生成樹(shù)；從不同的頂點(diǎn)出發(fā)，也可能得到不同的生成樹(shù)。7.4最小生成樹(shù)ACDEIBFGHJONMLK非連通無(wú)向圖AHKCDEIBFOGJNML非連通圖的生成森林說(shuō)明（1）一個(gè)圖可以有許多棵不同的生成樹(shù)（2）所有生成樹(shù)具有以下共同特點(diǎn)：生成樹(shù)的頂點(diǎn)個(gè)數(shù)與圖的頂點(diǎn)個(gè)數(shù)相同生成樹(shù)是圖的極小連通子圖一個(gè)有n個(gè)頂點(diǎn)的連通圖的生成樹(shù)有n-1條邊生成樹(shù)中任意兩個(gè)頂點(diǎn)間的路徑是唯一的在生成樹(shù)中再加一條邊必然形成回路（3）含n個(gè)頂點(diǎn)n-1條邊的圖不一定是生成樹(shù)GHKIONMLKONMLKONMLKV1V2V4V5V3V7V6V8例深度遍歷：V1V2V4V8V5V3V6V7V1V2V4V5V3V7V6V8深度優(yōu)先生成樹(shù)V1V2V4V5V3V7V6V8廣度優(yōu)先生成樹(shù)V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8廣度遍歷：V1V2V3V4V5V6V7V8例ABLMCFDEGHKIJABLMFCJDEGHKI深度優(yōu)先生成森林

2.最小生成樹(shù)問(wèn)題提出：要在n個(gè)城市間建立通信聯(lián)絡(luò)網(wǎng)，頂點(diǎn)——表示城市權(quán)——城市間建立通信線(xiàn)路所需花費(fèi)代價(jià)最小1654327131791812752410

問(wèn)題分析1、n個(gè)城市最多可設(shè)置n(n-1)/2條線(xiàn)路（選擇邊，選擇多少條邊）2、問(wèn)題轉(zhuǎn)化為：如何在可能的線(xiàn)路中選擇n-1條，能把所有城市（頂點(diǎn)）均連起來(lái)，且總耗費(fèi)各邊權(quán)值之和最?。?、希望找到一棵生成樹(shù)，它的每條邊上的權(quán)值之和（即建立該通信網(wǎng)所需花費(fèi)的總代價(jià)）最小———最小代價(jià)生成樹(shù)建立數(shù)學(xué)模型：頂點(diǎn)———表示城市；邊————表示線(xiàn)路；權(quán)值—表示線(xiàn)路的經(jīng)濟(jì)代價(jià)；連通網(wǎng)——城市間的通信網(wǎng)；構(gòu)造最小生成樹(shù)方法方法一：普里姆(Prim)算法

——?dú)w并頂點(diǎn)，時(shí)間復(fù)雜度O(n2)方法二：克魯斯卡爾算法

——?dú)w并邊，時(shí)間復(fù)雜度與邊相關(guān)設(shè)想一下：先把權(quán)值最小的邊歸入生成樹(shù)內(nèi)，逐個(gè)遞增，舍去回路邊，則得到的很可能就是最小生成樹(shù)！例1654326513566425131163141643142116432142516543214253方法一：普里姆(Prim)算法示例：歸并頂點(diǎn)例1654326513566425165432651356642516543214253012345012345úúúúúúúú?ùêêêêêêêê?é￥￥￥￥￥￥￥￥￥￥06246063205546505135065160方法二：克魯斯卡爾(Kruskal)算法示例：歸并邊算法思想：設(shè)連通網(wǎng)N=(V,{E})，令最小生成樹(shù)初始狀態(tài)為只有n個(gè)頂點(diǎn)而無(wú)邊的非連通圖T=(V,{})，每個(gè)頂點(diǎn)自成一個(gè)連通分量在E中選取代價(jià)最小的邊，若該邊依附的頂點(diǎn)落在T中不同的連通分量上，則將此邊加入到T中；否則，舍去此邊，選取下一條代價(jià)最小的邊依此類(lèi)推，直至T中所有頂點(diǎn)都在同一連通分量上為止例1654326513566425165432123457.5

最短路徑問(wèn)題提出：如何求從上海到圖中各城市的最短路徑？如何求任意兩個(gè)城市之間的最短路徑？例北京上海南京濟(jì)南徐州280400320180160600260250青島連2005606601807.5.1

求某一頂點(diǎn)到其余各頂點(diǎn)的最短路徑基本概念用帶權(quán)的有向圖表示一個(gè)交通運(yùn)輸網(wǎng)，圖中：頂點(diǎn)——表示城市邊——表示城市間的交通聯(lián)系權(quán)——表示此線(xiàn)路的長(zhǎng)度或沿此線(xiàn)路運(yùn)輸所花的時(shí)間或費(fèi)用等最短路徑——從某頂點(diǎn)出發(fā)，沿圖的邊到達(dá)另一頂點(diǎn)所經(jīng)過(guò)的路徑中，各邊上權(quán)值之和最小的一條路徑。最短路徑(Dijkstra算法)目的：

設(shè)一有向圖G=（V,E），已知各邊的權(quán)值，以某指定點(diǎn)v0為源點(diǎn)，求從v0到圖的其余各點(diǎn)的最短路徑。例1：源點(diǎn)從F→A的路徑有4條：①F→A：24②F→B→A：5＋18=23③F→B→C→A：5+7+9=21④

F→D→C→A：25+12+9=36想一想：從F→B的最短路徑是哪條？從F→C的最短路徑是哪條？迪杰斯特拉算法思想：按路徑長(zhǎng)度遞增次序產(chǎn)生最短路徑把圖中的頂點(diǎn)V分成兩組：（1）S：已求出最短路徑的頂點(diǎn)的集合（2）V-S=T：尚未確定最短路徑的頂點(diǎn)集合例：下圖中從源點(diǎn)V0到其余各頂點(diǎn)的最短路徑51643208562301371732913長(zhǎng)度最短路徑<V0,V1><V0,V2><V0,V2,V3><V0,V2,V3,V4><V0,V2,V3,V4,V5><V0,V1,V6>8131921203.求最短路徑步驟初始時(shí)令S={V0},T={其余頂點(diǎn)}，T中頂點(diǎn)對(duì)應(yīng)的距離值：若存在<V0,Vi>，為<V0,Vi>弧上的權(quán)值若不存在<V0,Vi>，為從T中選取一個(gè)其距離值為最小的頂點(diǎn)W，加入S對(duì)T中頂點(diǎn)的距離值進(jìn)行修改：若加進(jìn)W作中間頂點(diǎn)，從V0到Vi的距離值比不加W的路徑要短，則修改此距離值重復(fù)上述步驟，直到S中包含所有頂點(diǎn)，即S=V為止516432085623013717329<V0,V1>:13<V0,V2>:8<V0,V3>:<V0,V4>:30<V0,V5>:<V0,V6>:32從中選

V2<V0,V2>:813<V0,V1>8<V0,V2>30<V0,V4>32<V0,V6>V2:8<V0,V2>13<V0,V1>-------13<V0,V2,V3>30<V0,V4>32<V0,V6>V1:13<V0,V1>--------------13<V0,V2,V3>30<V0,V4>22<V0,V1,V5>20<V0,V1,V6>V3:13<V0,V2,V3>---------------------19<V0,V2,V3,V4>22<V0,V1,V5>20<V0,V1,V6>V4:19<V0,V2,V3,V4>終點(diǎn)從V0到各終點(diǎn)的最短路徑及其長(zhǎng)度V1V2V3V4V5V6Vj--------------------------------21<V0,V2,V3,V4,V5>20<V0,V1,V6>V6:20<V0,V1,V6>516432085623013717329例：求F到各頂點(diǎn)最短路徑7.6

有向無(wú)環(huán)圖及其應(yīng)用1.基本概念

有向無(wú)環(huán)圖（directedacyclinggraph）——

一個(gè)無(wú)環(huán)的有向圖，簡(jiǎn)稱(chēng)DAG圖。

作用：是描述一項(xiàng)工程進(jìn)行過(guò)程的有效工具。主要進(jìn)行拓?fù)渑判蚝完P(guān)鍵路徑的操作。

V1V2V4V3V5DAGV3V1V2DG2.拓?fù)渑判騿?wèn)題提出：

學(xué)生應(yīng)按怎樣的順序?qū)W習(xí)這些課程，才能無(wú)矛盾、順利地完成學(xué)業(yè)？

課程代號(hào)課程名稱(chēng)先修課C1C2C3C4C5C6C7C8C9C10C11C12無(wú)C1C1,C2C1C3,C4C11C3.C5C3,C6無(wú)C9C9C1,C9,C10程序設(shè)計(jì)基礎(chǔ)離散數(shù)學(xué)數(shù)據(jù)結(jié)構(gòu)匯編語(yǔ)言程序設(shè)計(jì)方法學(xué)計(jì)算機(jī)原理編譯原理操作系統(tǒng)高等數(shù)學(xué)線(xiàn)性代數(shù)普通物理數(shù)值分析拓?fù)渑判颍河赡硞€(gè)集合上的一個(gè)偏序得到該集合上的一個(gè)全序的操作。答案：采用拓?fù)渑判蚶n程代號(hào)課程名稱(chēng)先修課C1C2C3C4C5C6C7C8C9C10C11C12無(wú)C1C1,C2C1C3,C4C11C3.C5C3,C6無(wú)C9C9C1,C9,C10程序設(shè)計(jì)基礎(chǔ)離散數(shù)學(xué)數(shù)據(jù)結(jié)構(gòu)匯編語(yǔ)言程序設(shè)計(jì)方法學(xué)計(jì)算機(jī)原理編譯原理操作系統(tǒng)高等數(shù)學(xué)線(xiàn)性代數(shù)普通物理數(shù)值分析C1C2C3C4C5C6C7C8C9C10C11C12例：建立表示課程之間優(yōu)先關(guān)系的有向圖頂點(diǎn)——表示課程有向弧——表示先決條件，若課程i是課程j的先決條件，則圖中有弧<i,j>AOV網(wǎng)AOV網(wǎng)——用頂點(diǎn)表示活動(dòng)，用弧表示活動(dòng)間優(yōu)先關(guān)系的有向圖稱(chēng)為頂點(diǎn)表示活動(dòng)的網(wǎng)(ActivityOnVertexnetwork)，簡(jiǎn)稱(chēng)AOV網(wǎng)若<vi,vj>是圖中有向邊，則vi是vj的直接前驅(qū)；vj是vi的直接后繼AOV網(wǎng)中不允許有回路，這意味著某項(xiàng)活動(dòng)以自己為先決條件拓?fù)渑判颉袮OV網(wǎng)絡(luò)中各頂點(diǎn)按照它們相互之間的優(yōu)先關(guān)系排列成一個(gè)線(xiàn)性序列的過(guò)程檢測(cè)AOV網(wǎng)中是否存在環(huán)的方法：對(duì)有向圖構(gòu)造其頂點(diǎn)的拓?fù)溆行蛐蛄?，若網(wǎng)中所有頂點(diǎn)都在它的拓?fù)溆行蛐蛄兄校瑒t該AOV網(wǎng)必定不存在環(huán)拓?fù)渑判虻姆椒ㄔ谟邢驁D中選一個(gè)沒(méi)有前驅(qū)的頂點(diǎn)且輸出之從圖中刪除該頂點(diǎn)和所有以它為尾的弧重復(fù)上述兩步，直至全部頂點(diǎn)均已輸出；或者當(dāng)圖中不存在無(wú)前驅(qū)的頂點(diǎn)為止動(dòng)畫(huà)演示C1C2C3C4C5C6C7C8C9C10C11C12拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12--C8或：C9--C10--C11--C6--C1--C12--C4--C2--C3--C5--C7--C8一個(gè)AOV網(wǎng)的拓?fù)湫蛄胁皇俏ㄒ坏乃惴▽?shí)現(xiàn)以鄰接表作存儲(chǔ)結(jié)構(gòu)把鄰接表中所有入度為0的頂點(diǎn)進(jìn)棧棧非空時(shí)，輸出棧頂元素Vj并退棧；在鄰接表中查找Vj的直接后繼Vk，把Vk的入度減1；若Vk的入度為0則進(jìn)棧重復(fù)上述操作直至?？諡橹埂Ｈ魲？諘r(shí)輸出的頂點(diǎn)個(gè)數(shù)不是n，則有向圖有環(huán)；否則，拓?fù)渑判蛲戤吽惴?.12StatusTopologicalSort(ALGraphG){//有向圖G采用鄰接表存儲(chǔ)結(jié)構(gòu)。

//若G無(wú)回路，則輸出G的頂點(diǎn)的一個(gè)拓?fù)湫蛄胁⒎祷豋K，否則ERROR。

FindInDegree(G,indegree);//對(duì)各頂點(diǎn)求入度indegree[0..vernum-1]

InitStack(S);for(i=0;i<G.vexnum;++i)//建零入度頂點(diǎn)棧S

if(!indegree[i])Push(S,i);

//入度為0者進(jìn)棧

count=0;//對(duì)輸出頂點(diǎn)計(jì)數(shù)

while(!StackEmpty(S)){Pop(S,i);printf(i,G,vertices[i].data);++count;//輸出i號(hào)頂點(diǎn)并計(jì)數(shù)

for(p=G.vertices[i].firstarc;p;p=p->nextarc){k=p->adjvex;//對(duì)i號(hào)頂點(diǎn)的每個(gè)鄰接點(diǎn)的入度減1

if(!(--indegree[k]))Push(S,k);

//若入度減為0，則入棧

}//for}//whileif(count<G.vexnum)returnERROR;//該有向圖有回路

elsereturnOK;}//TopologicalSort算法分析求各頂點(diǎn)入度：O(e)建零入度頂點(diǎn)棧：O(n)while中入度減1操作：

O(e)拓?fù)渑判颍篢(n)=O(n+e)3.關(guān)鍵路徑問(wèn)題提出把工程計(jì)劃表示為有向圖，用頂點(diǎn)表示事件，弧表示活動(dòng)；每個(gè)事件表示在它之前的活動(dòng)已完成，在它之后的活動(dòng)可以開(kāi)始.例設(shè)一個(gè)工程有11項(xiàng)活動(dòng)，9個(gè)事件

事件V1——表示整個(gè)工程開(kāi)始

事件V9——表示整個(gè)工程結(jié)束問(wèn)題：（1）完成整項(xiàng)工程至少需要多少時(shí)間？（2）哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵？987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4AOE網(wǎng)AOE網(wǎng)(ActivityOnEdge)——也叫邊表示活動(dòng)的網(wǎng)。AOE網(wǎng)是一個(gè)帶權(quán)的有向無(wú)環(huán)圖，其中頂點(diǎn)表示事件，弧表示活動(dòng)，權(quán)表示活動(dòng)持續(xù)時(shí)間路徑長(zhǎng)度——路徑上各活動(dòng)持續(xù)時(shí)間之和關(guān)鍵路徑——路徑長(zhǎng)度最長(zhǎng)的路徑Ve(j)——表示事件Vj的最早發(fā)生時(shí)間Vl(j)——表示事件Vj的最遲發(fā)生時(shí)間e(i)——表示活動(dòng)ai的最早開(kāi)始時(shí)間l(i)——表示活動(dòng)ai的最遲開(kāi)始時(shí)間l(i)-e(i)——表示完成活動(dòng)ai的時(shí)間余量關(guān)鍵活動(dòng)——關(guān)鍵路徑上的活動(dòng)，即l(i)=e(i)的活動(dòng)987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4問(wèn)題分析如何找e(i)=l(i)的關(guān)鍵活動(dòng)？設(shè)活動(dòng)ai用弧<j,k>表示，其持續(xù)時(shí)間記為：dut(<j,k>)則有：（1）e(i)=Ve(j)

（2）l(i)=Vl(k)-dut(<j,k>)jkai如何求Ve(j)和Vl(j)？(1)從Ve(1)=0開(kāi)始向前遞推(2)從Vl(n)=Ve(n)開(kāi)始向后遞推987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4求關(guān)鍵路徑步驟求Ve(i)求Vl(j)求e(i)求l(i)計(jì)算l(i)-e(i)987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4V1V2V3V4V5V6V7V8V9頂點(diǎn)Ve

Vl0645771614180668710161418a1a2a3a4a5a6a7a8a9a10a11活動(dòng)ell-e00002266046258377077071031616014140033

算法實(shí)現(xiàn)輸入頂點(diǎn)和弧信息，建立其鄰接表計(jì)算每個(gè)頂點(diǎn)的入度對(duì)其進(jìn)行拓?fù)渑判蚺判蜻^(guò)程中求頂點(diǎn)的Ve[i]

將得到的拓?fù)湫蛄羞M(jìn)棧按逆拓?fù)湫蛄星箜旤c(diǎn)的Vl[i]計(jì)算每條弧的e[i]和l[i],找出e[i]=l[i]的關(guān)鍵活動(dòng)時(shí)間復(fù)雜度為O(n+e)StatusTopologicalOrder(ALGraphG,SqStack&T){//有向圖G采用鄰接表存儲(chǔ)結(jié)構(gòu)，求各頂點(diǎn)事件的最早發(fā)生時(shí)間ve（全局變量）。//T為拓?fù)湫蛄许旤c(diǎn)棧，S為零入度頂點(diǎn)棧。//如果G無(wú)回路，則用棧T返回G的一個(gè)拓?fù)湫蛄校液瘮?shù)值為OK，否則為ERROR。FindInDegree(G,indegree);//對(duì)各頂點(diǎn)求入度indegree[0..vernum-1]InitStack(S);//初始化零入度頂點(diǎn)棧Sfor(i=0;i<G.vexnum;++i)//建立零入度頂點(diǎn)棧Sif(!indegree[i])Push(S,i);

//入度為0的頂點(diǎn)序號(hào)入棧InitStack(T);//初始化拓?fù)湫蛄许旤c(diǎn)棧Tcount=0;//初始化輸出頂點(diǎn)計(jì)數(shù)器ve[0..G.vexnum-1]=0;//設(shè)各頂點(diǎn)最早發(fā)生時(shí)間為0while(!StackEmpty(S)){

Pop(S,j);Push(T,j);++count;

//j號(hào)頂點(diǎn)入T棧并計(jì)數(shù)

for(p=G.vertices[j].firstarc;p;p=p->nextarc) { k=p->adjvex;//對(duì)j號(hào)頂點(diǎn)的每個(gè)鄰接點(diǎn)入度減1 if(!(--indegree[k]))Push(S,k);//若入度減為0，則入棧

if(ve[j]+*(p->info)>ve[k])

//求各頂點(diǎn)的最早發(fā)生時(shí)間

ve[k]=ve[j]+*(p->info)；

}//for結(jié)束}//while結(jié)束if(count<G.vexnum)returnERROR;//該有向網(wǎng)有回路elsereturnOK;}//ToptlogicalOrderStatusCriticalPath(ALGraphG){//G為有向網(wǎng)，輸出G的各項(xiàng)關(guān)鍵活動(dòng)。if(!TopologicalOrder(G,T))returnERROR;vl[0..G.vexnum-1]=ve[G.vexnum-1];//初始化頂點(diǎn)事件最遲發(fā)生時(shí)間while(!StackEmpty(T))//按拓?fù)淠嫘蚯蟾黜旤c(diǎn)的vl

值

for(Pop(T,j),p=G.vertices[j].firstarc;p;p=p->nextarc){k=p->adjvex;dut=*(p->info); //dut

是事件vj

到事件vk

活動(dòng)持續(xù)時(shí)間，即dut<j,k>

if(vl[k]–dut<vl[j])vl[j]=vl[k]–dut; }//for結(jié)束for(j=0;j<G.vexnum;++j)

//求活動(dòng)的最早開(kāi)始時(shí)間ee、最遲開(kāi)始時(shí)間el和關(guān)鍵活動(dòng)for(p=G.vertices[j].firstarc;p;p=p->nextarc){ k=p->adjvex;dut=*(p->info);

ee=ve[j];el=vl[k]–dut; tag=(ee==el)?￠*￠:￠￠;

printf(j,k,dut,ee,el,tag);//輸出關(guān)鍵活動(dòng)}//for(p=G.vertices[j].firstarc)結(jié)束}//CriticalPath987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4inlinkvexnextvexdatalength123456789123456789011121122263445^79^51^62^51^87^84^92^94^4.算法實(shí)現(xiàn)圖用帶權(quán)鄰接矩陣存儲(chǔ)ad[][]數(shù)組dist[]存放當(dāng)前找到的從源點(diǎn)V0到每個(gè)終點(diǎn)的最短路徑長(zhǎng)度，其初態(tài)為圖中直接路徑權(quán)值數(shù)組pre[]表示從V0到各終點(diǎn)的最短路徑上，此頂點(diǎn)的前一頂點(diǎn)的序號(hào)；若從V0到某終點(diǎn)無(wú)路徑，則用0作為其前一頂點(diǎn)的序號(hào)516432085623013717329dist012345601383032pre01234560000000(1)k=1113212220111931214111長(zhǎng)度最短路徑13<V0,V1>8<V0,V2>13<V0,V2,V3>19<V0,V2,V3,V4>21<V0,V2V3,V4,V5>20<V0,V1,V6>算法分析：T(n)=O(n2)算法7.15——Dijkstra

算法求最短路徑voidShortestPath_DIJ(MGraphG,intv0,PathMatrix&p,ShortPathTable&D){

//用Dijkstra

算法求有向網(wǎng)G的v0頂點(diǎn)到其余頂點(diǎn)v的最短路//p[v]及其帶權(quán)長(zhǎng)度D[v]。若p[v][w]為T(mén)RUE，則w是從v0到v

//當(dāng)前求得最短路徑上的頂點(diǎn)。final[v]為T(mén)RUE當(dāng)且僅當(dāng)v∈S,

//即已經(jīng)求得v0到v的最短路徑。

for(v=0;v<G.vexnum;++v){final[v]=FALSE;D[v]=G.arcs[v0][v];for(w=0;w<G.vexnum;++w)P[v][w]=FALSE;//設(shè)空路徑

if(D[v]<INFINITY){P[v][v0]=TRUE;P[v][v]=TRUE;}}//forD[v0]=0;final[v0]=TRUE;//初始化，v0頂點(diǎn)屬于S集

//開(kāi)始主循環(huán)，每次求得v0到某個(gè)v頂點(diǎn)的最短路徑，并加v到S集

for(i=1;i<G.vexnum;++i){//其余G.vexnum-1個(gè)頂點(diǎn)

min=INFINITY;//當(dāng)前所知離v0頂點(diǎn)的最近距離

for(w=0;w<G.vexnum;++w)if(!final[w])if(D[w]<min){v=w;min=D[w];}//w頂點(diǎn)離v0頂點(diǎn)更近

final[v]=TRUE;//離v0頂點(diǎn)最近的v加入S集

for(w=0;w<G.vexnum;++w)//更新當(dāng)前最短路徑及距離

if(!final[w]&&(min+G.arcs[v][w]<D[w])){

//修改D[w]和P[w],w∈V-SD[w]=min+G.arcs[v][w];P[w]=P[v];P[w][P]=TRUE;//P[w]=P[v]+[w]}//if}//for}//ShortestPath_DIJ7.6.2每一對(duì)頂點(diǎn)之間的最短路徑方法一每次以一個(gè)頂點(diǎn)為源點(diǎn)，重復(fù)執(zhí)行Dijkstra算法n次——T(n)=O(n3)2.方法二：弗洛伊德(Floyd)算法【算法思想】

逐個(gè)頂點(diǎn)試探法【求最短路徑步驟】初始時(shí)設(shè)置一個(gè)n階方陣，令其對(duì)角線(xiàn)元素為0，若存在弧<Vi,Vj>，則對(duì)應(yīng)元素為權(quán)值；否則為逐步試著在原直接路徑中增加中間頂點(diǎn)，若加入中間點(diǎn)后路徑變短，則修改之；否則，維持原值所有頂點(diǎn)試探完畢，算法結(jié)束例ACB264311041160230初始：路徑：ABACBABCCA046602370加入B：路徑：ABABCBABCCACAB0411602370加入A：路徑：ABACBABCCACAB046502370加入C：路徑：ABABCBCABCCACAB【算法實(shí)現(xiàn)】圖用鄰接矩陣存儲(chǔ)length[][]存放最短路徑長(zhǎng)度path[i][j]是從Vi到Vj的最短路徑上Vj前一頂點(diǎn)序號(hào)【算法描述(算法7.16)】voidshortestPath_FLOYD(MGrgph

G,PathMatrix&p[],DistancMatrix&D){

//用Floyd算法求得有向網(wǎng)G中各對(duì)頂點(diǎn)v和w之間的最短//路徑P[v][w]及其帶權(quán)長(zhǎng)度D[v][w]。若P[v][w][u]為//TRUE，則u是從v到w當(dāng)前求得最短路徑上的頂點(diǎn)

for(v=0;v<G.vexnum;++v)

//各對(duì)結(jié)點(diǎn)之間初始已知路徑及距離

for(w=0;w<G.vexnum;++w){D[v][w]=G.arcs[v][w];for(u=0;u<G.vexnum;++u)P[v][w][u]=FLASE;if(D[v][w]<INFINITY){//從v到w有直接路徑

P[v][w][v]=TRUE；P[v][w][w]=TRUE;}//if}//forfor(u=0;u<G.vexnum;++u)for(v=0;v<G.vexnum;++v)for(w=0;w<G.vexnum;++w)if(D[v][u]+D[u][w]<D[v][w]){//從v到u到w的一條路徑更短

D[v][w]=D[v][u]+D[u][w];for(i=0;i<G.vexnum;++i)p[v][w][i]=P[v][u][i]||P[u][w][i];}//if}ShortestPath_FLOYD例132264311初始：041160230length=1231231-1

3path=加入V1：0411602370length=12312311

2path=加入V2：046602370length=12212311

3path=加入V3：046502370length=02232311

3path=算法分析：T(n)=O(n3)實(shí)驗(yàn)4最小生成樹(shù)在N個(gè)城市之間建設(shè)通信網(wǎng)絡(luò)，以最低經(jīng)濟(jì)代價(jià)建設(shè)這個(gè)通信網(wǎng)。輸入：nm（n個(gè)城市，m條邊,00表示結(jié)束）45AB2BC3AC6CD7AD10輸出：最小生成樹(shù)，頂點(diǎn)和邊的權(quán)值。要求：使用Prim算法實(shí)現(xiàn)存儲(chǔ)結(jié)構(gòu)采用：鄰接表圖的知識(shí)回顧

1.

圖的基本概念有向圖、無(wú)向圖、完全圖、稀疏圖、稠密圖；度、鄰接點(diǎn)、弧、邊、權(quán)；路徑；連通圖與連通分量；生成樹(shù)與最小生成樹(shù)2.

圖的存儲(chǔ)結(jié)構(gòu)

鄰接矩陣：二維數(shù)組、順序存儲(chǔ)；

鄰接表：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，為每個(gè)頂點(diǎn)建立一個(gè)單鏈表；

十字鏈表：有向圖的另一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)；

鄰接多重表：無(wú)向圖的另一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)3.

圖的遍歷深度優(yōu)先搜索；廣度優(yōu)先搜索

4.

圖的連通性最小生成樹(shù)：普里姆算法：時(shí)間復(fù)雜度O（n2），與網(wǎng)中的邊無(wú)關(guān)，適合求邊稠密的網(wǎng)；克魯斯卡爾算法：時(shí)間復(fù)雜度O（eloge），與邊數(shù)有關(guān)，適合求邊稀疏的網(wǎng)5.有向無(wú)環(huán)圖及其應(yīng)用AOV網(wǎng)：頂點(diǎn)表示活動(dòng)、弧表示活動(dòng)之間優(yōu)先關(guān)系的有向圖；拓?fù)渑判颍簩⑺谢顒?dòng)排列成一個(gè)線(xiàn)性序列；AOE網(wǎng)：弧表示活動(dòng)、權(quán)表示活動(dòng)持續(xù)時(shí)間的帶權(quán)的有向無(wú)環(huán)圖；關(guān)鍵路徑：AOE網(wǎng)中帶權(quán)路徑最長(zhǎng)的路徑，用來(lái)估算工程完成時(shí)間6.最短路徑迪杰斯特拉Dijkstra算法：求從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑；弗洛易德Floyd算法：求每一對(duì)頂點(diǎn)之間的最短路徑圖的鄰接矩陣存儲(chǔ)表示：

#defineINFINITYINT_MAX//

最大值∞

#defineMAX_VERTEX_NUM20//最大頂點(diǎn)個(gè)數(shù)

typedef

enum{DG,DN,UDG,UDN}GraphKind;//{有向圖,有向網(wǎng),無(wú)向圖,無(wú)向網(wǎng)}

typedef

struct

ArcCell{

VRType

adj;//

VRType是頂點(diǎn)關(guān)系類(lèi)型。對(duì)無(wú)權(quán)圖，用1或0表示相鄰否；

//

對(duì)帶權(quán)圖，則為權(quán)值類(lèi)型。

InfoType*info;//該弧相關(guān)信息的指針

}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef

struct{

VertexType

vexs[MAX_VERTEX_NUM];//頂點(diǎn)向量

AdjMatrixarcs;//鄰接矩陣

int

vexnum,arcnum;//圖的當(dāng)前頂點(diǎn)數(shù)和弧(邊)數(shù)

GraphKindkind;//圖的種類(lèi)標(biāo)志

}MGraph;構(gòu)造一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向網(wǎng)的時(shí)間復(fù)雜度為O（n2+e*n），其中O（n2）用于對(duì)鄰接矩陣初始化。簡(jiǎn)單化類(lèi)型定義：#defineMAX20typedef

int

vextype;typedef

struct{

vextypevex[MAX];

intarcs[MAX][MAX];}mgraph;圖的鄰接表存儲(chǔ)表示：#defineMAX_VERTEX_NUM20//最大頂點(diǎn)個(gè)數(shù)typedef

struct

ArcNode{int

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

struct

ArcNode*nextarc;//指示下一條邊或弧的指針

InfoType*info;//該弧相關(guān)信息的指針}ArcNode;typedef

struct

VNode{VertexTypedata;//頂點(diǎn)信息

ArcNode*firstarc;//指向第一條依附該頂點(diǎn)的弧的指針}Vnode，AdjList[MAX_VERTEX_NUM];typedef

struct{

AdjListvertices;//鄰接表

int

vexnum,arcnum;//圖的當(dāng)前頂點(diǎn)數(shù)和弧(邊)數(shù)

intkind;//圖的種類(lèi)標(biāo)志

}ALGraph;

#defineMAX_VERTEX_NUM20

typedef

emnu{unvisited,visited}VisitIf;

typedef

struct

Ebox{

VisitIfmark;//

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

int

ivex,jvex;//該邊依附的兩個(gè)頂點(diǎn)的位置

struct

EBox*ilink,*jlink;//分別指向依附這兩個(gè)頂點(diǎn)的下一條邊

InfoType*info;//該邊信息指針

}EBox;

typedef

struct

VexBox{

VertexTypedata;

EBox*firstedge;//

指向第一條依附該頂點(diǎn)的邊

}VexBox;

typedef

struct{

VexBox

adjmulist[MAX_VERTEX_NUM];

int

vexnum,edgenum;//無(wú)向圖的當(dāng)前頂點(diǎn)數(shù)和邊數(shù)

}AMLGraph;算法7.7生成非連通圖的深度優(yōu)先生成森林voidDFSForest(Graph

G,CSTree&T){

//建立無(wú)向圖G的深度優(yōu)先生成森林的（最左）孩子（右）兄弟鏈表TT=NULL;for(v=0;v<G.vexnum;++v)visited[v]=FALSE;for(v=0;v<G.vexnum;++v)if(!visited[v]){//第v頂點(diǎn)為新的生成樹(shù)的根結(jié)點(diǎn)

p=(CSTree)malloc(sizeof(CSNode));//分配根結(jié)點(diǎn)*p={GetVex(G,v),NULL,NULL};//給該結(jié)點(diǎn)賦值

if(!T)T=p;//是第一棵生成樹(shù)的根（T的根）

elseq->nextsibling=p;//是其它生成樹(shù)的根

q=p;//q指示當(dāng)前生成樹(shù)的根

DFSTree(G,v,p);

//建立以p為根的生成樹(shù)

}}//DFSForest算法7.8voidDFSTree(Graph

G,int

v,CSTree&T){

//從第v個(gè)頂點(diǎn)出發(fā)濃深度優(yōu)先遍歷圖G，建立以T為根的生成樹(shù)。

visited[v]=TRUE;first=TRUE;for(w=FistAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))if(!visited[w]){p=(CSTree)malloc(sizeof(CSNode));//分配孩子結(jié)點(diǎn)*p={GetVex(G,w),NULL,NULL};if(first){//w是v的第一個(gè)未被訪(fǎng)問(wèn)的鄰接頂點(diǎn)