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

數(shù)據(jù)結(jié)構(gòu)第七章圖第一頁，共九十九頁，編輯于2023年，星期三2【重點(diǎn)掌握】：圖的兩種遍歷方法：遍歷的定義、深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷的算法；應(yīng)用圖的遍歷算法判斷圖的連通性及求圖的生成樹；

用Prim、Kruskal算法求圖的最小生成樹；用Dijkstra算法求解單源最短路徑問題；用Floyd算法求所有頂點(diǎn)間的最短路徑問題；利用AOV網(wǎng)進(jìn)行拓?fù)渑判?；利用AOE網(wǎng)求關(guān)鍵路徑問題；【掌

握】：掌握?qǐng)D的定義和術(shù)語；圖的各種存儲(chǔ)結(jié)構(gòu)及其構(gòu)造算法、在實(shí)際問題中的求解效率。第二頁，共九十九頁，編輯于2023年，星期三37.3圖的遍歷7.3圖的遍歷：從圖的某頂點(diǎn)出發(fā)，訪問圖中所有頂點(diǎn)，并且每個(gè)頂點(diǎn)僅訪問一次。

圖結(jié)構(gòu)的遍歷復(fù)雜性：（1）在圖結(jié)構(gòu)中，沒有一個(gè)“自然”的首結(jié)點(diǎn)，圖中的任意一個(gè)頂點(diǎn)都可以作為第一個(gè)被訪問的結(jié)點(diǎn)（2）在非連通圖中，從一個(gè)頂點(diǎn)出發(fā)，只能訪問它所在的連通分量上的所有頂點(diǎn)，因此，還需考慮如何選取下一個(gè)出發(fā)點(diǎn)以訪問圖中的其余連通分量（3）在圖結(jié)構(gòu)中，如果有回路存在，那么一個(gè)頂點(diǎn)被訪問后，有可能沿回路又回到該頂點(diǎn)，考慮如何避免重復(fù)訪問（4）在圖結(jié)構(gòu)中，一個(gè)頂點(diǎn)可以和其他多個(gè)頂點(diǎn)鄰接，當(dāng)這樣的頂點(diǎn)訪問過后，考慮如何選取下一個(gè)要訪問的頂點(diǎn)的問題第三頁，共九十九頁，編輯于2023年，星期三4

圖的遍歷方法有深度優(yōu)先遍歷和廣度優(yōu)先遍歷兩種。7.3.1

深度優(yōu)先搜索方法：（1）從圖的某一頂點(diǎn)V0出發(fā)，訪問此頂點(diǎn)；（2）依次從V0的未被訪問的鄰接點(diǎn)出發(fā)，深度優(yōu)先遍歷圖，直至圖中所有和V0相通的頂點(diǎn)都被訪問到。

若此時(shí)圖中尚有頂點(diǎn)未被訪問，則另選圖中一個(gè)未被訪問的頂點(diǎn)作起點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問到。第四頁，共九十九頁，編輯于2023年，星期三5

V0

V7

V6

V5

V4

V3

V2

V1若圖的存儲(chǔ)結(jié)構(gòu)為鄰接表，則訪問鄰接點(diǎn)的順序不唯一，深度優(yōu)先序列不是唯一的

V0

V1

V3

V2

V7

V6

V5

V4

V0,V1,V3,V4,V7,V2,V5,V6,※求圖G以V0為起點(diǎn)的的深度優(yōu)先序列（設(shè)存儲(chǔ)結(jié)構(gòu)為鄰接矩陣）第五頁，共九十九頁，編輯于2023年，星期三6voidDFS(GraphG,intv){/*從第v個(gè)頂點(diǎn)出發(fā)，遞歸地深度優(yōu)先遍歷圖G*//*v是頂點(diǎn)在一維數(shù)組中的位置，假設(shè)G是非空?qǐng)D*/visited[v]=1;Visit(v);/*訪問第v個(gè)頂點(diǎn)*/for(w=FirstAdjVex(G,v);w;w=NextAdjVex(G,v,w))if(!visited[w])DFS(G,w);

/*對(duì)v的尚未訪問的鄰接頂點(diǎn)w遞歸調(diào)用DFS*/}輔助數(shù)組：intvisited[Max_Vertex_Num];訪問標(biāo)志數(shù)組,全局變量，初始時(shí)所有分量全為0，visited[v]=1表示頂點(diǎn)v已被訪問.visited01234……00000深度優(yōu)先遍歷算法:7.3圖的遍歷第六頁，共九十九頁，編輯于2023年，星期三77.3圖的遍歷在鄰接表存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)深度優(yōu)先搜索:voidDFSTraverseAL(ALGraphG)/*深度優(yōu)先遍歷以鄰接表存儲(chǔ)的圖G*/{inti;for(i=0;i<G.vexnum;++i)visited[i]=0;/*標(biāo)志數(shù)組初始化*/for(i=0;i<G.vexnum;++i)if(!visited[i])DFSAL(G,i);/*Vi未訪問過，從Vi開始DFS搜索*/}第七頁，共九十九頁，編輯于2023年，星期三8voidDFSAL(ALGraphG,inti){/*從第v個(gè)頂點(diǎn)出發(fā)，遞歸地深度優(yōu)先遍歷圖G*//*v是頂點(diǎn)的序號(hào)，假設(shè)G是用鄰接表存儲(chǔ)*/

EdgeNode*p;

intw;visited[i]=1;Visit(i);/*訪問第v個(gè)頂點(diǎn)*/for(p=G.vertices[i].firstarc;p;p=p->nextarc){w=p->adjvex;/*w是v的鄰接頂點(diǎn)的序號(hào)*/if(!visited[w])DFSAL(G,w);

/*若w尚未訪問,遞歸調(diào)用DFS*/}}/*DFSAL*/7.3圖的遍歷第八頁，共九十九頁，編輯于2023年，星期三9

