1、2022-2-15精選課件精選課件1第第7 7章章 圖圖圖是一種圖是一種的結構關系，每個元素可以有零個或多的結構關系，每個元素可以有零個或多個直接前趨；零個或多個直接后繼個直接前趨；零個或多個直接后繼。精選課件精選課件2【重點掌握重點掌握】：圖的兩種遍歷方法：遍歷的定義、深度優(yōu)先搜索遍歷和圖的兩種遍歷方法：遍歷的定義、深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷的算法；廣度優(yōu)先搜索遍歷的算法；應用圖的遍歷算法判斷圖的連通性及求圖的生成樹；應用圖的遍歷算法判斷圖的連通性及求圖的生成樹； 用用PrimPrim、KruskalKruskal算法求圖的最小生成樹；算法求圖的最小生成樹；用用DijkstraDij

2、kstra算法求解單源最短路徑問題；用算法求解單源最短路徑問題；用FloydFloyd算法求算法求所有頂點間的最短路徑問題；所有頂點間的最短路徑問題；利用利用AOVAOV網進行拓撲排序；利用網進行拓撲排序；利用AOEAOE網求關鍵路徑問題；網求關鍵路徑問題；【掌掌 握握】：掌握圖的定義和術語；掌握圖的定義和術語；1.1. 圖的各種存儲結構及其構造算法、在實際問題中的求解圖的各種存儲結構及其構造算法、在實際問題中的求解效率。效率。精選課件精選課件37.3 7.3 圖的遍歷圖的遍歷 7.3 7.3 圖的遍歷：圖的遍歷：從圖的某頂點出發(fā)，訪問圖中所有頂點，從圖的某頂點出發(fā)，訪問圖中所有頂點，并且每個

3、頂點僅訪問一次。并且每個頂點僅訪問一次。 圖結構的遍歷復雜性：圖結構的遍歷復雜性：（1 1）在圖結構中，沒有一個）在圖結構中，沒有一個“自然自然”的首結點，圖中的任的首結點，圖中的任意一個頂點都可以作為第一個被訪問的結點意一個頂點都可以作為第一個被訪問的結點（2 2）在非連通圖中，從一個頂點出發(fā)，只能訪問它所在的）在非連通圖中，從一個頂點出發(fā)，只能訪問它所在的連通分量上的所有頂點，因此，還需考慮連通分量上的所有頂點，因此，還需考慮如何選取下一個出如何選取下一個出發(fā)點發(fā)點以訪問圖中的其余連通分量以訪問圖中的其余連通分量（3 3）在圖結構中，如果有回路存在，那么一個頂點被訪問）在圖結構中，如果有回

4、路存在，那么一個頂點被訪問后，有可能沿回路又回到該頂點，考慮后，有可能沿回路又回到該頂點，考慮如何避免重復訪問如何避免重復訪問（4 4）在圖結構中，一個頂點可以和其他多個頂點鄰接，當）在圖結構中，一個頂點可以和其他多個頂點鄰接，當這樣的頂點訪問過后，考慮這樣的頂點訪問過后，考慮如何選取下一個要訪問的頂點的如何選取下一個要訪問的頂點的問題問題精選課件精選課件4 圖的遍歷方法有深度優(yōu)先遍歷和廣度優(yōu)先遍歷兩種。圖的遍歷方法有深度優(yōu)先遍歷和廣度優(yōu)先遍歷兩種。7.3.1 深度優(yōu)先搜索深度優(yōu)先搜索方法：方法：（1 1）從圖的某一頂點）從圖的某一頂點V V0 0出發(fā)，訪問此頂點；出發(fā)，訪問此頂點；（2 2）

5、依次從）依次從V V0 0的未被訪問的鄰接點出發(fā)，深度優(yōu)先遍歷圖，的未被訪問的鄰接點出發(fā)，深度優(yōu)先遍歷圖，直至圖中所有和直至圖中所有和V V0 0相通的頂點都被訪問到。相通的頂點都被訪問到。 若此時圖中若此時圖中尚有頂點未被訪問，則另選圖中一個未被訪問的頂點作起點，尚有頂點未被訪問，則另選圖中一個未被訪問的頂點作起點，重復上述過程，直至圖中所有頂點都被訪問到。重復上述過程，直至圖中所有頂點都被訪問到。精選課件精選課件5 V0V0 V7V7 V6V6 V5V5 V4V4 V3V3 V2V2 V1V1若圖的存儲結構為鄰接表，則若圖的存儲結構為鄰接表，則訪問鄰接點的順序不唯一，訪問鄰接點的順序不唯一

6、，深度優(yōu)先序列不是唯一的深度優(yōu)先序列不是唯一的 V0V0 V1V1 V3V3 V2V2 V7V7 V6V6 V5V5 V4V4 V0,V1,V3,V4,V7,V2,V5,V6, V0,V1,V3,V4,V7,V2,V5,V6, 求圖求圖G以以V0為起點的的深度優(yōu)先序列（設存儲結構為鄰接為起點的的深度優(yōu)先序列（設存儲結構為鄰接矩陣）矩陣）精選課件精選課件6void DFS(Graph G, int v)/* 從第從第v個頂點出發(fā)，遞歸地深度優(yōu)先遍歷圖個頂點出發(fā)，遞歸地深度優(yōu)先遍歷圖G*/ /* v是頂點在一維數組中的位置，假設是頂點在一維數組中的位置，假設G是非空圖是非空圖*/ visitedv

