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

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

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

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

二叉樹的先序遍歷）樹的后根遍歷（=

二叉樹的中序遍歷）森林的先序遍歷（=

二叉樹的先序遍歷）森林的中序遍歷（=

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

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

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

3．熟練掌握圖的兩種遍歷算法。

4．理解各種圖的應用問題的算法。

【重點和難點】理解各種圖的算法及其應用場合。

【知識點】圖的類型定義、圖的存儲表示、圖的深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷、無向網(wǎng)的最小生成樹、最短路徑、拓撲排序、關(guān)鍵路徑7.1圖的定義和術(shù)語

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

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

則稱G‘為G的子圖0123子圖0130123023356例245136圖與子圖權(quán)(Weight)——與圖的邊或弧相關(guān)的數(shù),可以表示兩個頂點之間的距離或耗費網(wǎng)——帶權(quán)的圖上?！本┰趺醋咦顑?yōu)?

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

和從Vj到

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

ADTGraph{

數(shù)據(jù)對象V：V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點集。

數(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)的建立和銷毀:

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

DestroyGraph(&G);//銷毀圖G對頂點的訪問操作:

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

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

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

對鄰接點的操作:

FirstAdjVex(G,v);//返回v的第一個鄰接點。若該頂點在G中沒有鄰接點，則返回“空”

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

插入或刪除頂點:

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

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

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

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

遍歷:

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

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

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

nextarc1234acdbdatafirstarc4212^^^adjvex

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

nextarc1234acdbdatafirstarc4212^^^adjvex

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

markivex

ilink

jvex

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

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

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

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

從頂點i

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

dataFirstout例aecbd1234acdb5e1214

34323552^^^^^

markivex

ilink

jvex

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

ilink、

jlink：分別指向下一條依附頂點ivex

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

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

◆復雜性：圖的任意頂點可能和其余的頂點相鄰接，可能在訪問了某個頂點后，沿某條路徑搜索后又回到原頂點。

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

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

廣度優(yōu)先搜索(BreadthFirstSearch--BFS)遍歷類似樹的按層次遍歷的過程。

算法思想:⑴從圖中某個頂點vi出發(fā)，訪問vi；⑵訪問vi的所有相鄰接且未被訪問的所有頂點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)先搜索

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

圖的定義和術(shù)語7.2圖的存儲結(jié)構(gòu)7.3圖的遍歷7.4最小生成樹7.5最短路徑小結(jié)第七章圖欲在n個城市間建立通信網(wǎng)，則n個城市應鋪n-1條線路；但因為每條線路都會有對應的經(jīng)濟成本，而n個城市可能有n(n-1)/2條線路，那么，如何選擇n–1條線路使總費用最少？典型用途：先建立數(shù)學模型：頂點———表示城市，有n個；邊————表示線路，有n–1條；邊的權(quán)值—表示線路的經(jīng)濟代價；連通網(wǎng)——表示n個城市間的通信網(wǎng)。顯然此連通網(wǎng)是一棵生成樹！問題抽象：

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

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

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

——歸并頂點，時間復雜度O(n2)方法二：克魯斯卡爾算法

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

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

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

設(shè)一有向圖G=（V,E），已知各邊的權(quán)值，以某指定點v0為源點，求從v0到圖的其余各點的最短路徑。例1：源點從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的最短路徑是哪條？迪杰斯特拉算法思想：按路徑長度遞增次序產(chǎn)生最短路徑把圖中的頂點V分成兩組：（1）S：已求出最短路徑的頂點的集合（2）V-S=T：尚未確定最短路徑的頂點集合例：下圖中從源點V0到其余各頂點的最短路徑51643208562301371732913長度最短路徑<V0,V1><V0,V2><V0,V2,V3><V0,V2,V3,V4><V0,V2,V3,V4,V5><V0,V1,V6>8131921203.求最短路徑步驟初始時令S={V0},T={其余頂點}，T中頂點對應的距離值：若存在<V0,Vi>，為<V0,Vi>弧上的權(quán)值若不存在<V0,Vi>，為從T中選取一個其距離值為最小的頂點W，加入S對T中頂點的距離值進行修改：若加進W作中間頂點，從V0到Vi的距離值比不加W的路徑要短，則修改此距離值重復上述步驟，直到S中包含所有頂點，即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>終點從V0到各終點的最短路徑及其長度V1V2V3V4V5V6Vj--------------------------------21<V0,V2,V3,V4,V5>20<V0,V1,V6>V6:20<V0,V1,V6>516432085623013717329例：求F到各頂點最短路徑7.6

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

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

一個無環(huán)的有向圖，簡稱DAG圖。

作用：是描述一項工程進行過程的有效工具。主要進行拓撲排序和關(guān)鍵路徑的操作。

V1V2V4V3V5DAGV3V1V2DG2.拓撲排序問題提出：

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