在遍歷時(shí)，對(duì)圖中每個(gè)頂點(diǎn)至多調(diào)用一次DFS函數(shù)，因?yàn)橐坏┠硞€(gè)頂點(diǎn)被標(biāo)志成已被訪問，就不再從它出發(fā)進(jìn)行搜索。因此，遍歷圖的過程實(shí)質(zhì)上是對(duì)每個(gè)頂點(diǎn)查找其鄰接點(diǎn)的過程。其耗費(fèi)的時(shí)間則取決于所采用的存儲(chǔ)結(jié)構(gòu)。

用鄰接矩陣做圖的存儲(chǔ)結(jié)構(gòu)時(shí)，查找各個(gè)頂點(diǎn)的鄰接點(diǎn)所需的時(shí)間為O(n2)，其中n為圖中頂點(diǎn)數(shù)。當(dāng)以鄰接矩陣做存儲(chǔ)結(jié)構(gòu)時(shí)，深度優(yōu)先搜索遍歷圖的時(shí)間復(fù)雜度為O(n2+n)。

當(dāng)以鄰接表做圖的存儲(chǔ)結(jié)構(gòu)時(shí)，找鄰接點(diǎn)所需時(shí)間為O(e)，其中e為無向圖中邊的數(shù)或有向圖中弧的數(shù)。因此，當(dāng)以鄰接表做存儲(chǔ)結(jié)構(gòu)時(shí)，深度優(yōu)先搜索遍歷圖的時(shí)間復(fù)雜度為O(n+e)。7.3圖的遍歷第九頁，共九十九頁，編輯于2023年，星期三10圖中某頂點(diǎn)v出發(fā)：1）訪問頂點(diǎn)v；2）訪問v的所有未被訪問的鄰接點(diǎn)w1,w2,…wk

；3）依次從這些鄰接點(diǎn)出發(fā)，訪問它們的所有未被訪問的鄰接點(diǎn);依此類推，直到圖中所有訪問過的頂點(diǎn)的鄰接點(diǎn)都被訪問；7.3.2

廣度優(yōu)先遍歷7.3圖的遍歷第十頁，共九十九頁，編輯于2023年，星期三11

V0

V7

V6

V5

V4

V3

V2

V1V0,V1,V2,V3,V4,V7,V5,V6

V0

V1

V3

V2

V7

V6

V5

V4若圖的存儲(chǔ)結(jié)構(gòu)為鄰接表，則訪問鄰接點(diǎn)的順序不唯一，深度優(yōu)先序列不是唯一的※求圖G以V0為起點(diǎn)的的廣度優(yōu)先序列（設(shè)存儲(chǔ)結(jié)構(gòu)為鄰接矩陣）∵先被訪問的頂點(diǎn)，其鄰接點(diǎn)也要先被訪問∴設(shè)一隊(duì)列保存已訪問的頂點(diǎn)第十一頁，共九十九頁，編輯于2023年，星期三12Q※在鄰接表存儲(chǔ)結(jié)構(gòu)上的廣度優(yōu)先搜索V0V1V2V3V4V7V5V6V1V2V3V0V4V7V5V6V0V7V6V5V4V3V2V17.3圖的遍歷7012V0V2V3V1datafirstarc01^^adjvexnext3V430511^274564V5V6V72^62^51^47^6^第十二頁，共九十九頁，編輯于2023年，星期三13voidBFSTraverse(MGraphG)/*從v出發(fā)，廣度優(yōu)先遍歷連通圖G*//*使用輔助隊(duì)列Q和訪問標(biāo)志數(shù)組visited*/{for(v=0;v<G.vexnum;++i)visited[v]=0;InitQueue(Q,G.vexnum);/*初始化空的輔助隊(duì)列Q*/for(v=0;v<G.vexnum;++v){if(!visited[v])/*若v尚未訪問*/

{visited[v]=1;Visit(v);EnQueue(Q,v); while(!QueueEmpty_Sq(Q)) {DeQueue(Q,u);/*隊(duì)頭元素出隊(duì),并賦值給u*/

/*訪問u所有未被訪問的鄰接點(diǎn)*/ for(w=0;w<G.vexnum;w++;) if(G.arcs[u,w].adj&&!visited[w]) {visited[w]=1;Visit(w);EnQueue(Q,w);}}/*while*/

}

}}/*BFSTraverse*/7.3圖的遍歷第十三頁，共九十九頁，編輯于2023年，星期三14第七

章

圖

7.4

連通網(wǎng)的最小生成樹 7.4.1

生成樹7.4.2

最小生成樹7.4.3

構(gòu)造最小生成樹的Prim算法7.4.4

構(gòu)造最小生成樹的Kruskal算法第十四頁，共九十九頁，編輯于2023年，星期三157.4.1

生成樹※生成樹：包含了無向圖G所有頂點(diǎn)的極小連通子圖。1）“極小”含義：一個(gè)有n個(gè)頂點(diǎn)的連通圖的生成樹有n-1條邊，刪除任何一條邊，子圖不再連通；在生成樹中再加一條邊必然形成回路。（生成樹包含了圖中的所有頂點(diǎn)，但只有足以構(gòu)成生成樹的n-1條邊）2）一個(gè)圖可以有許多棵不同的生成樹；3）生成樹中任意兩個(gè)頂點(diǎn)間的路徑是唯一的；4）含n個(gè)頂點(diǎn)n-1條邊的圖不一定是生成樹。7.4最小的生成樹第十五頁，共九十九頁，編輯于2023年，星期三167.4最小的生成樹

生成樹的含義：n個(gè)頂點(diǎn)的圖最多可存在n(n-1)/2條邊線路。求生成樹是為了在網(wǎng)絡(luò)中連通n個(gè)頂點(diǎn)而選擇最少的邊(n－1)。