7、 =1; Visit(v); /*訪問第訪問第v個頂點個頂點*/ for ( w=FirstAdjVex(G, v); w; w=NextAdjVex(G, v, w) ) if (!visitedw) DFS(G, w); /*對對v的尚未訪問的鄰接頂點的尚未訪問的鄰接頂點w遞歸調用遞歸調用DFS*/輔助數組：輔助數組：int visitedMax_Vertex_Num ; 訪問標志數組訪問標志數組, ,全局變量，初始時所有分量全局變量，初始時所有分量全為全為0，visitedv=1表示頂點表示頂點v v已被訪問已被訪問. .visited0123400000深度優(yōu)先遍歷算法深度優(yōu)先遍歷算法

8、: :7.3 7.3 圖的遍歷圖的遍歷精選課件精選課件77.3 7.3 圖的遍歷圖的遍歷void DFSTraverseAL(ALGraph G)/*深度優(yōu)先遍歷以鄰接表存儲的圖深度優(yōu)先遍歷以鄰接表存儲的圖G*/int i; for (i=0;iG.vexnum; + i) visitedi=0; /*標志數組初始化標志數組初始化*/ for(i=0;inextarc) w=p-adjvex; /*w是是v的鄰接頂點的序號的鄰接頂點的序號*/ if (!visitedw) DFSAL(G, w); /*若若w尚未訪問尚未訪問, 遞歸調用遞歸調用DFS*/ /*DFSAL*/7.3 7.3 圖的

9、遍歷圖的遍歷精選課件精選課件9 在遍歷時，對圖中每個頂點至多調用一次在遍歷時，對圖中每個頂點至多調用一次DFSDFS函數，因為函數，因為一旦某個頂點被標志成已被訪問，就不再從它出發(fā)進行搜索。一旦某個頂點被標志成已被訪問，就不再從它出發(fā)進行搜索。因此，遍歷圖的過程實質上是對每個頂點查找其鄰接點的過因此，遍歷圖的過程實質上是對每個頂點查找其鄰接點的過程。其耗費的時間則取決于所采用的存儲結構。程。其耗費的時間則取決于所采用的存儲結構。 用鄰接矩陣做圖的存儲結構時，查找用鄰接矩陣做圖的存儲結構時，查找各個各個頂點的鄰接點頂點的鄰接點所需的時間為所需的時間為O(n2)，其中，其中n n為圖中頂點數。當以

10、鄰接矩陣做為圖中頂點數。當以鄰接矩陣做存儲結構時，深度優(yōu)先搜索遍歷圖的時間復雜度為存儲結構時，深度優(yōu)先搜索遍歷圖的時間復雜度為O(n2+n)。 當以鄰接表做圖的存儲結構時，找鄰接點所需時間為當以鄰接表做圖的存儲結構時，找鄰接點所需時間為O(e)，其中其中e e為無向圖中邊的數或有向圖中弧的數。因此，為無向圖中邊的數或有向圖中弧的數。因此，當以鄰接表做存儲結構時，深度優(yōu)先搜索遍歷圖的時間復雜當以鄰接表做存儲結構時，深度優(yōu)先搜索遍歷圖的時間復雜度為度為O(n+e)。7.3 7.3 圖的遍歷圖的遍歷精選課件精選課件10圖中某頂點圖中某頂點v v出發(fā)：出發(fā)：1 1）訪問頂點）訪問頂點v v ；2 2）

11、訪問）訪問v v的所有未被訪問的鄰接點的所有未被訪問的鄰接點w w1 1 ,w ,w2 2 , w, wk k ；3 3）依次從這些鄰接點出發(fā)，訪問它們的所有未被訪問的鄰）依次從這些鄰接點出發(fā)，訪問它們的所有未被訪問的鄰接點接點; ; 依此類推，直到圖中所有訪問過的頂點的鄰接點依此類推，直到圖中所有訪問過的頂點的鄰接點都被訪問；都被訪問；7.3.2 廣度優(yōu)先遍歷廣度優(yōu)先遍歷7.3 7.3 圖的遍歷圖的遍歷精選課件精選課件11 V0V0 V7V7 V6V6 V5V5 V4V4 V3V3 V2V2 V1V1 V0,V1,V2, V3,V4,V7,V5,V6 V0,V1,V2, V3,V4,V7,V

12、5,V6 V0V0 V1V1 V3V3 V2V2 V7V7 V6V6 V5V5 V4V4若圖的存儲結構為鄰接表，則若圖的存儲結構為鄰接表，則訪問鄰接點的順序不唯一，訪問鄰接點的順序不唯一，深度優(yōu)先序列不是唯一的深度優(yōu)先序列不是唯一的求圖求圖G以以V0為起點的的廣度優(yōu)先序列（設存儲結構為鄰為起點的的廣度優(yōu)先序列（設存儲結構為鄰接矩陣）接矩陣） 先被訪問的頂點，其先被訪問的頂點，其鄰接點也要先被訪問鄰接點也要先被訪問設一隊列保存已訪問設一隊列保存已訪問的頂點的頂點精選課件精選課件12Q 在鄰接表存儲結構上的廣度優(yōu)先搜索在鄰接表存儲結構上的廣度優(yōu)先搜索V0V0V1V1V2V2V3V3V4V4V7V7

