數據結構第七章圖第一頁，共九十九頁，2022年，8月28日2【重點掌握】：圖的兩種遍歷方法：遍歷的定義、深度優先搜索遍歷和廣度優先搜索遍歷的算法；應用圖的遍歷算法判斷圖的連通性及求圖的生成樹；

用Prim、Kruskal算法求圖的最小生成樹；用Dijkstra算法求解單源最短路徑問題；用Floyd算法求所有頂點間的最短路徑問題；利用AOV網進行拓撲排序；利用AOE網求關鍵路徑問題；【掌

握】：掌握圖的定義和術語；圖的各種存儲結構及其構造算法、在實際問題中的求解效率。第二頁，共九十九頁，2022年，8月28日37.3圖的遍歷7.3圖的遍歷：從圖的某頂點出發，訪問圖中所有頂點，并且每個頂點僅訪問一次。

圖結構的遍歷復雜性：（1）在圖結構中，沒有一個“自然”的首結點，圖中的任意一個頂點都可以作為第一個被訪問的結點（2）在非連通圖中，從一個頂點出發，只能訪問它所在的連通分量上的所有頂點，因此，還需考慮如何選取下一個出發點以訪問圖中的其余連通分量（3）在圖結構中，如果有回路存在，那么一個頂點被訪問后，有可能沿回路又回到該頂點，考慮如何避免重復訪問（4）在圖結構中，一個頂點可以和其他多個頂點鄰接，當這樣的頂點訪問過后，考慮如何選取下一個要訪問的頂點的問題第三頁，共九十九頁，2022年，8月28日4

圖的遍歷方法有深度優先遍歷和廣度優先遍歷兩種。

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

若此時圖中尚有頂點未被訪問，則另選圖中一個未被訪問的頂點作起點，重復上述過程，直至圖中所有頂點都被訪問到。第四頁，共九十九頁，2022年，8月28日5

V0

V7

V6

V5

V4

V3

V2

V1若圖的存儲結構為鄰接表，則訪問鄰接點的順序不唯一，深度優先序列不是唯一的

V0

V1

V3

V2

V7

V6

V5

V4

V0,V1,V3,V4,V7,V2,V5,V6,※求圖G以V0為起點的的深度優先序列（設存儲結構為鄰接矩陣）第五頁，共九十九頁，2022年，8月28日6voidDFS(GraphG,intv){/*從第v個頂點出發，遞歸地深度優先遍歷圖G*//*v是頂點在一維數組中的位置，假設G是非空圖*/visited[v]=1;Visit(v);/*訪問第v個頂點*/for(w=FirstAdjVex(G,v);w;w=NextAdjVex(G,v,w))if(!visited[w])DFS(G,w);

/*對v的尚未訪問的鄰接頂點w遞歸調用DFS*/}輔助數組：intvisited[Max_Vertex_Num];訪問標志數組,全局變量，初始時所有分量全為0，visited[v]=1表示頂點v已被訪問.visited01234……00000深度優先遍歷算法:7.3圖的遍歷第六頁，共九十九頁，2022年，8月28日77.3圖的遍歷在鄰接表存儲結構上實現深度優先搜索:voidDFSTraverseAL(ALGraphG)/*深度優先遍歷以鄰接表存儲的圖G*/{inti;for(i=0;i<G.vexnum;++i)visited[i]=0;/*標志數組初始化*/for(i=0;i<G.vexnum;++i)if(!visited[i])DFSAL(G,i);/*Vi未訪問過，從Vi開始DFS搜索*/}第七頁，共九十九頁，2022年，8月28日8voidDFSAL(ALGraphG,inti){/*從第v個頂點出發，遞歸地深度優先遍歷圖G*//*v是頂點的序號，假設G是用鄰接表存儲*/

EdgeNode*p;

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

/*若w尚未訪問,遞歸調用DFS*/}}/*DFSAL*/7.3圖的遍歷第八頁，共九十九頁，2022年，8月28日9