例如：一個(gè)通信網(wǎng)絡(luò)中，節(jié)點(diǎn)代表了路由器，為了使各路由器之間是連通的（數(shù)據(jù)可達(dá)），且不形成回路(數(shù)據(jù)回到發(fā)送方)，則需建立該網(wǎng)絡(luò)的生成樹。第十六頁，共九十九頁，編輯于2023年，星期三17求生成樹的方法：利用遍歷算法。

從連通圖中的任一頂點(diǎn)出發(fā)進(jìn)行遍歷時(shí)，除出發(fā)點(diǎn)外，其余頂點(diǎn)必須通過一條邊才能到達(dá)，所以遍歷過程中經(jīng)歷的邊有n-1條，它和n個(gè)頂點(diǎn)組成了連通圖的一棵生成樹。

由深度優(yōu)先搜索得到的是深度優(yōu)先生成樹；由廣度優(yōu)先搜索得到的是廣度優(yōu)先生成樹。第十七頁，共九十九頁，編輯于2023年，星期三18V0V7V6V5V4V3V2V1深度遍歷：V0V1V3V4V7V2V5V6V0V7V6V5V4V3V2V17.4最小的生成樹V0V7V6V5V4V3V2V1深度優(yōu)先搜索生成樹第十八頁，共九十九頁，編輯于2023年，星期三19廣度遍歷：V0V1V2V3V4V7V5V6V0V7V6V5V4V3V2V1V0V7V6V5V4V3V2V1廣度優(yōu)先搜索生成樹7.4最小的生成樹V0V7V6V5V4V3V2V1第十九頁，共九十九頁，編輯于2023年，星期三207.4.2

最小生成樹的概念

由生成樹的定義可知，無向連通圖的生成樹不是惟一的。

問題的提出：設(shè)要在n個(gè)城市間建立通信聯(lián)絡(luò)網(wǎng)，頂點(diǎn)—表示城市，權(quán)表示城市間建立通信線路所需花費(fèi)代價(jià)。希望找到一棵生成樹，它的每條邊上的權(quán)值之和（即建立該通信網(wǎng)所需花費(fèi)的總代價(jià)）最小——最小代價(jià)生成樹。7.4最小的生成樹第二十頁，共九十九頁，編輯于2023年，星期三21※最小生成樹定義：對(duì)于一個(gè)網(wǎng)絡(luò)，它的所有生成樹中邊權(quán)值最小的生成樹稱為最小生成樹。

問題分析：n個(gè)城市間建立通信網(wǎng)，如何在可能的線路中選擇n-1條，能把所有城市（頂點(diǎn)）均連起來，且總耗費(fèi)（各邊權(quán)值之和）最小。即：如何在保證n點(diǎn)連通的前題下最節(jié)省經(jīng)費(fèi)?第二十一頁，共九十九頁，編輯于2023年，星期三221.Prim

法基本步驟

設(shè)連通網(wǎng)絡(luò)G={V,E}。集合U存放G的最小生成樹中的頂點(diǎn)，集合T存放最小生成樹之外的頂點(diǎn)。(1)從G中選擇某一頂點(diǎn)u0出發(fā)，在與它關(guān)聯(lián)的邊中選擇一個(gè)邊權(quán)最小的邊(u0,v);將頂點(diǎn)v加入最小生成樹的頂點(diǎn)集合U，在集合T中刪除該頂點(diǎn)；(2)用頂點(diǎn)v到集合T中頂點(diǎn)的邊權(quán)“更新”原集合U中頂點(diǎn)到集合T中頂點(diǎn)的最小邊權(quán)；(3)從一個(gè)頂點(diǎn)在U中，而另一個(gè)頂點(diǎn)在T中的各條邊中選擇權(quán)值最小的邊(u,v),把頂點(diǎn)v加入到集合U

中。(4)重復(fù)(2)、(3)，直到網(wǎng)絡(luò)中的所有頂點(diǎn)都加入到生成樹頂點(diǎn)集合U中為止。7.4.3

構(gòu)造最小生成樹的Prim算法7.4最小的生成樹第二十二頁，共九十九頁，編輯于2023年，星期三23V3V1V4V6V5V2651U={V1}V3V1V4V6V5V251654V3V4V6V5V21V1U={V1,V3}V3V1V4V6V5V216542V3V1V4V6V5V251654U={V1,V3,V6}7.4最小的生成樹V3V1V4V6V5V236521655462.過程演示第二十三頁，共九十九頁，編輯于2023年，星期三24V3V1V4V6V5V216542U={V1,V3,V6,V4

}V3V1V4V6V5V216542U={V1,V3,V6,V4,V2}V3V1V4V6V5V215423U={V1,V3,V6,V4,V2,V5}7.4最小的生成樹V3V1V4V6V5V23652165546Prim算法的時(shí)間復(fù)雜度為O(n2)第二十四頁，共九十九頁，編輯于2023年，星期三257.4.3構(gòu)造最小生成樹的Kruskal算法1.基本思想：按網(wǎng)中權(quán)值遞增的順序構(gòu)造最小生成樹。

2.基本步驟

1）設(shè)連通網(wǎng)G=(V,E)，令最小生成樹初始狀態(tài)是只有n個(gè)頂點(diǎn)而無邊的非連通圖T=(V,)，每個(gè)頂點(diǎn)自成一個(gè)連通分量；2）在E中選取代價(jià)最小的邊，若該邊依附的頂點(diǎn)落在T中不同的連通分量上，則將此邊加入到T中；否則，舍去此邊，選取下一條代價(jià)最小的邊；3）依此類推，直至T中所有頂點(diǎn)都在同一連通分量上為止。7.4最小的生成樹第二十五頁，共九十九頁，編輯于2023年，星期三26V3V1V4V6V5V2V3V4V6V5V21V1V3V1V4V6V5V212V3V1V4V6V5V2123V3V1V4V6V5V2164237.4最小的生成樹V3V1V4V6V5V236521655463.過程演示第二十六頁，共九十九頁，編輯于2023年，星期三27V3V1V4V6V5V2165423V3V1V4V6V5V236521655467.4最小的生成樹Kruskal