13、V5V5V6V6V1V1V2V2V3V3V0V0V4V4V7V7V5V5V6V6 V0 V0 V7 V7 V6 V6 V5 V5 V4 V4 V3 V3 V2 V2 V1 V17.3 7.3 圖的遍歷圖的遍歷7012V0V2V3V1datafirstarc 0 1adjvex next3V4 3 0 5 1 1 2 7456 4V5V6V7 2 6 2 5 1 4 7 6精選課件精選課件13void BFSTraverse(MGraph G) /*從從v出發(fā)，廣度優(yōu)先遍歷連通圖出發(fā)，廣度優(yōu)先遍歷連通圖G*/ /*使用輔助隊列使用輔助隊列Q和訪問標志數組和訪問標志數組visited*/ for

14、(v=0; vG.vexnum; +i) visitedv=0; InitQueue(Q, G.vexnum); /*初始化空的輔助隊列初始化空的輔助隊列Q*/ for (v=0;vG.vexnum;+v) if(!visitedv) /*若若v尚未訪問尚未訪問*/ visitedv=1; Visit(v); EnQueue(Q,v); while (!QueueEmpty_Sq(Q) DeQueue(Q,u); /*隊頭元素出隊隊頭元素出隊,并賦值給并賦值給u*/ /*訪問訪問u所有未被訪問的鄰接點所有未被訪問的鄰接點*/ for(w=0; wG.vexnum; w+;) if (G.arc

15、su,w.adj & !visitedw) visitedw=1; Visit(w); EnQueue(Q,w); /*while*/ /*BFSTraverse*/7.3 7.3 圖的遍歷圖的遍歷精選課件精選課件14第七 章 圖 7.4 連通網的最小生成樹連通網的最小生成樹 7.4.1 生成樹生成樹 7.4.2 最小生成樹最小生成樹 7.4.3 構造最小生成樹的構造最小生成樹的Prim算法算法 7.4.4 構造最小生成樹的構造最小生成樹的Kruskal算法算法精選課件精選課件157.4.1 生成樹生成樹生成樹：生成樹：包含了無向圖包含了無向圖G G所有頂點的所有頂點的極小極小連通子圖

16、。連通子圖。1 1）“極小極小”含義：一個有含義：一個有n n個頂點的連通圖的生成樹有個頂點的連通圖的生成樹有n-1n-1條邊，刪除任何一條邊，子圖不再連通；在生成樹中條邊，刪除任何一條邊，子圖不再連通；在生成樹中再加一條邊必然形成回路。（生成樹包含了圖中的所有再加一條邊必然形成回路。（生成樹包含了圖中的所有頂點，但只有足以構成生成樹的頂點，但只有足以構成生成樹的n-1n-1條邊）條邊）2 2）一個圖可以有許多棵不同的生成樹；）一個圖可以有許多棵不同的生成樹；3 3）生成樹中任意兩個頂點間的路徑是唯一的；）生成樹中任意兩個頂點間的路徑是唯一的；4 4）含）含n n個頂點個頂點n-1n-1條邊的

17、圖不一定是生成樹。條邊的圖不一定是生成樹。7.4 7.4 最小的生成樹最小的生成樹精選課件精選課件167.4 7.4 最小的生成樹最小的生成樹 n n個個頂點的圖頂點的圖最多可存在最多可存在n(n-1)/2n(n-1)/2條邊條邊線路。求生成樹是為了在網絡中連通線路。求生成樹是為了在網絡中連通n n個頂點而選擇最少的個頂點而選擇最少的邊邊(n(n1)1)。 例如：一個通信網絡中，節(jié)點代表了路由器，為了使例如：一個通信網絡中，節(jié)點代表了路由器，為了使各路由器之間是連通的（數據可達），且不形成回路各路由器之間是連通的（數據可達），且不形成回路( (數據數據回到發(fā)送方回到發(fā)送方) )，則需建立該網絡

18、的生成樹。，則需建立該網絡的生成樹。精選課件精選課件17利用遍歷算法。利用遍歷算法。從連通圖中的任一頂點出發(fā)進行遍歷時，除出發(fā)從連通圖中的任一頂點出發(fā)進行遍歷時，除出發(fā)點外，其余頂點必須通過一條邊才能到達，所以遍歷點外，其余頂點必須通過一條邊才能到達，所以遍歷過程中經歷的邊有過程中經歷的邊有n-1n-1條，它和條，它和n n個頂點組成了連通圖個頂點組成了連通圖的一棵生成樹。的一棵生成樹。 由深度優(yōu)先搜索得到的是深度優(yōu)先生成樹；由廣度由深度優(yōu)先搜索得到的是深度優(yōu)先生成樹；由廣度優(yōu)先搜索得到的是廣度優(yōu)先生成樹。優(yōu)先搜索得到的是廣度優(yōu)先生成樹。精選課件精選課件18 V0 V0 V7 V7 V6 V6

19、 V5 V5 V4 V4 V3 V3 V2 V2 V1 V1深度遍歷：深度遍歷：V0V1V3V4V7V2 V5V6 V0 V0 V7 V7 V6 V6 V5 V5 V4 V4 V3 V3 V2 V2 V1 V17.4 7.4 最小的生成樹最小的生成樹 V0 V0 V7 V7 V6 V6 V5 V5 V4 V4 V3 V3 V2 V2 V1 V1深度優(yōu)先搜索生成樹深度優(yōu)先搜索生成樹精選課件精選課件19廣度遍歷：廣度遍歷： V0 V1 V2 V3 V4 V7 V5 V6 V0 V0 V7 V7 V6 V6 V5 V5 V4 V4 V3 V3 V2 V2 V1 V1 V0 V0 V7 V7 V6 V

20、6 V5 V5 V4 V4 V3 V3 V2 V2 V1 V1廣度優(yōu)先搜索生成樹廣度優(yōu)先搜索生成樹7.4 7.4 最小的生成樹最小的生成樹 V0 V0 V7 V7 V6 V6 V5 V5 V4 V4 V3 V3 V2 V2 V1 V1精選課件精選課件207.4.2 最小生成樹的概念最小生成樹的概念 由生成樹的定義可知，無向連通圖的生成樹不是惟一由生成樹的定義可知，無向連通圖的生成樹不是惟一的。的。 問題的提出：問題的提出：設要在設要在n n個城市間建立通信聯(lián)絡網，頂個城市間建立通信聯(lián)絡網，頂點點表示城市，權表示城市間建立通信線路所需花費代價。表示城市，權表示城市間建立通信線路所需花費代價。希望

21、找到一棵生成樹，它的每條邊上的權值之和（即建立希望找到一棵生成樹，它的每條邊上的權值之和（即建立該通信網所需花費的總代價）最小該通信網所需花費的總代價）最小最小代價生成樹。最小代價生成樹。7.4 7.4 最小的生成樹最小的生成樹精選課件精選課件21 最小生成樹定義：最小生成樹定義：對于一個網絡，它的所有生成樹對于一個網絡，它的所有生成樹中邊權值最小的生成樹稱為最小生成樹。中邊權值最小的生成樹稱為最小生成樹。 問題分析：問題分析：n n個城市間建立通信網，如何在可能的線路個城市間建立通信網，如何在可能的線路中選擇中選擇n-1n-1條，能把所有城市（頂點）均連起來，且總條，能把所有城市（頂點）均連

22、起來，且總耗費（各邊權值之和）最小。耗費（各邊權值之和）最小。即：如何在保證即：如何在保證n點連通點連通的前題下最節(jié)省經費的前題下最節(jié)省經費? ?精選課件精選課件221. 1. Prim 法基本步驟法基本步驟G=V,EUGT(1)G(2)(3)U(u,v)(4)(2) 、(3)U7.4.3 構造最小生成樹的構造最小生成樹的PrimPrim算法算法7.4 7.4 最小的生成樹最小的生成樹精選課件精選課件23V3V3V1V1V4V4V6V6V5V5V2V2651U= V1 V3V3V1V1V4V4V6V6V5V5V2V251654V3V3V4V4V6V6V5V5V2V21V1V1U= V1,V3

23、U= V1,V3 V3V3V1V1V4V4V6V6V5V5V2V216542V3V3V1V1V4V4V6V6V5V5V2V251654U= V1,V3,V6U= V1,V3,V67.4 7.4 最小的生成樹最小的生成樹V3V3V1V1V4V4V6V6V5V5V2V236521655462. 2. 過程演示過程演示精選課件精選課件24V3V3V1V1V4V4V6V6V5V5V2V216542U= V1,V3,V6,V4U= V1,V3,V6,V4 V3V3V1V1V4V4V6V6V5V5V2V216542U= V1,V3,V6,V4,V2 U= V1,V3,V6,V4,V2 V3V3V1V1V4

24、V4V6V6V5V5V2V215423U= V1,V3,V6,V4,V2,V5 U= V1,V3,V6,V4,V2,V5 7.4 7.4 最小的生成樹最小的生成樹V3V3V1V1V4V4V6V6V5V5V2V23652165546Prim 算法的時間復雜度為算法的時間復雜度為O(n2)精選課件精選課件257.4.3 7.4.3 構造最小生成樹的構造最小生成樹的KruskalKruskal算法算法1.1.基本思想：按網中權值遞增的順序構造最小生成樹。基本思想：按網中權值遞增的順序構造最小生成樹。 2.2.基本步驟基本步驟 1 1）設連通網）設連通網G=(V,E)G=(V,E)，令最小生成樹初始狀

25、態(tài)是只有，令最小生成樹初始狀態(tài)是只有n n個個頂點而無邊的非連通圖頂點而無邊的非連通圖T=(V,T=(V, ) )，每個頂點自成一個連，每個頂點自成一個連通分量；通分量； 2 2）在）在E E中選取代價最小的邊，若該邊依附的頂點落在中選取代價最小的邊，若該邊依附的頂點落在T T中中不同的連通分量上，則將此邊加入到不同的連通分量上，則將此邊加入到T T中；否則，舍去中；否則，舍去此邊，選取下一條代價最小的邊；此邊，選取下一條代價最小的邊； 3 3）依此類推，直至）依此類推，直至T T中所有頂點都在同一連通分量上為中所有頂點都在同一連通分量上為止。止。7.4 7.4 最小的生成樹最小的生成樹精選課

26、件精選課件26V3V3V1V1V4V4V6V6V5V5V2V2V3V3V4V4V6V6V5V5V2V21V1V1V3V3V1V1V4V4V6V6V5V5V2V212V3V3V1V1V4V4V6V6V5V5V2V2123V3V3V1V1V4V4V6V6V5V5V2V2164237.4 7.4 最小的生成樹最小的生成樹V3V3V1V1V4V4V6V6V5V5V2V236521655463. 3. 過程演示過程演示精選課件精選課件27V3V3V1V1V4V4V6V6V5V5V2V2165423V3V3V1V1V4V4V6V6V5V5V2V236521655467.4 7.4 最小的生成樹最小的生成樹

27、Kruskal 算法的時間復雜度為算法的時間復雜度為O(ne)。精選課件精選課件28 7.5 7.5 單源最短路徑單源最短路徑(Shortest Path)(Shortest Path) 從一個源點到其他各點的最短路徑從一個源點到其他各點的最短路徑精選課件精選課件29 交通咨詢系統(tǒng)、通訊網、計算機網絡中經常要尋找兩結交通咨詢系統(tǒng)、通訊網、計算機網絡中經常要尋找兩結點間最短路徑。例如：交通咨詢系統(tǒng)中：咨詢點間最短路徑。例如：交通咨詢系統(tǒng)中：咨詢A A到到B B的最短路的最短路徑；計算機網中如何發(fā)送徑；計算機網中如何發(fā)送E-mailE-mail才最節(jié)省費用（使才最節(jié)省費用（使E-mailE-mai

28、l由由A A到到B B沿最短路徑傳送）。沿最短路徑傳送）。 設用帶權的有向圖表示一個交通運輸網，圖中：設用帶權的有向圖表示一個交通運輸網，圖中： 頂點頂點表示城市表示城市 邊邊表示城市間的交通聯(lián)系表示城市間的交通聯(lián)系 權權表示此線路的長度或沿此線路運輸所花的時間表示此線路的長度或沿此線路運輸所花的時間或費用等或費用等 這類問題歸結為從某頂點出發(fā)，沿圖的邊到達另一頂點這類問題歸結為從某頂點出發(fā)，沿圖的邊到達另一頂點所經過的路徑中，各邊上權值之和最小的一條路徑所經過的路徑中，各邊上權值之和最小的一條路徑最短最短路徑。路徑上的第一個頂點為源點，最后一個頂點為終點。路徑。路徑上的第一個頂點為源點，最后

29、一個頂點為終點。 問題的提出問題的提出: :7.5 7.5 最短路徑最短路徑精選課件精選課件30精選課件精選課件31 從一個源點到其他各點的最短路徑從一個源點到其他各點的最短路徑1.1.7.5 7.5 最短路徑最短路徑2. 2. 基本思想基本思想精選課件精選課件32依據算法的基本思想把依據算法的基本思想把V V分成兩組：分成兩組：（1 1）S S：已求出最短路徑的頂點的集合：已求出最短路徑的頂點的集合（2 2）V-S=TV-S=T：尚未確定最短路徑的頂點集合：尚未確定最短路徑的頂點集合 將將T T中頂點按如下規(guī)則加入到中頂點按如下規(guī)則加入到S S中：中： （1 1）按遞增的次序產生最短路徑：從

30、源點）按遞增的次序產生最短路徑：從源點V V0 0到到S S中各頂點中各頂點的最短路徑長度都不大于從的最短路徑長度都不大于從V V0 0到到T T中任何頂點的最短路徑長中任何頂點的最短路徑長度度; ; （2 2）待求的最短路徑最多以已求出最短路徑的頂點為中間）待求的最短路徑最多以已求出最短路徑的頂點為中間點：從點：從V V0 0到某頂點的最短路徑中，只將到某頂點的最短路徑中，只將S S中的頂點作為中間中的頂點作為中間點點精選課件精選課件33（2 2）Dijkstra Dijkstra 算法的基本步驟算法的基本步驟7.5 7.5 最短路徑最短路徑精選課件精選課件34 1）圖用帶權鄰接矩陣存儲；）

31、圖用帶權鄰接矩陣存儲；2 2）引入一個輔助數組引入一個輔助數組dist。它的每一個分量。它的每一個分量disti表示表示當前找到的從源點當前找到的從源點v0 到終點到終點vi 的最短路徑的長度的最短路徑的長度 初始狀態(tài)：初始狀態(tài)： 若從源點若從源點v0 到頂點到頂點vi有邊，則有邊，則disti為該邊上的權為該邊上的權值；值； 若從源點若從源點v0 到頂點到頂點vi 沒有邊，則沒有邊，則disti為為 。3 3）數組）數組path表示從表示從V0到各終點的最短路徑上，此頂點到各終點的最短路徑上，此頂點的的前一頂點前一頂點的序號；若從的序號；若從V0 到某終點無路徑，則用到某終點無路徑，則用-1

32、-1 作為該結點前一頂點的序號作為該結點前一頂點的序號4)4)數組數組s標識標識V0 到該結點的最短路徑是否求出。到該結點的最短路徑是否求出。0 0表示表示沒求出，沒求出，1 1表示已求出。表示已求出。7.5 7.5 最短路徑最短路徑(3) (3) 算法實現(xiàn)算法實現(xiàn)精選課件精選課件357.5 7.5 最短路徑最短路徑260003013501010122601030135010101439000301350001013010000300160001011010000300-1 001000P4d4S4P3d3S3P2d2S2P1d1S1頂點4頂點3頂點2頂點1選取點01234精選課件精選課件36