在遍歷時，對圖中每個頂點至多調用一次DFS函數，因為一旦某個頂點被標志成已被訪問，就不再從它出發進行搜索。因此，遍歷圖的過程實質上是對每個頂點查找其鄰接點的過程。其耗費的時間則取決于所采用的存儲結構。

用鄰接矩陣做圖的存儲結構時，查找各個頂點的鄰接點所需的時間為O(n2)，其中n為圖中頂點數。當以鄰接矩陣做存儲結構時，深度優先搜索遍歷圖的時間復雜度為O(n2+n)。

當以鄰接表做圖的存儲結構時，找鄰接點所需時間為O(e)，其中e為無向圖中邊的數或有向圖中弧的數。因此，當以鄰接表做存儲結構時，深度優先搜索遍歷圖的時間復雜度為O(n+e)。7.3圖的遍歷第九頁，共九十九頁，2022年，8月28日10圖中某頂點v出發：1）訪問頂點v；2）訪問v的所有未被訪問的鄰接點w1,w2,…wk

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

廣度優先遍歷7.3圖的遍歷第十頁，共九十九頁，2022年，8月28日11

V0

V7

V6

V5

V4

V3

V2

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

V0

V1

V3

V2

V7

V6

V5

V4若圖的存儲結構為鄰接表，則訪問鄰接點的順序不唯一，深度優先序列不是唯一的※求圖G以V0為起點的的廣度優先序列（設存儲結構為鄰接矩陣）∵先被訪問的頂點，其鄰接點也要先被訪問∴設一隊列保存已訪問的頂點第十一頁，共九十九頁，2022年，8月28日12Q※在鄰接表存儲結構上的廣度優先搜索V0V1V2V3V4V7V5V6V1V2V3V0V4V7V5V6V0V7V6V5V4V3V2V17.3圖的遍歷7012V0V2V3V1datafirstarc01^^adjvexnext3V430511^274564V5V6V72^62^51^47^6^第十二頁，共九十九頁，2022年，8月28日13voidBFSTraverse(MGraphG)/*從v出發，廣度優先遍歷連通圖G*//*使用輔助隊列Q和訪問標志數組visited*/{for(v=0;v<G.vexnum;++i)visited[v]=0;InitQueue(Q,G.vexnum);/*初始化空的輔助隊列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);/*隊頭元素出隊,并賦值給u*/

/*訪問u所有未被訪問的鄰接點*/ 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圖的遍歷第十三頁，共九十九頁，2022年，8月28日14第七

章

圖

7.4

連通網的最小生成樹 7.4.1

生成樹7.4.2

最小生成樹7.4.3

構造最小生成樹的Prim算法7.4.4

構造最小生成樹的Kruskal算法第十四頁，共九十九頁，2022年，8月28日15

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

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

例如：一個通信網絡中，節點代表了路由器，為了使各路由器之間是連通的（數據可達），且不形成回路(數據回到發送方)，則需建立該網絡的生成樹。第十六頁，共九十九頁，2022年，8月28日17求生成樹的方法：利用遍歷算法。

從連通圖中的任一頂點出發進行遍歷時，除出發點外，其余頂點必須通過一條邊才能到達，所以遍歷過程中經歷的邊有n-1條，它和n個頂點組成了連通圖的一棵生成樹。

由深度優先搜索得到的是深度優先生成樹；由廣度優先搜索得到的是廣度優先生成樹。第十七頁，共九十九頁，2022年，8月28日18V0V7V6V5V4V3V2V1深度遍歷：V0V1V3V4V7V2V5V6V0V7V6V5V4V3V2V17.4最小的生成樹V0V7V6V5V4V3V2V1深度優先搜索生成樹第十八頁，共九十九頁，2022年，8月28日19廣度遍歷：V0V1V2V3V4V7V5V6V0V7V6V5V4V3V2V1V0V7V6V5V4V3V2V1廣度優先搜索生成樹7.4最小的生成樹V0V7V6V5V4V3V2V1第十九頁，共九十九頁，2022年，8月28日20

最小生成樹的概念

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

問題的提出：設要在n個城市間建立通信聯絡網，頂點—表示城市，權表示城市間建立通信線路所需花費代價。希望找到一棵生成樹，它的每條邊上的權值之和（即建立該通信網所需花費的總代價）最小——最小代價生成樹。7.4最小的生成樹第二十頁，共九十九頁，2022年，8月28日21※最小生成樹定義：對于一個網絡，它的所有生成樹中邊權值最小的生成樹稱為最小生成樹。

問題分析：n個城市間建立通信網，如何在可能的線路中選擇n-1條，能把所有城市（頂點）均連起來，且總耗費（各邊權值之和）最小。即：如何在保證n點連通的前題下最節省經費?第二十一頁，共九十九頁，2022年，8月28日221.Prim

法基本步驟

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

中。(4)重復(2)、(3)，直到網絡中的所有頂點都加入到生成樹頂點集合U中為止。

構造最小生成樹的Prim算法7.4最小的生成樹第二十二頁，共九十九頁，2022年，8月28日23V3V1V4V6V5V2651U={V1}V3V1V4V6V5V251654V3V4V6V5V21V1U={V1,V3}V3V1V4V6V5V216542V3V1V4V6V5V251654U={V1,V3,V6}7.4最小的生成樹V3V1V4V6V5V236521655462.過程演示第二十三頁，共九十九頁，2022年，8月28日24V3V1V4V6V5V216542U={V1,V3,V6,V4

}V3V1V4V6V5V216542U={V1,V3,V6,V4,V2}V3V1V4V6V5V215423U={V1,V3,V6,V4,V2,V5}7.4最小的生成樹V3V1V4V6V5V23652165546Prim算法的時間復雜度為O(n2)第二十四頁，共九十九頁，2022年，8月28日257.4.3構造最小生成樹的Kruskal算法1.基本思想：按網中權值遞增的順序構造最小生成樹。

2.基本步驟

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

算法的時間復雜度為O(ne)。第二十七頁，共九十九頁，2022年，8月28日28

7.5單源最短路徑(ShortestPath)

從一個源點到其他各點的最短路徑第二十八頁，共九十九頁，2022年，8月28日29

交通咨詢系統、通訊網、計算機網絡中經常要尋找兩結點間最短路徑。例如：交通咨詢系統中：咨詢A到B的最短路徑；計算機網中如何發送E-mail才最節省費用（使E-mail由A到B沿最短路徑傳送）。

設用帶權的有向圖表示一個交通運輸網，圖中：

頂點——表示城市

邊——表示城市間的交通聯系

權——表示此線路的長度或沿此線路運輸所花的時間或費用等

這類問題歸結為從某頂點出發，沿圖的邊到達另一頂點所經過的路徑中，各邊上權值之和最小的一條路徑——最短路徑。路徑上的第一個頂點為源點，最后一個頂點為終點。

問題的提出:7.5最短路徑第二十九頁，共九十九頁，2022年，8月28日30※最短路徑問題：如果從圖中某一頂點(源點)到達另一頂點(終點)的路徑可能不止一條，如何找到一條路徑使沿此路徑上各邊上的權值總和達到最小。

第三十頁，共九十九頁，2022年，8月28日31

從一個源點到其他各點的最短路徑1.

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

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

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

將T中頂點按如下規則加入到S中：

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

（2）待求的最短路徑最多以已求出最短路徑的頂點為中間點：從V0到某頂點的最短路徑中，只將S中的頂點作為中間點第三十二頁，共九十九頁，2022年，8月28日33（2）Dijkstra算法的基本步驟

設V0是源點，初使時令S={V0},T={其余頂點}，T中頂點對應的距離值若存在，<V0,Vi>邊權值為<V0,Vi>弧上的權值；若不存在，<V0,Vi>邊權值為。1）從T中選取一個其距離值最小的頂點W，加入S；2）①對T中頂點的距離值進行修改：先求出V0到Vi中間只經S中結點的最短路徑；若加進W作中間頂點后從V0到Vi的距離值

比

不加W的路徑要短，則修改此距離值；②上述最短路徑中長度最小者即為下一條長度最短的路徑；③將所求最短路徑的終點加入S中；3）重復2）直到S中包含所有頂點，即S=V為止。7.5最短路徑第三十三頁，共九十九頁，2022年，8月28日34

1）圖用帶權鄰接矩陣存儲；2）引入一個輔助數組dist。它的每一個分量dist[i]表示當前找到的從源點v0到終點vi

的最短路徑的長度

初始狀態：若從源點v0到頂點vi有邊，則dist[i]為該邊上的權值；若從源點v0到頂點vi

沒有邊，則dist[i]為

。3）數組path[]表示從V0到各終點的最短路徑上，此頂點的前一頂點的序號；若從V0到某終點無路徑，則用-1

作為該結點前一頂點的序號4)數組s[]標識V0到該結點的最短路徑是否求出。0表示沒求出，1表示已求出。7.5最短路徑(3)算法實現第三十四頁，共九十九頁，2022年，8月28日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]頂點4頂點3頂點2頂點1選取點01234第三十五頁，共九十九頁，2022年，8月28日36