算法的時(shí)間復(fù)雜度為O(ne)。第二十七頁，共九十九頁，編輯于2023年，星期三28

7.5單源最短路徑(ShortestPath)

從一個(gè)源點(diǎn)到其他各點(diǎn)的最短路徑第二十八頁，共九十九頁，編輯于2023年，星期三29

交通咨詢系統(tǒng)、通訊網(wǎng)、計(jì)算機(jī)網(wǎng)絡(luò)中經(jīng)常要尋找兩結(jié)點(diǎn)間最短路徑。例如：交通咨詢系統(tǒng)中：咨詢A到B的最短路徑；計(jì)算機(jī)網(wǎng)中如何發(fā)送E-mail才最節(jié)省費(fèi)用（使E-mail由A到B沿最短路徑傳送）。

設(shè)用帶權(quán)的有向圖表示一個(gè)交通運(yùn)輸網(wǎng)，圖中：

頂點(diǎn)——表示城市

邊——表示城市間的交通聯(lián)系

權(quán)——表示此線路的長度或沿此線路運(yùn)輸所花的時(shí)間或費(fèi)用等

這類問題歸結(jié)為從某頂點(diǎn)出發(fā)，沿圖的邊到達(dá)另一頂點(diǎn)所經(jīng)過的路徑中，各邊上權(quán)值之和最小的一條路徑——最短路徑。路徑上的第一個(gè)頂點(diǎn)為源點(diǎn)，最后一個(gè)頂點(diǎn)為終點(diǎn)。

問題的提出:7.5最短路徑第二十九頁，共九十九頁，編輯于2023年，星期三30※最短路徑問題：如果從圖中某一頂點(diǎn)(源點(diǎn))到達(dá)另一頂點(diǎn)(終點(diǎn))的路徑可能不止一條，如何找到一條路徑使沿此路徑上各邊上的權(quán)值總和達(dá)到最小。

第三十頁，共九十九頁，編輯于2023年，星期三31

從一個(gè)源點(diǎn)到其他各點(diǎn)的最短路徑1.

問題的提法：給定一個(gè)帶權(quán)有向圖D與源點(diǎn)v，求從v到D中其它頂點(diǎn)的最短路徑。7.5最短路徑10長度最短路徑<V0,V1><V0,V3><V0,V3,V2>

<V0,V3,V4>3050902.迪杰斯特拉算法（Dijkstra）（1）基本思想

為求得這些最短路徑，Dijkstra提出按路徑長度的遞增次序，逐步產(chǎn)生最短路徑的算法。首先求出長度最短的一條最短路徑，再參照它求出長度次短的一條最短路徑，依此類推，直到從頂點(diǎn)v到其它各頂點(diǎn)的最短路徑全部求出為止。第三十一頁，共九十九頁，編輯于2023年，星期三32依據(jù)算法的基本思想把V分成兩組：（1）S：已求出最短路徑的頂點(diǎn)的集合（2）V-S=T：尚未確定最短路徑的頂點(diǎn)集合

將T中頂點(diǎn)按如下規(guī)則加入到S中：

（1）按遞增的次序產(chǎn)生最短路徑：從源點(diǎn)V0到S中各頂點(diǎn)的最短路徑長度都不大于從V0到T中任何頂點(diǎn)的最短路徑長度;

（2）待求的最短路徑最多以已求出最短路徑的頂點(diǎn)為中間點(diǎn)：從V0到某頂點(diǎn)的最短路徑中，只將S中的頂點(diǎn)作為中間點(diǎn)第三十二頁，共九十九頁，編輯于2023年，星期三33（2）Dijkstra算法的基本步驟

設(shè)V0是源點(diǎn)，初使時(shí)令S={V0},T={其余頂點(diǎn)}，T中頂點(diǎn)對(duì)應(yīng)的距離值若存在，<V0,Vi>邊權(quán)值為<V0,Vi>弧上的權(quán)值；若不存在，<V0,Vi>邊權(quán)值為。1）從T中選取一個(gè)其距離值最小的頂點(diǎn)W，加入S；2）①對(duì)T中頂點(diǎn)的距離值進(jìn)行修改：先求出V0到Vi中間只經(jīng)S中結(jié)點(diǎn)的最短路徑；若加進(jìn)W作中間頂點(diǎn)后從V0到Vi的距離值

比

不加W的路徑要短，則修改此距離值；②上述最短路徑中長度最小者即為下一條長度最短的路徑；③將所求最短路徑的終點(diǎn)加入S中；3）重復(fù)2）直到S中包含所有頂點(diǎn)，即S=V為止。7.5最短路徑第三十三頁，共九十九頁，編輯于2023年，星期三34

1）圖用帶權(quán)鄰接矩陣存儲(chǔ)；2）引入一個(gè)輔助數(shù)組dist。它的每一個(gè)分量dist[i]表示當(dāng)前找到的從源點(diǎn)v0到終點(diǎn)vi

的最短路徑的長度

初始狀態(tài)：若從源點(diǎn)v0到頂點(diǎn)vi有邊，則dist[i]為該邊上的權(quán)值；若從源點(diǎn)v0到頂點(diǎn)vi

沒有邊，則dist[i]為

。3）數(shù)組path[]表示從V0到各終點(diǎn)的最短路徑上，此頂點(diǎn)的前一頂點(diǎn)的序號(hào)；若從V0到某終點(diǎn)無路徑，則用-1