33、 如何從表中讀取源點如何從表中讀取源點0 0到終點的最短路徑到終點的最短路徑？ 以頂點以頂點4 4為例：為例： (1) V0 (1) V0到頂點到頂點4 4的最短路徑為的最短路徑為6060。 (2) path4=2 path2=3 (2) path4=2 path2=3 path3=0 path3=0； 反過來排列，得到路徑反過來排列，得到路徑0, 3, 2, 40, 3, 2, 4，即，即V0V0到頂點到頂點V4V4的最短路徑。的最短路徑。7.5 7.5 最短路徑最短路徑2600030135010101226010301350101014390003013500010130100003001

34、600010110100003000 001000P4d4S4P3d3S3P2d2S2P1d1S1頂點4頂點3頂點2頂點1選取點精選課件精選課件37算法的時間復雜度為算法的時間復雜度為O(n2)精選課件精選課件38 7.6 AOV7.6 AOV網與拓撲排序網與拓撲排序精選課件精選課件397.6.1 7.6.1 有向無環(huán)圖的概念有向無環(huán)圖的概念1.1. 有向無環(huán)圖（有向無環(huán)圖（directed acycline graphdirected acycline graph）：沒有回路的有向圖。：沒有回路的有向圖。 含有公共子式的表達式含有公共子式的表達式 例如：表達式例如：表達式(a+b)(a+b)