如何從表中讀取源點0到終點的最短路徑？

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

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

反過來排列，得到路徑0,3,2,4，即V0到頂點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]頂點4頂點3頂點2頂點1選取點第三十六頁，共九十九頁，2022年，8月28日37※Dijkstra算法的時間復雜度為O(n2)第三十七頁，共九十九頁，2022年，8月28日38

7.6AOV網與拓撲排序第三十八頁，共九十九頁，2022年，8月28日397.6.1有向無環圖的概念1.

有向無環圖（directedacyclinegraph）：沒有回路的有向圖。◆含有公共子式的表達式

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

a

-

+

b*/ef用有向無環圖表示的表達式◆流程圖：

工程流程、生產過程中工序流程、程序流程、課程的流程。常用的兩種有向無環圖是：AOV網，AOE網。7.6有向無環圖及其應用

-

a

+

b*/ef

a

+

b用二叉樹表示的表達式第三十九頁，共九十九頁，2022年，8月28日40AOV網與拓撲排序1.AOV網

(ActivityOnVertexnetwork)

用頂點表示活動，邊表示活動的順序關系的有向圖稱為AOV網。

在AOV網中，若從頂點i到頂點j有一條有向路徑。則頂點i是頂點j的前驅，j是i的后繼。若<i,j>是網中一條弧，則i是j的直接前驅，j是i的直接后繼。