作為該結(jié)點(diǎn)前一頂點(diǎn)的序號(hào)4)數(shù)組s[]標(biāo)識(shí)V0到該結(jié)點(diǎn)的最短路徑是否求出。0表示沒求出，1表示已求出。7.5最短路徑(3)算法實(shí)現(xiàn)第三十四頁，共九十九頁，編輯于2023年，星期三357.5最短路徑260003013501010122601030135010101439000301350001013010000300160001011010000300-1001000P[4]d[4]S[4]P[3]d[3]S[3]P[2]d[2]S[2]P[1]d[1]S[1]頂點(diǎn)4頂點(diǎn)3頂點(diǎn)2頂點(diǎn)1選取點(diǎn)01234第三十五頁，共九十九頁，編輯于2023年，星期三36

如何從表中讀取源點(diǎn)0到終點(diǎn)的最短路徑？

以頂點(diǎn)4為例：(1)V0到頂點(diǎn)4的最短路徑為60。

(2)path[4]=2→path[2]=3→path[3]=0；

反過來排列，得到路徑0,3,2,4，即V0到頂點(diǎn)V4的最短路徑。7.5最短路徑2600030135010101226010301350101014390003013500010130100003001600010110100003000001000P[4]d[4]S[4]P[3]d[3]S[3]P[2]d[2]S[2]P[1]d[1]S[1]頂點(diǎn)4頂點(diǎn)3頂點(diǎn)2頂點(diǎn)1選取點(diǎn)第三十六頁，共九十九頁，編輯于2023年，星期三37※Dijkstra算法的時(shí)間復(fù)雜度為O(n2)第三十七頁，共九十九頁，編輯于2023年，星期三38

7.6AOV網(wǎng)與拓?fù)渑判虻谌隧摚簿攀彭?，編輯?023年，星期三397.6.1有向無環(huán)圖的概念1.

有向無環(huán)圖（directedacyclinegraph）：沒有回路的有向圖。◆含有公共子式的表達(dá)式

例如：表達(dá)式(a+b)*(a+b-e/f)

a

-

+

b*/ef用有向無環(huán)圖表示的表達(dá)式◆流程圖：

工程流程、生產(chǎn)過程中工序流程、程序流程、課程的流程。常用的兩種有向無環(huán)圖是：AOV網(wǎng)，AOE網(wǎng)。7.6有向無環(huán)圖及其應(yīng)用

-

a

+

b*/ef

a

+

b用二叉樹表示的表達(dá)式第三十九頁，共九十九頁，編輯于2023年，星期三407.6.2AOV網(wǎng)與拓?fù)渑判?.AOV網(wǎng)

(ActivityOnVertexnetwork)

用頂點(diǎn)表示活動(dòng)，邊表示活動(dòng)的順序關(guān)系的有向圖稱為AOV網(wǎng)。

在AOV網(wǎng)中，若從頂點(diǎn)i到頂點(diǎn)j有一條有向路徑。則頂點(diǎn)i是頂點(diǎn)j的前驅(qū)，j是i的后繼。若<i,j>是網(wǎng)中一條弧，則i是j的直接前驅(qū)，j是i的直接后繼。

在AOV網(wǎng)中，每一條弧表示了活動(dòng)之間存在的制約關(guān)系。

注：AOV網(wǎng)中不允許有回路，這意味著某項(xiàng)活動(dòng)以自己為先決條件。

例如：計(jì)算機(jī)專業(yè)的學(xué)生必須學(xué)習(xí)一系列的基本課和專業(yè)課。學(xué)生應(yīng)按照怎樣的順序來學(xué)習(xí)呢？

可以把這個(gè)問題看做一個(gè)大的工程，其活動(dòng)就是學(xué)習(xí)每一門課程。7.6有向無環(huán)圖及其應(yīng)用第四十頁，共九十九頁，編輯于2023年，星期三41C1C2C3C4C5C6C7C8C9C10C11無無C1,C2C3，C9C2C4C5C4C1C4，C9C4,C7課程代號(hào)

課程名稱

先修課程序設(shè)計(jì)基礎(chǔ)高等數(shù)學(xué)離散數(shù)學(xué)數(shù)據(jù)結(jié)構(gòu)普通物理人工智能計(jì)算機(jī)原理算法分析高級(jí)語言編譯系統(tǒng)操作系統(tǒng)C1、C2是獨(dú)立于其它課程的基礎(chǔ)課，而另一些課程必須在學(xué)完作為它的基礎(chǔ)課后才能開始，即有先行課。先行條件規(guī)定了課程之間的優(yōu)先關(guān)系。

計(jì)算機(jī)專業(yè)的課程設(shè)置及其關(guān)系7.6有向無環(huán)圖及其應(yīng)用第四十一頁，共九十九頁，編輯于2023年，星期三42

頂點(diǎn)表示課程，弧表示前提條件活動(dòng)。若課程i是課程j的先行課，則必然存在弧<i,j>。由此得到如下AOV網(wǎng)：

在安排學(xué)習(xí)順序時(shí)，必須保證在學(xué)習(xí)某門課前，已經(jīng)學(xué)習(xí)了其先行課。如何設(shè)置這些課程的學(xué)習(xí)順序，才能無矛盾、順利地完成學(xué)業(yè)？7.6有向無環(huán)圖及其應(yīng)用C1程序設(shè)計(jì)基礎(chǔ)C3離散數(shù)學(xué)C2高等數(shù)學(xué)C4數(shù)據(jù)結(jié)構(gòu)C5普通物理C6人工智能C7計(jì)算機(jī)原理C8算法分析C9高級(jí)語言C10編譯系統(tǒng)C11操作系統(tǒng)第四十二頁，共九十九頁，編輯于2023年，星期三432.拓?fù)渑判?/p>

拓?fù)湫蛄校河邢驁DD的一個(gè)頂點(diǎn)序列稱作一個(gè)拓?fù)湫蛄?，?duì)于該序列中任兩頂點(diǎn)v、u，若在D中v是u前趨，則在序列中v也是u前趨。

拓?fù)渑判颍喊袮OV網(wǎng)絡(luò)中各頂點(diǎn)按照它們相互之間的領(lǐng)先關(guān)系排列成一個(gè)線性序列的過程。