35、* *(a+b-e/f)(a+b-e/f) a a - - + + b b * * / / e e f f 用用有向無環(huán)圖有向無環(huán)圖表示的表達式表示的表達式 流程圖：流程圖： 工程流程、生產過程中工序流程、程序流程、課程的流工程流程、生產過程中工序流程、程序流程、課程的流程。常用的兩種有向無環(huán)圖是：程。常用的兩種有向無環(huán)圖是：AOVAOV網，網，AOEAOE網。網。7.6 7.6 有向無環(huán)圖及其應用有向無環(huán)圖及其應用 - - a a + + b b * * / / e e f f a a + + b b 用用二叉樹二叉樹表示的表達式表示的表達式精選課件精選課件407.6.2 AOV AOV網與

36、拓撲排序網與拓撲排序活動活動活動的順序關系活動的順序關系AOVAOV網中不允許有回路，這意味著某項活動以自己為網中不允許有回路，這意味著某項活動以自己為先決條件。先決條件。7.6 7.6 有向無環(huán)圖及其應用有向無環(huán)圖及其應用精選課件精選課件41計算機專業(yè)的課程設置及其關系計算機專業(yè)的課程設置及其關系7.6 7.6 有向無環(huán)圖及其應用有向無環(huán)圖及其應用精選課件精選課件42 頂點表示課程，弧表示前提條件活動。若課程頂點表示課程，弧表示前提條件活動。若課程i i是課程是課程j j的先行課，的先行課，則必然存在弧則必然存在弧。由此得到如下。由此得到如下AOVAOV網：網： 在安排學習順序時，必須保證在

