【正文】 計算機(jī)基礎(chǔ) C3 離散數(shù)學(xué) C1, C2 C4 數(shù)據(jù)結(jié)構(gòu) C3, C2 C5 高級語言程序設(shè)計 C2 C6 編譯原理 C5, C4 C7 操作系統(tǒng) C4, C9 C8 普通物理 C1 C9 計算機(jī)原理 C8 81 有向圖的應(yīng)用 兩個問題 ?整個工程能否順利進(jìn)行？ ?哪些活動是影響工程按期完工的關(guān)鍵？ —— 拓?fù)渑判? —— 關(guān)鍵路徑 82 有向圖的應(yīng)用 —— 拓?fù)渑判? AOV 網(wǎng) ?用頂點表示活動，用弧表示活動間的優(yōu)先關(guān)系的有向圖，稱為頂點表示活動的網(wǎng)（ Activity On Vertices） ?若 vi , vj 是圖中的有向邊，則表示活動 vi 必須先于活動 vj 進(jìn)行 ? AOV 網(wǎng)中不允許有回路，這意味著某項活動不能以自己為先決條件 83 有向圖的應(yīng)用 —— 拓?fù)渑判? ?例 學(xué)生課程學(xué)習(xí)工程圖 84 有向圖的應(yīng)用 —— 拓?fù)渑判? 由給定的 AOV 網(wǎng)所描述的工程是否可行？ ?檢測方法：拓?fù)渑判? ?對有向圖構(gòu)造其頂點的拓?fù)溆行蛐蛄?，若網(wǎng)中所有頂點都在它的拓?fù)溆行蛐蛄兄校瑒t該 AOV 網(wǎng)必定不存在回路，工程可行。 85 有向圖的應(yīng)用 —— 拓?fù)渑判? 概念 ?拓?fù)洌ㄓ行颍┬蛄? ?在 AOV 網(wǎng)中若將各個頂點（代表各個活動）排列成一個線性有序的序列 v1, v2, …, v n，使得若從頂點 vi 到 vj 有一條有向路徑，則在序列中頂點 vi 必須排在頂點 vj 之前。 86 有向圖的應(yīng)用 —— 拓?fù)渑判? ?例，對學(xué)生選課工程圖進(jìn)行拓?fù)渑判?，得到的拓?fù)溆行蛐蛄袨? C1 , C2 , C3 , C4 , C5 , C6 , C8 , C9 , C7 或 C1 , C8 , C9 , C2 , C5 , C3 , C4 , C7 , C6 拓?fù)湫蛄胁⒉晃ㄒ? 87 有向圖的應(yīng)用 —— 拓?fù)渑判? ?例，對下列有向圖不能求得它的拓?fù)溆行蛐蛄? B D A C 因為圖中存在一個有向回路 {B, C, D} 88 有向圖的應(yīng)用 —— 拓?fù)渑判? 拓?fù)渑判虻乃枷? ?輸入一個 AOV 網(wǎng)，令 n 為頂點個數(shù)。 ?(2) 從圖中刪去該頂點，同時刪去與該頂點關(guān)聯(lián)的弧。這說明圖中還剩下一些頂點，它們都有直接前驅(qū)，再也找不到?jīng)]有前驅(qū)的頂點了。 89 有向圖的應(yīng)用 —— 拓?fù)渑判? ?例 e a b c g h d f a b h c d g f e 在算法中需要用定量的描述替代定性的概念 ?? 入度為零的頂點 ?? 弧頭頂點的入度減 1 輸出 沒有前驅(qū)的頂點 刪除頂點及以它為尾的弧 90 有向圖的應(yīng)用 —— 拓?fù)渑判? 拓?fù)渑判虻乃惴ㄋ枷? ?圖的存儲：鄰接表 ?增設(shè)一個數(shù)組 indegree[ ]，記錄各個頂點的入度 ?在輸入數(shù)據(jù)時，每輸入一條弧 j, k，就需要建立一個弧結(jié)點，將它鏈入相應(yīng)弧鏈表中，并統(tǒng)計入度信息 EArcNode *p = new EArcNode (k)。 ghead[j].firstout = p。 //頂點 k 入度加 1 91 有向圖的應(yīng)用 —— 拓?fù)渑判? ?使用一個鏈?zhǔn)綏＃?存放入度為零的頂點 ?只要出現(xiàn)入度為零的頂點，就將它加入棧中 ?由于表頭結(jié)點的“入度計數(shù)域”在變成 0之后，已經(jīng)無用，故用它作為鏈?zhǔn)綏? ?使用頂點棧的拓?fù)渑判蛩惴梢悦枋鋈缦? ?(1) 建立入度為零的頂點棧； ?(2) 當(dāng)入度為零的頂點棧不空時，重復(fù)執(zhí)行 ? 從頂點棧中退出一個頂點，并輸出之； ? 該頂點發(fā)出的所有弧的終點的入度減 1； ? 如果弧的終點入度減為至 0，則該頂點壓入頂點棧； ?(3) 如果輸出頂點個數(shù)少于 AOV 網(wǎng)的頂點個數(shù)，則說明網(wǎng)中存在有向回路；否則拓?fù)渑判蛲瓿伞? for (i=0； in； i++) if (!indegree[i]) { indegree[i]=top； top=i。 count=0； 93 有向圖的應(yīng)用 —— 拓?fù)渑判? while (top1) { i=top。 couti； count++； for (p=ghead[i].firstout； p； p=plink) { k=padjvex； if (!(indegree[k])) { indegree[k]=top； top=k。 ? 從始點到終點的有向路徑可能不止一條，完成不同路徑的活動所需的時間也可能不同，但只有各條路徑上所有活動都完成了，整個工程才算完成。 ?從開始頂點到結(jié)束頂點的這條最長的路徑稱為關(guān)鍵路徑（ Critical Path） ?關(guān)鍵路徑上的所有活動稱為關(guān)鍵活動 ?說明：關(guān)鍵路徑可能不止一條 100 有向圖的應(yīng)用 —— 關(guān)健路徑 問題 2—— 為縮短工期，應(yīng)當(dāng)加快哪些活動？ ?要找出關(guān)鍵路徑，必須找出關(guān)鍵活動，只有提高關(guān)鍵活動的功效，才可能縮短整個工期。若圖中有回路則結(jié)束。 4）根據(jù)各點的 ee 和 le 的值，求每個活動（?。┑淖钤玳_始時間 e(i) 和最遲開始時間 l(i)。 105 有向圖的應(yīng)用 —— 關(guān)健路徑 算法 bool TopologicalSort(Stack amp。 //S是入度為零頂點棧， T為拓?fù)湫蛄许旤c棧。 Stack S。 ee[0..n1]=0。 kn。 106 有向圖的應(yīng)用 —— 關(guān)健路徑 while (!()) { j=()。 count++。 p。 if (indegree[k]==0) (k)。 //對 j的各后繼點 k修改 ee[k] } } if(countn) return false。 } // TopologicalSort 107 有向圖的應(yīng)用 —— 關(guān)健路徑 void CriticalPath( ) { Stack T。 le[0..n1]=ee[n1]。 p。 if (le[k]dut(j,k)le[j]) le[j]=le[k]dut(j,k)。 jn。p。 tag=(ee[j]==le[k]dut(j,k))?’*’:’ ‘。 } }//CriticalPath 108 有向圖的應(yīng)用 —— 關(guān)健路徑 ?例 頂點 ee[i] le[i] v0 v1 v2 v3 v4 v5 v6 v7 v8 0 6 4 5 7 7 16 14 18 0 6 6 8 7 10 16 14 18 活動 e[k] l[k] le a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 0 0 0 0 2 2 0 3 3 6 6 0 4 6 2 5 8 3 7 7 0 7 7 0 7 10 3 16 16 0 14 14 0 ????????????????????)}(|,)(m i n {)()1()1()}(|,)(m a x {)(0)0(jSiijdutilejleneenlejPijidutieejeeee????????),()()()()(vudutvleilueeie109 有向圖的應(yīng)用 —— 關(guān)健路徑 算法分析 ?拓?fù)渑判蚯? ee[i] 和逆拓?fù)溆行蚯? le[i] 時，所需時間為 O(n+e) ?求各個活動的 e[k] 和 l[k] 時所需時間為 O(e) ?總共花費時間仍然是 O(n+e) 110 最短路徑（ Shortest Path） 111 最短路徑（ Shortest Path） 求從某個源點到其余各點的最短路徑 ?—— Dijkstra 算法 每一對頂點之間的最短路徑 ?—— Floyd 算法 112 最短路徑 —— 求單源最短路徑 單源最短路徑問題 ?如果從圖中某一頂點（稱為源點）到達(dá)另一頂點（稱為終點）的路徑可能不止一條，如何找到一條路徑使得沿此路徑上各邊上的權(quán)值總和達(dá)到最小。 ?規(guī)定各邊（或?。┥系臋?quán)值大于或等于 0。 ?第一條最短路徑長度的求法 ?這條路徑必定只含一條弧 v0, v1 ，并且這條弧的權(quán)值最小。 ?dist[i] ← cost[0][i], i= 1, …,n 1。 ?S ← S ∨ { k }。 119 最短路徑 —— 求單源最短路徑 計算最短路徑的圖鄰接矩陣類的定義 const int Vexnum =20； //圖中最大頂點個數(shù) define max ∞ //定義無窮大 class Graph { //圖的類定義 float cost[Vernum][Vernum]； float dist [Vexnum]； //最短路徑長度數(shù)組 int path[Vexnum]； //最短路徑頂點序列數(shù)組 int find[Vexnum]； //最短路徑頂點集 public: void ShortestPath (int， int)； int choose ( int )； }； // Graph 120 最短路徑 —— 求單源最短路徑 Dijkstra 描述的單源最短路徑算法 void ShortestPath_DIJ (int v0。 int *dist) { for (v=0。 v++) { find[v]=0。 dist[v]=cost[v0][v]。 for (i=1。 i++){ k=mininum(dist)。 for (w=1。 w++) if (!find[w] amp。 cost[k][w]max) if (dist[w]dist[k]+cost[k][w]) { dist[w]=dist[k]+cost[k][w]。 } } }// ShortestPath_DIJ 算法的時間復(fù)雜度 ： O(n2) 121 最短路徑 —— 求單源最短路徑 Dijkstra算法中各輔助數(shù)組的變化 選 取 頂點 1 頂點 2 頂點 3 頂點 4 終 點 f [1] d [1] p [1] f [2] d [2] p [2] f [3] d [3] p [3] f [4] d [4] p [4] 0 0 10 0 0 ? 1 0 30 0 0 100 0 1 1 10 0 0 60 1 0 30 0 0 100 0 3 1 10 0 0 50 3 1 30 0 0 90 3 2 1 10 0 1 50 3 1 30 0 0 60 2 4 1 10 0 1 50 3 1 30 0 1 60 2 如何從表中讀取源點 0到終點 v的最短路徑？舉頂點 4為例 path[4]=2 →path[2]=3 → path[3] = 0 ， 反過來排列，得到路徑 0324，這就是源點 0到終點 4的最短路徑。) ?方法二： Floyd算法 —— T(n)=O(n179。 ?所有頂點試探完畢，算法結(jié)