課程代號課程名稱先修課C1C2C3C4C5C6C7C8C9C10C11C12無C1C1,C2C1C3,C4C11C3.C5C3,C6無C9C9C1,C9,C10程序設(shè)計基礎(chǔ)離散數(shù)學數(shù)據(jù)結(jié)構(gòu)匯編語言程序設(shè)計方法學計算機原理編譯原理操作系統(tǒng)高等數(shù)學線性代數(shù)普通物理數(shù)值分析拓撲排序：由某個集合上的一個偏序得到該集合上的一個全序的操作。答案：采用拓撲排序例課程代號課程名稱先修課C1C2C3C4C5C6C7C8C9C10C11C12無C1C1,C2C1C3,C4C11C3.C5C3,C6無C9C9C1,C9,C10程序設(shè)計基礎(chǔ)離散數(shù)學數(shù)據(jù)結(jié)構(gòu)匯編語言程序設(shè)計方法學計算機原理編譯原理操作系統(tǒng)高等數(shù)學線性代數(shù)普通物理數(shù)值分析C1C2C3C4C5C6C7C8C9C10C11C12例：建立表示課程之間優(yōu)先關(guān)系的有向圖頂點——表示課程有向弧——表示先決條件，若課程i是課程j的先決條件，則圖中有弧<i,j>AOV網(wǎng)AOV網(wǎng)——用頂點表示活動，用弧表示活動間優(yōu)先關(guān)系的有向圖稱為頂點表示活動的網(wǎng)(ActivityOnVertexnetwork)，簡稱AOV網(wǎng)若<vi,vj>是圖中有向邊，則vi是vj的直接前驅(qū)；vj是vi的直接后繼AOV網(wǎng)中不允許有回路，這意味著某項活動以自己為先決條件拓撲排序——把AOV網(wǎng)絡(luò)中各頂點按照它們相互之間的優(yōu)先關(guān)系排列成一個線性序列的過程檢測AOV網(wǎng)中是否存在環(huán)的方法：對有向圖構(gòu)造其頂點的拓撲有序序列，若網(wǎng)中所有頂點都在它的拓撲有序序列中，則該AOV網(wǎng)必定不存在環(huán)拓撲排序的方法在有向圖中選一個沒有前驅(qū)的頂點且輸出之從圖中刪除該頂點和所有以它為尾的弧重復上述兩步，直至全部頂點均已輸出；或者當圖中不存在無前驅(qū)的頂點為止動畫演示C1C2C3C4C5C6C7C8C9C10C11C12拓撲序列：C1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12--C8或：C9--C10--C11--C6--C1--C12--C4--C2--C3--C5--C7--C8一個AOV網(wǎng)的拓撲序列不是唯一的算法實現(xiàn)以鄰接表作存儲結(jié)構(gòu)把鄰接表中所有入度為0的頂點進棧棧非空時，輸出棧頂元素Vj并退棧；在鄰接表中查找Vj的直接后繼Vk，把Vk的入度減1；若Vk的入度為0則進棧重復上述操作直至棧空為止。若?？諘r輸出的頂點個數(shù)不是n，則有向圖有環(huán)；否則，拓撲排序完畢算法7.12StatusTopologicalSort(ALGraphG){//有向圖G采用鄰接表存儲結(jié)構(gòu)。

//若G無回路，則輸出G的頂點的一個拓撲序列并返回OK，否則ERROR。

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

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

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

//入度為0者進棧

count=0;//對輸出頂點計數(shù)

while(!StackEmpty(S)){Pop(S,i);printf(i,G,vertices[i].data);++count;//輸出i號頂點并計數(shù)

for(p=G.vertices[i].firstarc;p;p=p->nextarc){k=p->adjvex;//對i號頂點的每個鄰接點的入度減1

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

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

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

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

O(e)拓撲排序：T(n)=O(n+e)3.關(guān)鍵路徑問題提出把工程計劃表示為有向圖，用頂點表示事件，弧表示活動；每個事件表示在它之前的活動已完成，在它之后的活動可以開始.例設(shè)一個工程有11項活動，9個事件

事件V1——表示整個工程開始

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

Vl0645771614180668710161418a1a2a3a4a5a6a7a8a9a10a11活動ell-e00002266046258377077071031616014140033

算法實現(xiàn)輸入頂點和弧信息，建立其鄰接表計算每個頂點的入度對其進行拓撲排序排序過程中求頂點的Ve[i]

將得到的拓撲序列進棧按逆拓撲序列求頂點的Vl[i]計算每條弧的e[i]和l[i],找出e[i]=l[i]的關(guān)鍵活動時間復雜度為O(n+e)StatusTopologicalOrder(ALGraphG,SqStack&T){//有向圖G采用鄰接表存儲結(jié)構(gòu)，求各頂點事件的最早發(fā)生時間ve（全局變量）。//T為拓撲序列頂點棧，S為零入度頂點棧。//如果G無回路，則用棧T返回G的一個拓撲序列，且函數(shù)值為OK，否則為ERROR。FindInDegree(G,indegree);//對各頂點求入度indegree[0..vernum-1]InitStack(S);//初始化零入度頂點棧Sfor(i=0;i<G.vexnum;++i)//建立零入度頂點棧Sif(!indegree[i])Push(S,i);

//入度為0的頂點序號入棧InitStack(T);//初始化拓撲序列頂點棧Tcount=0;//初始化輸出頂點計數(shù)器ve[0..G.vexnum-1]=0;//設(shè)各頂點最早發(fā)生時間為0while(!StackEmpty(S)){

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

//j號頂點入T棧并計數(shù)

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

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

//求各頂點的最早發(fā)生時間

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

}//for結(jié)束}//while結(jié)束if(count<G.vexnum)returnERROR;//該有向網(wǎng)有回路elsereturnOK;}//ToptlogicalOrderStatusCriticalPath(ALGraphG){//G為有向網(wǎng)，輸出G的各項關(guān)鍵活動。if(!TopologicalOrder(G,T))returnERROR;vl[0..G.vexnum-1]=ve[G.vexnum-1];//初始化頂點事件最遲發(fā)生時間while(!StackEmpty(T))//按拓撲逆序求各頂點的vl

值

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

是事件vj

到事件vk

活動持續(xù)時間，即dut<j,k>

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

//求活動的最早開始時間ee、最遲開始時間el和關(guān)鍵活動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)鍵活動}//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.算法實現(xiàn)圖用帶權(quán)鄰接矩陣存儲ad[][]數(shù)組dist[]存放當前找到的從源點V0到每個終點的最短路徑長度，其初態(tài)為圖中直接路徑權(quán)值數(shù)組pre[]表示從V0到各終點的最短路徑上，此頂點的前一頂點的序號；若從V0到某終點無路徑，則用0作為其前一頂點的序號516432085623013717329dist012345601383032pre01234560000000(1)k=1113212220111931214111長度最短路徑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頂點到其余頂點v的最短路//p[v]及其帶權(quán)長度D[v]。若p[v][w]為TRUE，則w是從v0到v

//當前求得最短路徑上的頂點。final[v]為TRUE當且僅當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頂點屬于S集

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

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

min=INFINITY;//當前所知離v0頂點的最近距離

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

final[v]=TRUE;//離v0頂點最近的v加入S集

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

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每一對頂點之間的最短路徑方法一每次以一個頂點為源點，重復執(zhí)行Dijkstra算法n次——T(n)=O(n3)2.方法二：弗洛伊德(Floyd)算法【算法思想】

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

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

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

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

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

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

1.

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

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

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

鄰接表：鏈式存儲結(jié)構(gòu)，為每個頂點建立一個單鏈表；

十字鏈表：有向圖的另一種鏈式存儲結(jié)構(gòu)；

鄰接多重表：無向圖的另一種鏈式存儲結(jié)構(gòu)3.

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

4.

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

#defineINFINITYINT_MAX//

最大值∞

#defineMAX_VERTEX_NUM20//最大頂點個數(shù)

typedef

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

typedef

struct

ArcCell{

VRType

adj;//

VRType是頂點關(guān)系類型。對無權(quán)圖，用1或0表示相鄰否；

//

對帶權(quán)圖，則為權(quán)值類型。

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

}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef

struct{

VertexType

vexs[MAX_VERTEX_NUM];//頂點向量

AdjMatrixarcs;//鄰接矩陣

int

vexnum,arcnum;//圖的當前頂點數(shù)和弧(邊)數(shù)

GraphKindkind;//圖的種類標志

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

int

vextype;typedef

struct{

vextypevex[MAX];

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

struct

ArcNode{int

adjvex;//該弧所指向的頂點的位置

struct

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

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

struct

VNode{VertexTypedata;//頂點信息

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

struct{

AdjListvertices;//鄰接表

int

vexnum,arcnum;//圖的當前頂點數(shù)和弧(邊)數(shù)

intkind;//圖的種類標志

}ALGraph;

#defineMAX_VERTEX_NUM20

typedef

emnu{unvisited,visited}VisitIf;

typedef

struct

Ebox{

VisitIfmark;//

訪問標記

int

ivex,jvex;//該邊依附的兩個頂點的位置

struct

EBox*ilink,*jlink;//分別指向依附這兩個頂點的下一條邊

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

}EBox;

typedef

struct

VexBox{

VertexTypedata;

EBox*firstedge;//

指向第一條依附該頂點的邊

}VexBox;

typedef

struct{

VexBox

adjmulist[MAX_VERTEX_NUM];

int

vexnum,edgenum;//無向圖的當前頂點數(shù)和邊數(shù)

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

G,CSTree&T){

//建立無向圖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頂點為新的生成樹的根結(jié)點

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

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

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

q=p;//q指示當前生成樹的根

DFSTree(G,v,p);

//建立以p為根的生成樹

}}//DFSForest算法7.8voidDFSTree(Graph

G,int

v,CSTree&T){

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

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é)點*p={GetVex(G,w),NULL,NULL};if(first){//w是v的第一個未被訪問的鄰接頂點