37、學習某門課前，已經學習了其先行課。在安排學習順序時，必須保證在學習某門課前，已經學習了其先行課。如何設置這些課程的學習順序，才能無矛盾、順利地完成學業(yè)？如何設置這些課程的學習順序，才能無矛盾、順利地完成學業(yè)？7.6 7.6 有向無環(huán)圖及其應用有向無環(huán)圖及其應用C1C3C2C4C5C6C7C8C9C10C11精選課件精選課件432. 2. 拓撲排序拓撲排序 拓撲序列：拓撲序列：有向圖有向圖D D的一個頂點序列稱作一個拓撲序列，的一個頂點序列稱作一個拓撲序列，對于該序列中任兩頂點對于該序列中任兩頂點v v、u u，若在，若在D D中中v v是是u u前趨，則在序前趨，則在序列中列中v v也是也是u

38、 u前趨。前趨。 拓撲排序：拓撲排序：把把AOVAOV網絡中各頂點按照它們相互之間的領網絡中各頂點按照它們相互之間的領先關系排列成一個線性序列的過程。先關系排列成一個線性序列的過程。 拓撲排序的應用：拓撲排序的應用：判斷工程流程的是否合理判斷工程流程的是否合理. . 如何判斷如何判斷AOVAOV網是否網是否存在有向回路？存在有向回路？利用拓撲排序檢測利用拓撲排序檢測AOVAOV網中網中是否存在環(huán)：是否存在環(huán)：對有向圖構對有向圖構造其頂點的拓撲有序序列，造其頂點的拓撲有序序列，若網中所有頂點都在它的若網中所有頂點都在它的拓撲有序序列中，則該拓撲有序序列中，則該AOVAOV網必定不存在環(huán)。網必定不

39、存在環(huán)。7.6 7.6 有向無環(huán)圖及其應用有向無環(huán)圖及其應用精選課件精選課件443.3.拓撲排序算法拓撲排序算法（1 1）在）在AOVAOV網中選一個網中選一個沒有前驅的頂點沒有前驅的頂點v v并將其輸出；并將其輸出；（2 2）從網中刪除頂點）從網中刪除頂點v v和和所有以所有以v v為尾的弧為尾的??； （3 3）重復）重復(1)(1)、(2)(2)，直至全部頂點均已輸出；或者當圖，直至全部頂點均已輸出；或者當圖中不存在無前驅的頂點為止。中不存在無前驅的頂點為止。7.6 7.6 有向無環(huán)圖及其應用有向無環(huán)圖及其應用精選課件精選課件45C1C3C2C9C5C10C7C6C8C11C4拓撲序列：C