拓?fù)渑判虻膽?yīng)用：判斷工程流程的是否合理.

如何判斷AOV網(wǎng)是否存在有向回路？？利用拓?fù)渑判驒z測AOV網(wǎng)中是否存在環(huán)：對(duì)有向圖構(gòu)造其頂點(diǎn)的拓?fù)溆行蛐蛄?，若網(wǎng)中所有頂點(diǎn)都在它的拓?fù)溆行蛐蛄兄校瑒t該AOV網(wǎng)必定不存在環(huán)。7.6有向無環(huán)圖及其應(yīng)用第四十三頁，共九十九頁，編輯于2023年，星期三443.拓?fù)渑判蛩惴ǎ?）在AOV網(wǎng)中選一個(gè)沒有前驅(qū)的頂點(diǎn)v并將其輸出；（2）從網(wǎng)中刪除頂點(diǎn)v和所有以v為尾的弧；

（3）重復(fù)(1)、(2)，直至全部頂點(diǎn)均已輸出；或者當(dāng)圖中不存在無前驅(qū)的頂點(diǎn)為止。7.6有向無環(huán)圖及其應(yīng)用第四十四頁，共九十九頁，編輯于2023年，星期三45C1C3C2C9C5C10C7C6C8C11C4拓?fù)湫蛄校篊17.6有向無環(huán)圖及其應(yīng)用第四十五頁，共九十九頁，編輯于2023年，星期三46C3C2C9C5C10C7C6C8C11C4拓?fù)湫蛄校篊1，C2拓?fù)湫蛄校篊17.6有向無環(huán)圖及其應(yīng)用第四十六頁，共九十九頁，編輯于2023年，星期三47C3C9C5C10C7C6C8C11C4拓?fù)湫蛄校篊1，C2拓?fù)湫蛄校篊1，C2，C37.6有向無環(huán)圖及其應(yīng)用第四十七頁，共九十九頁，編輯于2023年，星期三48C9C5C10C7C6C8C11C4拓?fù)湫蛄校篊1，C2，C3拓?fù)湫蛄校篊1，C2，C3，C97.6有向無環(huán)圖及其應(yīng)用第四十八頁，共九十九頁，編輯于2023年，星期三49C5C10C7C6C8C11C4拓?fù)湫蛄校篊1，C2，C3，C9拓?fù)湫蛄校篊1，C2，C3，C9，C4C5C10C7C6C8C11拓?fù)湫蛄校篊1，C2，C3，C9，C4，C5C10C7C6C8C11拓?fù)湫蛄校篊1，C2，C3，C9，C4，C5，C7C10C6C8C11拓?fù)湫蛄校篊1，C2，C3，C9，C4，C5，C7，C10，C6，C8，C11

一個(gè)AOV網(wǎng)的拓?fù)湫蛄胁皇俏ㄒ坏摹Ｈ绾斡?jì)算機(jī)上實(shí)現(xiàn)對(duì)有向圖的拓?fù)渑判?？?.6有向無環(huán)圖及其應(yīng)用第四十九頁，共九十九頁，編輯于2023年，星期三50拓?fù)渑判蛩惴?（1）在AOV網(wǎng)中選一個(gè)沒有前驅(qū)的頂點(diǎn)v并將其輸出；（2）從網(wǎng)中刪除頂點(diǎn)v和所有以v為尾的??；

（3）重復(fù)(1)、(2)，直至全部頂點(diǎn)均已輸出；或者當(dāng)圖中不存在無前驅(qū)的頂點(diǎn)為止。7.6有向無環(huán)圖及其應(yīng)用※拓?fù)渑判蚍椒ǖ牧硪环N等價(jià)描述：

（1）

選擇一入度為0頂點(diǎn)v，輸出；

（2）

將v鄰接到的頂點(diǎn)的入度減1；

（3）

重復(fù)(1)、(2)，直至全部頂點(diǎn)均已輸出;或圖中沒有入度為0的頂點(diǎn)為止。第五十頁，共九十九頁，編輯于2023年，星期三51拓?fù)渑判虻臄?shù)據(jù)結(jié)構(gòu)：

以鄰接表存儲(chǔ)有向圖，并在頂點(diǎn)結(jié)點(diǎn)中增加該頂點(diǎn)的入度信息。算法：

1）為方便查找入度為0的元素，將鄰接表中所有入度為0的頂點(diǎn)進(jìn)棧2）棧非空時(shí)，輸出棧頂元素Vj并退棧；3）在鄰接表中查找Vj的直接后繼Vk，把Vk的入度減1；若Vk的入度為0則進(jìn)棧；

重復(fù)上述操作直至棧空為止。若棧空時(shí)輸出的頂點(diǎn)個(gè)數(shù)不是n，則有向圖有環(huán)；否則，拓?fù)渑判蛲戤叀５谖迨豁?，共九十九頁，編輯?023年，星期三52例:0123450122inlink4432^^^vexnext3^14^130012345^3210405top7.6有向無環(huán)圖及其應(yīng)用第五十二頁，共九十九頁，編輯于2023年，星期三530122inlink4432^^^vexnext3^14^130012345^輸出序列：53210405top7.6有向無環(huán)圖及其應(yīng)用第五十三頁，共九十九頁，編輯于2023年，星期三540122inlink4432^^^vexnext3^14^130012345^輸出序列：5p321040top7.6有向無環(huán)圖及其應(yīng)用第五十四頁，共九十九頁，編輯于2023年，星期三550122inlink4432^^^vexnext2^14^130012345^p321040top輸出序列：57.6有向無環(huán)圖及其應(yīng)用第五十五頁，共九十九頁，編輯于2023年，星期三560122inlink4432^^^vexnext2^14^130012345^p輸出序列：5321040top7.6有向無環(huán)圖及其應(yīng)用第五十六頁，共九十九頁，編輯于2023年，星期三570112inlink4432^^^vexnext2^14^130012345^p321040top輸出序列：57.6有向無環(huán)圖及其應(yīng)用第五十七頁，共九十九頁，編輯于2023年，星期三580112inlink4432^^^vexnext2^14^130012345^p=NULL321040top輸出序列：57.6有向無環(huán)圖及其應(yīng)用第五十八頁，共九十九頁，編輯于2023年，星期三590112inlink4432^^^vexnext2^14^130012345^輸出序列：5032104top7.6有向無環(huán)圖及其應(yīng)用第五十九頁，共九十九頁，編輯于2023年，星期三600112inlink4432^^^vexnext2^14^130012345^p32104top輸出序列：