在AOV網中，每一條弧表示了活動之間存在的制約關系。

注：AOV網中不允許有回路，這意味著某項活動以自己為先決條件。

例如：計算機專業的學生必須學習一系列的基本課和專業課。學生應按照怎樣的順序來學習呢？

可以把這個問題看做一個大的工程，其活動就是學習每一門課程。7.6有向無環圖及其應用第四十頁，共九十九頁，2022年，8月28日41C1C2C3C4C5C6C7C8C9C10C11無無C1,C2C3，C9C2C4C5C4C1C4，C9C4,C7課程代號

課程名稱

先修課程序設計基礎高等數學離散數學數據結構普通物理人工智能計算機原理算法分析高級語言編譯系統操作系統C1、C2是獨立于其它課程的基礎課，而另一些課程必須在學完作為它的基礎課后才能開始，即有先行課。先行條件規定了課程之間的優先關系。

計算機專業的課程設置及其關系7.6有向無環圖及其應用第四十一頁，共九十九頁，2022年，8月28日42

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

在安排學習順序時，必須保證在學習某門課前，已經學習了其先行課。如何設置這些課程的學習順序，才能無矛盾、順利地完成學業？7.6有向無環圖及其應用C1程序設計基礎C3離散數學C2高等數學C4數據結構C5普通物理C6人工智能C7計算機原理C8算法分析C9高級語言C10編譯系統C11操作系統第四十二頁，共九十九頁，2022年，8月28日432.拓撲排序