40、17.6 7.6 有向無環(huán)圖及其應用有向無環(huán)圖及其應用精選課件精選課件46C3C2C9C5C10C7C6C8C11C4拓撲序列：C1，C2拓撲序列：C17.6 7.6 有向無環(huán)圖及其應用有向無環(huán)圖及其應用精選課件精選課件47C3C9C5C10C7C6C8C11C4拓撲序列：C1，C2拓撲序列：C1，C2，C37.6 7.6 有向無環(huán)圖及其應用有向無環(huán)圖及其應用精選課件精選課件48C9C5C10C7C6C8C11C4拓撲序列：C1，C2，C3拓撲序列：C1，C2，C3，C97.6 7.6 有向無環(huán)圖及其應用有向無環(huán)圖及其應用精選課件精選課件49C5C10C7C6C8C11C4拓撲序列：拓撲序列：

41、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 一個一個AOVAOV網的拓撲網的拓撲序列不是唯一的。序列不是唯一的。如何計算機上實現(xiàn)如何計算機上實現(xiàn)對有向圖的拓撲排序？對有向圖的拓撲排序？7.6 7.6 有向無環(huán)圖及其應用有向無環(huán)圖及其應用精選課件精選課件50拓撲排序算法拓撲排序算法: :（1 1）在

42、）在AOVAOV網中選一個網中選一個沒有前驅的頂點沒有前驅的頂點v v并將其輸出；并將其輸出；（2 2）從網中刪除頂點）從網中刪除頂點v v和和所有以所有以v v為尾的弧為尾的弧； （3 3）重復）重復(1)(1)、(2)(2)，直至全部頂點均已輸出；或者當圖，直至全部頂點均已輸出；或者當圖中不存在中不存在無前驅無前驅的頂點為止。的頂點為止。7.6 7.6 有向無環(huán)圖及其應用有向無環(huán)圖及其應用 拓撲排序方法的另一種等價描述：拓撲排序方法的另一種等價描述： （1 1） 選擇一選擇一入度為入度為0 0頂點頂點v v，輸出；，輸出； （2 2） 將將v v鄰接到的頂點的入度減鄰接到的頂點的入度減1

43、1； （3 3） 重復重復(1)(1)、(2)(2)，直至全部頂點均已輸出，直至全部頂點均已輸出; ;或圖中或圖中沒有沒有入度為入度為0 0的頂點為止。的頂點為止。精選課件精選課件51拓撲排序的數據結構：拓撲排序的數據結構： 以鄰接表存儲有向圖，并在頂點結點中增加該頂點以鄰接表存儲有向圖，并在頂點結點中增加該頂點的入度信息。的入度信息。算法：算法： 1 1）為方便查找入度為）為方便查找入度為0 0的元素，將鄰接表中所有入度為的元素，將鄰接表中所有入度為0 0的頂點進棧的頂點進棧 2 2）棧非空時，輸出棧頂元素）棧非空時，輸出棧頂元素VjVj并退棧；并退棧； 3 3）在鄰接表中查找）在鄰接表中查

44、找VjVj的直接后繼的直接后繼VkVk，把，把VkVk的入度減的入度減1 1；若若VkVk的入度為的入度為0 0則進棧；則進棧； 重復上述操作直至?？諡橹?。若棧空時輸出的頂點重復上述操作直至?？諡橹?。若棧空時輸出的頂點個數不是個數不是n n，則有向圖有環(huán)；否則，拓撲排序完畢。，則有向圖有環(huán)；否則，拓撲排序完畢。精選課件精選課件52例例: :0123450122inlink 4 4 3 2vex next3 1 4 1 300123453210405top7.6 7.6 有向無環(huán)圖及其應用有向無環(huán)圖及其應用精選課件精選課件530122inlink 4 4 3 2vex next3 1 4 1 3

45、0012345輸出序列：53210405top7.6 7.6 有向無環(huán)圖及其應用有向無環(huán)圖及其應用精選課件精選課件540122inlink 4 4 3 2vex next3 1 4 1 30012345輸出序列：5p321040top7.6 7.6 有向無環(huán)圖及其應用有向無環(huán)圖及其應用精選課件精選課件550122inlink 4 4 3 2vex next 1 4 1 30012345p321040top輸出序列：57.6 7.6 有向無環(huán)圖及其應用有向無環(huán)圖及其應用精選課件精選課件560122inlink 4 4 3 2vex next 1 4 1 30012345p輸出序列：5321040

46、top7.6 7.6 有向無環(huán)圖及其應用有向無環(huán)圖及其應用精選課件精選課件57012inlink 4 4 3 2vex next 1 4 1 30012345p321040top輸出序列：57.6 7.6 有向無環(huán)圖及其應用有向無環(huán)圖及其應用精選課件精選課件58012inlink 4 4 3 2vex next 1 4 1 30012345p=NULL321040top輸出序列：57.6 7.6 有向無環(huán)圖及其應用有向無環(huán)圖及其應用精選課件精選課件590112inlink 4 4 3 2vex next21 4 1 30012345輸出序列：5 032104top7.6 7.6 有向無環(huán)圖及其

47、應用有向無環(huán)圖及其應用精選課件精選課件600112inlink 4 4 3 2vex next2 1 4 1 30012345p32104top輸出序列： 5 07.6 7.6 有向無環(huán)圖及其應用有向無環(huán)圖及其應用精選課件精選課件61012inlink 4 4 3 2vex next2 1 4 1 30012345p332104top輸出序列： 5 0 7.6 7.6 有向無環(huán)圖及其應用有向無環(huán)圖及其應用精選課件精選課件62012inlink 4 4 3 2vex next2 1 4 1 30012345p332104top輸出序列： 5 07.6 7.6 有向無環(huán)圖及其應用有向無環(huán)圖及其應用