507.6有向無環(huán)圖及其應(yīng)用第六十頁，共九十九頁，編輯于2023年，星期三610102inlink4432^^^vexnext2^14^130012345^p332104top輸出序列：

50

7.6有向無環(huán)圖及其應(yīng)用第六十一頁，共九十九頁，編輯于2023年，星期三620102inlink4432^^^vexnext2^14^130012345^p332104top輸出序列：

507.6有向無環(huán)圖及其應(yīng)用第六十二頁，共九十九頁，編輯于2023年，星期三630002inlink4432^^^vexnext2^14^130012345^p332104top2輸出序列：

507.6有向無環(huán)圖及其應(yīng)用第六十三頁，共九十九頁，編輯于2023年，星期三640002inlink4432^^^vexnext2^14^130012345^p332104top2輸出序列：

507.6有向無環(huán)圖及其應(yīng)用第六十四頁，共九十九頁，編輯于2023年，星期三650001inlink4432^^^vexnext2^14^130012345^p332104top2輸出序列：

507.6有向無環(huán)圖及其應(yīng)用第六十五頁，共九十九頁，編輯于2023年，星期三660001inlink4432^^^vexnext2^14^130012345^p=NULL332104top2輸出序列：

507.6有向無環(huán)圖及其應(yīng)用第六十六頁，共九十九頁，編輯于2023年，星期三670001inlink4432^^^vexnext2^14^130012344^輸出序列：

502332104top7.6有向無環(huán)圖及其應(yīng)用第六十七頁，共九十九頁，編輯于2023年，星期三680001inlink4432^^^vexnext2^14^130012345^p332104top輸出序列：

5027.6有向無環(huán)圖及其應(yīng)用第六十八頁，共九十九頁，編輯于2023年，星期三690001inlink4432^^^vexnext1^14^130012345^p332104top輸出序列：

5027.6有向無環(huán)圖及其應(yīng)用第六十九頁，共九十九頁，編輯于2023年，星期三700001inlink4432^^^vexnext1^14^130012345^p332104top輸出序列：

5027.6有向無環(huán)圖及其應(yīng)用第七十頁，共九十九頁，編輯于2023年，星期三710000inlink4432^^^vexnext1^14^130012345^p332104top1輸出序列：

5027.6有向無環(huán)圖及其應(yīng)用第七十一頁，共九十九頁，編輯于2023年，星期三720000inlink4432^^^vexnext1^14^130012345^p=NULL332104top1輸出序列：

5027.6有向無環(huán)圖及其應(yīng)用第七十二頁，共九十九頁，編輯于2023年，星期三730000inlink4432^^^vexnext1^14^130012345^輸出序列：

5021332104top7.6有向無環(huán)圖及其應(yīng)用第七十三頁，共九十九頁，編輯于2023年，星期三740000inlink4432^^^vexnext1^14^130012345^p=NULL332104top輸出序列：50217.6有向無環(huán)圖及其應(yīng)用第七十四頁，共九十九頁，編輯于2023年，星期三750000inlink4432^^^vexnext1^14^130012345^32104top輸出序列：502137.6有向無環(huán)圖及其應(yīng)用第七十五頁，共九十九頁，編輯于2023年，星期三760000inlink4432^^^vexnext1^14^130012345^p32104top輸出序列：502137.6有向無環(huán)圖及其應(yīng)用第七十六頁，共九十九頁，編輯于2023年，星期三770000inlink4432^^^vexnext0^14^130012345^p432104top輸出序列：502137.6有向無環(huán)圖及其應(yīng)用第七十七頁，共九十九頁，編輯于2023年，星期三780000inlink4432^^^vexnext0^14^130012345^p=NULL432104top輸出序列：502137.6有向無環(huán)圖及其應(yīng)用第七十八頁，共九十九頁，編輯于2023年，星期三790000inlink4432^^^vexnext0^14^130012345^輸出序列：502134432104top7.6有向無環(huán)圖及其應(yīng)用第七十九頁，共九十九頁，編輯于2023年，星期三800000inlink4432^^^vexnext0^14^130012345^p=NULL32104top輸出序列：5021347.6有向無環(huán)圖及其應(yīng)用第八十頁，共九十九頁，編輯于2023年，星期三81拓?fù)渑判蛩惴ǚ治?建鄰接表：T(n)=O(n+e)搜索入度為0的頂點(diǎn)的時(shí)間：T(n)=O(n)拓?fù)渑判颍篢(n)=O(n+e)7.6有向無環(huán)圖及其應(yīng)用第八十一頁，共九十九頁，編輯于2023年，星期三827.7AOE網(wǎng)和關(guān)鍵路徑１．AOE網(wǎng)(ActivityOnEdges)

如果在無有向環(huán)的帶權(quán)有向圖中,※用有向邊表示一個(gè)工程中的各項(xiàng)活動(dòng)(Activity),※用邊上的權(quán)值表示活動(dòng)的持續(xù)時(shí)間(Duration),※用頂點(diǎn)表示事件(Event)，每個(gè)事件表示在它之前的活動(dòng)已完成，在它之后的活動(dòng)可以開始.