拓撲序列：有向圖D的一個頂點序列稱作一個拓撲序列，對于該序列中任兩頂點v、u，若在D中v是u前趨，則在序列中v也是u前趨。

拓撲排序：把AOV網絡中各頂點按照它們相互之間的領先關系排列成一個線性序列的過程。

拓撲排序的應用：判斷工程流程的是否合理.

如何判斷AOV網是否存在有向回路？？利用拓撲排序檢測AOV網中是否存在環：對有向圖構造其頂點的拓撲有序序列，若網中所有頂點都在它的拓撲有序序列中，則該AOV網必定不存在環。7.6有向無環圖及其應用第四十三頁，共九十九頁，2022年，8月28日443.拓撲排序算法（1）在AOV網中選一個沒有前驅的頂點v并將其輸出；（2）從網中刪除頂點v和所有以v為尾的弧；

（3）重復(1)、(2)，直至全部頂點均已輸出；或者當圖中不存在無前驅的頂點為止。7.6有向無環圖及其應用第四十四頁，共九十九頁，2022年，8月28日45C1C3C2C9C5C10C7C6C8C11C4拓撲序列：C17.6有向無環圖及其應用第四十五頁，共九十九頁，2022年，8月28日46C3C2C9C5C10C7C6C8C11C4拓撲序列：C1，C2拓撲序列：C17.6有向無環圖及其應用第四十六頁，共九十九頁，2022年，8月28日47C3C9C5C10C7C6C8C11C4拓撲序列：C1，C2拓撲序列：C1，C2，C37.6有向無環圖及其應用第四十七頁，共九十九頁，2022年，8月28日48C9C5C10C7C6C8C11C4拓撲序列：C1，C2，C3拓撲序列：C1，C2，C3，C97.6有向無環圖及其應用第四十八頁，共九十九頁，2022年，8月28日49C5C10C7C6C8C11C4拓撲序列：C1，C2，C3，C9拓撲序列：C1，C2，C3，C9，C4C5C10C7C6C8C11拓撲序列：C1，C2，C3，C9，C4，C5C10C7C6C8C11拓撲序列：C1，C2，C3，C9，C4，C5，C7C10C6C8C11拓撲序列：C1，C2，C3，C9，C4，C5，C7，C10，C6，C8，C11

一個AOV網的拓撲序列不是唯一的。如何計算機上實現對有向圖的拓撲排序？？7.6有向無環圖及其應用第四十九頁，共九十九頁，2022年，8月28日50拓撲排序算法:（1）在AOV網中選一個沒有前驅的頂點v并將其輸出；（2）從網中刪除頂點v和所有以v為尾的弧；

（3）重復(1)、(2)，直至全部頂點均已輸出；或者當圖中不存在無前驅的頂點為止。7.6有向無環圖及其應用※拓撲排序方法的另一種等價描述：

（1）

選擇一入度為0頂點v，輸出；

（2）

將v鄰接到的頂點的入度減1；

（3）

重復(1)、(2)，直至全部頂點均已輸出;或圖中沒有入度為0的頂點為止。第五十頁，共九十九頁，2022年，8月28日51拓撲排序的數據結構：

以鄰接表存儲有向圖，并在頂點結點中增加該頂點的入度信息。算法：

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