48、精選課件精選課件6302inlink 4 4 3 2vex next2 1 4 1 30012345p332104top2輸出序列： 5 07.6 7.6 有向無環(huán)圖及其應用有向無環(huán)圖及其應用精選課件精選課件6402inlink 4 4 3 2vex next2 1 4 1 30012345p332104top2輸出序列： 5 07.6 7.6 有向無環(huán)圖及其應用有向無環(huán)圖及其應用精選課件精選課件650inlink 4 4 3 2vex next2 1 4 1 30012345p332104top2輸出序列： 5 07.6 7.6 有向無環(huán)圖及其應用有向無環(huán)圖及其應用精選課件精選課件660in

49、link 4 4 3 2vex next2 1 4 1 30012345p=NULL332104top2輸出序列： 5 07.6 7.6 有向無環(huán)圖及其應用有向無環(huán)圖及其應用精選課件精選課件670001inlink 4 4 3 2vex next2 1 4 1 30012344輸出序列： 5 0 2332104top7.6 7.6 有向無環(huán)圖及其應用有向無環(huán)圖及其應用精選課件精選課件680001inlink 4 4 3 2vex next2 1 4 1 30012345p332104top輸出序列： 5 0 27.6 7.6 有向無環(huán)圖及其應用有向無環(huán)圖及其應用精選課件精選課件690001in

50、link 4 4 3 2vex next 1 4 1 30012345p332104top輸出序列： 5 0 27.6 7.6 有向無環(huán)圖及其應用有向無環(huán)圖及其應用精選課件精選課件700001inlink 4 4 3 2vex next 1 4 1 30012345p332104top輸出序列： 5 0 2 7.6 7.6 有向無環(huán)圖及其應用有向無環(huán)圖及其應用精選課件精選課件71000inlink 4 4 3 2vex next 1 4 1 30012345p332104top1輸出序列： 5 0 27.6 7.6 有向無環(huán)圖及其應用有向無環(huán)圖及其應用精選課件精選課件72000inlink 4

51、 4 3 2vex next 1 4 1 30012345p=NULL332104top1輸出序列： 5 0 27.6 7.6 有向無環(huán)圖及其應用有向無環(huán)圖及其應用精選課件精選課件730000inlink 4 4 3 2vex next1 1 4 1 30012345輸出序列： 5 0 2 1332104top7.6 7.6 有向無環(huán)圖及其應用有向無環(huán)圖及其應用精選課件精選課件740000inlink 4 4 3 2vex next1 1 4 1 30012345p=NULL332104top輸出序列：5 0 2 17.6 7.6 有向無環(huán)圖及其應用有向無環(huán)圖及其應用精選課件精選課件75000

52、0inlink 4 4 3 2vex next1 1 4 1 3001234532104top輸出序列：5 0 2 1 37.6 7.6 有向無環(huán)圖及其應用有向無環(huán)圖及其應用精選課件精選課件760000inlink 4 4 3 2vex next1 1 4 1 30012345p32104top輸出序列：5 0 2 1 37.6 7.6 有向無環(huán)圖及其應用有向無環(huán)圖及其應用精選課件精選課件770000inlink 4 4 3 2vex next 1 4 1 30012345p432104top輸出序列：5 0 2 1 37.6 7.6 有向無環(huán)圖及其應用有向無環(huán)圖及其應用精選課件精選課件780

53、000inlink 4 4 3 2vex next 1 4 1 30012345p=NULL432104top輸出序列：5 0 2 1 37.6 7.6 有向無環(huán)圖及其應用有向無環(huán)圖及其應用精選課件精選課件790000inlink 4 4 3 2vex next0 1 4 1 30012345輸出序列：5 0 2 1 3 4432104top7.6 7.6 有向無環(huán)圖及其應用有向無環(huán)圖及其應用精選課件精選課件800000inlink 4 4 3 2vex next0 1 4 1 30012345p=NULL32104top輸出序列：5 0 2 1 3 47.6 7.6 有向無環(huán)圖及其應用有向無

54、環(huán)圖及其應用精選課件精選課件81拓撲排序算法分析拓撲排序算法分析:建鄰接表：建鄰接表：T(n)=O(n+e)搜索入度為搜索入度為0的頂點的時間：的頂點的時間：T(n)=O(n)拓撲排序：拓撲排序：T(n)=O(n+e)7.6 7.6 有向無環(huán)圖及其應用有向無環(huán)圖及其應用精選課件精選課件827.7 7.7 AOEAOE網網7.6 7.6 有向無環(huán)圖及其應用有向無環(huán)圖及其應用精選課件精選課件83頂點表示事件頂點表示事件邊表示活動邊表示活動事件事件V Vj j發(fā)生發(fā)生表示表示a ak k已結束已結束ak VjVi事件事件V Vi i發(fā)生發(fā)生表示活動表示活動a ak k可以開始可以開始 V3V1V4V6V5V2a4=3a1=3a2=2a6=3a5=4a3=2a7=2a8=1AOE網網事件事件 V V1 1表示整個工程開始表示整個工程開始事件事件 V V6 6表示整個工程結束表示整個工程結束7.6 7.6 有向無環(huán)圖及其應用有向無環(huán)圖及其應用精選課件精選課件847.6 7.6 有向無環(huán)圖及其應用有向無環(huán)圖及其應用精選課件精選課件85