這樣的有向圖叫做用邊表示活動(dòng)的網(wǎng)絡(luò)，簡稱AOE網(wǎng)。AOE網(wǎng)在某些工程估算方面非常有用?！猛?：計(jì)算完成整個(gè)工程至少需要多少時(shí)間(假設(shè)網(wǎng)絡(luò)中沒有環(huán))?※用途2：為縮短完成工程所需的時(shí)間,應(yīng)當(dāng)加快哪些活動(dòng)?

7.6有向無環(huán)圖及其應(yīng)用第八十二頁，共九十九頁，編輯于2023年，星期三83頂點(diǎn)表示事件邊表示活動(dòng)事件Vj發(fā)生表示ak已結(jié)束ak

VjVi事件Vi發(fā)生表示活動(dòng)ak可以開始

V3V1V4V6V5V2a4=3a1=3a2=2a6=3a5=4a3=2a7=2a8=1AOE網(wǎng)事件V1——表示整個(gè)工程開始事件V6——表示整個(gè)工程結(jié)束7.6有向無環(huán)圖及其應(yīng)用第八十三頁，共九十九頁，編輯于2023年，星期三84說明：AOV網(wǎng)和AOE網(wǎng)，用都能表示工程各子工程的流程，一個(gè)用頂點(diǎn)表示活動(dòng)，一個(gè)用邊表示活動(dòng)，但AOV網(wǎng)側(cè)重表示活動(dòng)的前后次序，AOE網(wǎng)除表示活動(dòng)先后次序，還表示了活動(dòng)的持續(xù)時(shí)間等，因此可利用AOE網(wǎng)解決工程所需最短時(shí)間及哪些子工程拖延會(huì)影響整個(gè)工程按時(shí)完成等問題。實(shí)際應(yīng)用中采用那一種圖，取決于要求解的問題。AOE網(wǎng)具有兩個(gè)性質(zhì):(1)只有在某頂點(diǎn)所代表的事件發(fā)生之后，從該頂點(diǎn)出發(fā)的弧所代表的活動(dòng)才能開始;(2)只有在進(jìn)入一個(gè)頂點(diǎn)的各弧所代表的活動(dòng)都已經(jīng)結(jié)束，該頂點(diǎn)所代表的事件才能發(fā)生。

7.6有向無環(huán)圖及其應(yīng)用第八十四頁，共九十九頁，編輯于2023年，星期三852.關(guān)鍵路徑(CriticalPath)

在AOE網(wǎng)中,有些活動(dòng)順序進(jìn)行，有些活動(dòng)并行進(jìn)行。

整個(gè)工程結(jié)束的條件：從源點(diǎn)到終點(diǎn)的有向路徑可能不止一條，其長度也不盡相同，但只有各條路徑上所有活動(dòng)都完成了，整個(gè)工程才算完成。

關(guān)鍵路徑：完成整個(gè)工程所需的時(shí)間取決于從源點(diǎn)到終點(diǎn)的最長路徑長度（該路徑上所有活動(dòng)的持續(xù)時(shí)間之和）。這條路徑長度最長的路徑就叫做關(guān)鍵路徑。

7.6有向無環(huán)圖及其應(yīng)用V3V1V4V6V5V2a4=3a1=3a2=2a6=3a5=4a3=2a7=2a8=1AOE網(wǎng)第八十五頁，共九十九頁，編輯于2023年，星期三86※關(guān)鍵路徑長度是整個(gè)工程所需的最短工期,即要縮短整個(gè)工期，必須加快關(guān)鍵活動(dòng)的進(jìn)度。第八十六頁，共九十九頁，編輯于2023年，星期三873.關(guān)鍵路徑的確定設(shè)活動(dòng)ai用弧<j,k>表示，其持續(xù)時(shí)間記為：dut(<j,k>)。(1)事件Vk的最早可能開始時(shí)間Ve[k]

是從源點(diǎn)V0到頂點(diǎn)Vk的最長路徑長度。決定了所有從頂點(diǎn)發(fā)出的弧所代表的活動(dòng)能夠開工的最早時(shí)間.

根據(jù)AOE網(wǎng)的性質(zhì)，只有進(jìn)入VK的所有活動(dòng)<Vj,Vk>（1≤j≤n-1)都結(jié)束時(shí),

Vk代表的事件才能發(fā)生。計(jì)算Vk的的最早可能開始時(shí)間方法如下:從Ve[1]=0開始遞推，Ve[k]=Max{ve[j]+dut(<j,k>)}VjVkVj1≤j≤n-17.6有向無環(huán)圖及其應(yīng)用第八十七頁，共九十九頁，編輯于2023年，星期三88(2)事件Vk的最遲允許開始時(shí)間Vl[k]

是在保證終點(diǎn)Vn-1

在Ve[n-1]

時(shí)刻完成的前提下(即不拖延工期)，事件Vk的允許的最遲開始時(shí)間。

從Vl[n]=Ve[n]開始遞推，Vl[k]=Min{vl[j]–dut(<j,k>)}VjVkVj2≤j≤n

設(shè)弧<Vk,Vj>代表從Vk出發(fā)的活動(dòng)，為了不拖延工期，Vk發(fā)生的最遲時(shí)間必須保證不推遲從事件Vk出發(fā)的所有活動(dòng)<Vk,Vj>的終點(diǎn)Vj(2≤j≤n)的最遲時(shí)間．

7.6有向無環(huán)圖及其應(yīng)用第八十八頁，共九十九頁，編輯于2023年，星期三89(3)活動(dòng)ai的最早可能開始時(shí)間e[i]

設(shè)活動(dòng)

ai由弧<Vk,Vj>表示，根據(jù)AOE網(wǎng)的性質(zhì)，只有事件Vk發(fā)生了，活動(dòng)ai才能開始。也就是說，活動(dòng)ai的最早開始時(shí)間等于是vk的最早發(fā)生時(shí)間。因此