重復上述操作直至棧空為止。若棧空時輸出的頂點個數不是n，則有向圖有環；否則，拓撲排序完畢。第五十一頁，共九十九頁，2022年，8月28日52例:0123450122inlink4432^^^vexnext3^14^130012345^3210405top7.6有向無環圖及其應用第五十二頁，共九十九頁，2022年，8月28日530122inlink4432^^^vexnext3^14^130012345^輸出序列：53210405top7.6有向無環圖及其應用第五十三頁，共九十九頁，2022年，8月28日540122inlink4432^^^vexnext3^14^130012345^輸出序列：5p321040top7.6有向無環圖及其應用第五十四頁，共九十九頁，2022年，8月28日550122inlink4432^^^vexnext2^14^130012345^p321040top輸出序列：57.6有向無環圖及其應用第五十五頁，共九十九頁，2022年，8月28日560122inlink4432^^^vexnext2^14^130012345^p輸出序列：5321040top7.6有向無環圖及其應用第五十六頁，共九十九頁，2022年，8月28日570112inlink4432^^^vexnext2^14^130012345^p321040top輸出序列：57.6有向無環圖及其應用第五十七頁，共九十九頁，2022年，8月28日580112inlink4432^^^vexnext2^14^130012345^p=NULL321040top輸出序列：57.6有向無環圖及其應用第五十八頁，共九十九頁，2022年，8月28日590112inlink4432^^^vexnext2^14^130012345^輸出序列：5032104top7.6有向無環圖及其應用第五十九頁，共九十九頁，2022年，8月28日600112inlink4432^^^vexnext2^14^130012345^p32104top輸出序列：

507.6有向無環圖及其應用第六十頁，共九十九頁，2022年，8月28日610102inlink4432^^^vexnext2^14^130012345^p332104top輸出序列：

50

7.6有向無環圖及其應用第六十一頁，共九十九頁，2022年，8月28日620102inlink4432^^^vexnext2^14^130012345^p332104top輸出序列：

507.6有向無環圖及其應用第六十二頁，共九十九頁，2022年，8月28日630002inlink4432^^^vexnext2^14^130012345^p332104top2輸出序列：

507.6有向無環圖及其應用第六十三頁，共九十九頁，2022年，8月28日640002inlink4432^^^vexnext2^14^130012345^p332104top2輸出序列：

507.6有向無環圖及其應用第六十四頁，共九十九頁，2022年，8月28日650001inlink4432^^^vexnext2^14^130012345^p332104top2輸出序列：

507.6有向無環圖及其應用第六十五頁，共九十九頁，2022年，8月28日660001inlink4432^^^vexnext2^14^130012345^p=NULL332104top2輸出序列：

507.6有向無環圖及其應用第六十六頁，共九十九頁，2022年，8月28日670001inlink4432^^^vexnext2^14^130012344^輸出序列：

502332104top7.6有向無環圖及其應用第六十七頁，共九十九頁，2022年，8月28日680001inlink4432^^^vexnext2^14^130012345^p332104top輸出序列：

5027.6有向無環圖及其應用第六十八頁，共九十九頁，2022年，8月28日690001inlink4432^^^vexnext1^14^130012345^p332104top輸出序列：

5027.6有向無環圖及其應用第六十九頁，共九十九頁，2022年，8月28日700001inlink4432^^^vexnext1^14^130012345^p332104top輸出序列：

5027.6有向無環圖及其應用第七十頁，共九十九頁，2022年，8月28日710000inlink4432^^^vexnext1^14^130012345^p332104top1輸出序列：

5027.6有向無環圖及其應用第七十一頁，共九十九頁，2022年，8月28日720000inlink4432^^^vexnext1^14^130012345^p=NULL332104top1輸出序列：

5027.6有向無環圖及其應用第七十二頁，共九十九頁，2022年，8月28日730000inlink4432^^^vexnext1^14^130012345^輸出序列：

5021332104top7.6有向無環圖及其應用第七十三頁，共九十九頁，2022年，8月28日740000inlink4432^^^vexnext1^14^130012345^p=NULL332104top輸出序列：50217.6有向無環圖及其應用第七十四頁，共九十九頁，2022年，8月28日750000inlink4432^^^vexnext1^14^130012345^32104top輸出序列：502137.6有向無環圖及其應用第七十五頁，共九十九頁，2022年，8月28日760000inlink4432^^^vexnext1^14^130012345^p32104top輸出序列：502137.6有向無環圖及其應用第七十六頁，共九十九頁，2022年，8月28日770000inlink4432^^^vexnext0^14^130012345^p432104top輸出序列：502137.6有向無環圖及其應用第七十七頁，共九十九頁，2022年，8月28日780000inlink4432^^^vexnext0^14^130012345^p=NULL432104top輸出序列：502137.6有向無環圖及其應用第七十八頁，共九十九頁，2022年，8月28日790000inlink4432^^^vexnext0^14^130012345^輸出序列：502134432104top7.6有向無環圖及其應用第七十九頁，共九十九頁，2022年，8月28日800000inlink4432^^^vexnext0^14^130012345^p=NULL32104top輸出序列：5021347.6有向無環圖及其應用第八十頁，共九十九頁，2022年，8月28日81拓撲排序算法分析:建鄰接表：T(n)=O(n+e)搜索入度為0的頂點的時間：T(n)=O(n)拓撲排序：T(n)=O(n+e)7.6有向無環圖及其應用第八十一頁，共九十九頁，2022年，8月28日827.7AOE網和關鍵路徑１．AOE網(ActivityOnEdges)

如果在無有向環的帶權有向圖中,※用有向邊表示一個工程中的各項活動(Activity),※用邊上的權值表示活動的持續時間(Duration),※用頂點表示事件(Event)，每個事件表示在它之前的活動已完成，在它之后的活動可以開始.

這樣的有向圖叫做用邊表示活動的網絡，簡稱AOE網。AOE網在某些工程估算方面非常有用。※用途1：計算完成整個工程至少需要多少時間(假設網絡中沒有環)?※用途2：為縮短完成工程所需的時間,應當加快哪些活動?

7.6有向無環圖及其應用第八十二頁，共九十九頁，2022年，8月28日83頂點表示事件邊表示活動事件Vj發生表示ak已結束ak

VjVi事件Vi發生表示活動ak可以開始

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

7.6有向無環圖及其應用第八十四頁，共九十九頁，2022年，8月28日852.關鍵路徑(CriticalPath)

在AOE網中,有些活動順序進行，有些活動并行進行。

整個工程結束的條件：從源點到終點的有向路徑可能不止一條，其長度也不盡相同，但只有各條路徑上所有活動都完成了，整個工程才算完成。

關鍵路徑：完成整個工程所需的時間取決于從源點到終點的最長路徑長度（該路徑上所有活動的持續時間之和）。這條路徑長度最長的路徑就叫做關鍵路徑。

7.6有向無環圖及其應用V3V1V4V6V5V2a4=3a1=3a2=2a6=3a5=4a3=2a7=2a8=1AOE網第八十五頁，共九十九頁，2022年，8月28日86※關鍵路徑長度是整個工程所需的最短工期,即要縮短整個工期，必須加快關鍵活動的進度。第八十六頁，共九十九頁，2022年，8月28日873.關鍵路徑的確定設活動ai用弧<j,k>表示，其持續時間記為：dut(<j,k>)。(1)事件Vk的最早可能開始時間Ve[k]

是從源點V0到頂點Vk的最長路徑長度。決定了所有從頂點發出的弧所代表的活動能夠開工的最早時間.

根據AOE網的性質，只有進入VK的所有活動<Vj,Vk>（1≤j≤n-1)都結束時,

Vk代表的事件才能發生。計算Vk的的最早可能開始時間方法如下:從Ve[1]=0開始遞推，Ve[k]=Max{ve[j]+dut(<j,k>)}VjVkVj1≤j≤n-17.6有向無環圖及其應用第八十七頁，共九十九頁，2022年，8月28日88(2)事件Vk的最遲允許開始時間Vl[k]

是在保證終點Vn-1

在Ve[n-1]

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

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

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

7.6有向無環圖及其應用第八十八頁，共九十九頁，2022年，8月28日89(3)活動ai的最早可能開始時間e[i]

設活動

ai由弧<Vk,Vj>表示，根據AOE網的性質，只有事件Vk發生了，活動ai才能開始。也就是說，活動ai的最早開始時間等于是vk的最早發生時間。因此,