【導(dǎo)讀】圖形結(jié)構(gòu)中，結(jié)點(diǎn)之間的關(guān)系可以是任意的，任意兩個數(shù)據(jù)元素之間都可能相關(guān)。果間接地用圖來表示，處理起來比較方便。離，有則輸出實(shí)際距離，無則輸出道路不直接相通。形結(jié)構(gòu)有何區(qū)別？G1是強(qiáng)連通圖嗎？寫出G2的鄰接矩陣、鄰接表和鄰接多重表。//對無權(quán)圖，用1或0表示相鄰否；//對帶權(quán)圖，則為權(quán)值類型。很容易判斷頂點(diǎn)i和頂點(diǎn)j是否有弧相連.矩陣是對稱的，可壓縮存儲（上（下）三角;第i行或第i列中1的個數(shù)為頂點(diǎn)i的度;矩陣中1的個數(shù)的一半為圖中邊的數(shù)目;對稀疏圖而言尤其浪費(fèi)空間?？臻g效率高；容易尋找頂點(diǎn)的鄰接點(diǎn)；結(jié)點(diǎn)對應(yīng)的單鏈表，沒有鄰接矩陣方便。

　　

【正文】 作業(yè) 1 假設(shè)圖 G采用鄰接表存儲，分別設(shè)計實(shí)現(xiàn)以下要求的算法： （ 1）求圖 G中每各頂點(diǎn)的出度； （ 2）求圖 G中出度最大的一個頂點(diǎn)，輸出該頂點(diǎn)編號； （ 3）計算圖 G中出度為 0的頂點(diǎn)數(shù)； （ 4）判斷圖 G中是否存在邊 i， j。 假設(shè)圖 G采用鄰接表存儲，編寫一個實(shí)現(xiàn)連通圖 G的深度優(yōu)先遍歷（從頂點(diǎn) v出發(fā)）的非遞歸算法。 第 7章 圖 圖的定義和術(shù)語 圖的存儲結(jié)構(gòu) 圖的遍歷操作 圖的連通性問題 有向無環(huán)圖及其應(yīng)用 最短路徑 有向無環(huán)圖及其應(yīng)用 一個無環(huán)的有向圖稱做有向無環(huán)圖 (DAG）。它在我們的生活中有廣泛的應(yīng)用。 ? 有向無環(huán)圖是描述含有 公共子式 的 表達(dá)式 的有效工具。 ? 有向無環(huán)圖也是描述一項(xiàng) 工程或系統(tǒng) 的 進(jìn)行過程 的有效工具。 對整個工程和系統(tǒng)，人們關(guān)心的是兩個方面的問題： 一是工程能否順利進(jìn)行；二是估算整個工程完成所必須的最短時間。 拓?fù)渑判? 問題 1：假設(shè)以有向圖表示一個工程的施工圖或程序的流程圖，則程序中能否出現(xiàn)回路？ 問題 2：如何檢查有向圖中是否存在回路？ 問題 3：何謂拓?fù)渑判颍? 拓?fù)渑判? 拓?fù)渑判?：由某個集合上的一個 偏序 得到該集合上的一個 全序 ，這個操作稱為拓?fù)渑判颉? (a)偏序 (b)全序 V1 V4 V3 V2 V1 V4 V3 V2 拓?fù)渑判? 何謂拓?fù)渑判?? 換句話說：對有向圖進(jìn)行如下操作，按照有向圖給出的次序關(guān)系，將圖中的頂點(diǎn)排成一個 線性序列 ，對于沒有限定次序關(guān)系的頂點(diǎn)，則可以人為加上 任意 的次序關(guān)系。 問題 4：如何進(jìn)行拓?fù)渑判颍? 拓?fù)渑判? 方法： (1)從入度為 0的頂點(diǎn)（如 v0）開始； (2)輸出 v0，將與之相關(guān)聯(lián)的尾端弧刪除； (3)重復(fù)上述兩步，直至圖中全部頂點(diǎn)已輸出，或不存在無前驅(qū)頂點(diǎn)為止。 前一種情況說明有向圖中不存在環(huán)，后一種情況則說明有向圖中存在環(huán)。 檢測一個有向圖是否存在回路的方法 ：對有向圖構(gòu)造其頂點(diǎn)的 拓?fù)溆行蛐蛄?，若圖中 所有頂點(diǎn) 都在它的 拓?fù)溆行蛐蛄兄?，則該圖中必定 不存在環(huán) 。 拓?fù)渑判? 拓?fù)湫蛄?1： C1C2C3C5C8C4C9C6C7 拓?fù)湫蛄?2： C2C5C1C3C8C4C9C6C7 問題 5：有向圖的拓?fù)溆行蛐蛄惺欠裎ㄒ唬? C8 C3 C5 C4 C9 C6 C7 C1 C2 拓?fù)渑判? 分析： （ 1）拓?fù)渑判蜃铌P(guān)鍵的操作是什么？ （ 2）圖的存儲結(jié)構(gòu)？ （ 3）如何處理多個入度為 0的頂點(diǎn)？ 問題 6：如何在計算機(jī)內(nèi)實(shí)現(xiàn)有向圖的拓?fù)渑判颍? 拓?fù)渑判? 實(shí)現(xiàn)拓?fù)渑判虻乃惴ɑA(chǔ) 存貯結(jié)構(gòu) :假設(shè)有向圖以鄰接表的形式存儲 操作過程 : 將所有入度為 0的頂點(diǎn)入棧； 當(dāng)棧非空時重復(fù)執(zhí)行下列操作： 從棧中退出頂點(diǎn) k； （ 1） 將 k頂點(diǎn)的信息輸出； （ 2） 將與 k鄰接的所有頂點(diǎn)的入度減 1。 拓?fù)渑判驐Ｊ纠?: C0 C1 C2 C3 C4 C5 C0 C1 C2 C3 0 C4 C5 0 degree data adj 1 3 0 1 0 3 1 vex link 3 0 5 1 5 0 0 1 5 0 拓?fù)渑判蛩惴ǖ臅r間復(fù)雜度分析 如果給定的有向圖有 n個頂點(diǎn)和 e條邊，那么求各頂點(diǎn)入度的時間為 O（ e），在拓?fù)渑判虻倪^程中，查找入度為零的頂點(diǎn)的時間為 O（ n），頂點(diǎn)進(jìn)棧及退棧輸出共執(zhí)行 n次，入度減 1的操作執(zhí)行 e次，所以，總的執(zhí)行時間為 O（ n+e） 。 拓?fù)渑判? 問題 7:什么是 AOV網(wǎng) ? C8 C3 C5 C4 C9 C6 C7 C1 C2 關(guān)鍵路徑 問題 1:什么是 AOE網(wǎng) ? 有什么用 ? 假設(shè)以有向網(wǎng)表示一個施工流程圖，弧上的權(quán)值表示完成該項(xiàng)子工程所需時間。 問： 哪些子工程項(xiàng)是“關(guān)鍵工程”？ 即： 哪些子工程項(xiàng)將影響整個工程的完成期限 整個工程完成的時間為： 從有向圖的源點(diǎn)到匯點(diǎn)的最長路徑 關(guān)鍵路徑 關(guān)鍵路徑示例 :p183 圖 v0 v1 v2 v3 v4 v5 v6 v7 v8 6 4 5 2 1 1 8 7 2 4 4 源點(diǎn) 匯點(diǎn) 關(guān)鍵路徑 相關(guān)術(shù)語 : 源點(diǎn) : p183 匯點(diǎn) : p183 AOE網(wǎng) : p183 關(guān)鍵路徑 :p183 關(guān)鍵活動 : p183 縮短工期結(jié)論 :p186 關(guān)鍵路徑 求關(guān)鍵路徑的目的 :求關(guān)鍵活動 確定哪些是關(guān)鍵活動 ,關(guān)鍵 活動 就是要找最早開始時間 e(i)與最遲開始時間 l(i)相等的活動 ,要首先確定 事件 的最早開始時間 ve(i)和最遲開始時間 vl(i). 關(guān)鍵路徑 求關(guān)鍵活動 : 假設(shè)第 i 條弧為 j, k,如果弧為 j, k的持續(xù)時間為dut(j, k), 則對第 j 個頂點(diǎn)而言 “ 事件 (頂點(diǎn) )”的最早發(fā)生時間 ve(j), ve(k) “事件 (頂點(diǎn) )”的最遲發(fā)生時間 vl(j), vl(k) 對第 i 項(xiàng)活動而言 “ 活動 (弧 )”的最早開始時間 e(i) “活動 (弧 )”的最遲開始時間 l(i) e(i)=ve(j) l(i)=vl(k) dut(j, k) 所以： 要先求事件的最早和最晚發(fā)生時間 關(guān)鍵路徑 第一步 :事件 i的最早發(fā)生時間 ,前邊活動都完成，最長路徑長度 從 ve(源點(diǎn) ) = 0開始向前遞推 , ve(j) = Max{ve(i) + dut(i, j)} (j=1,2,..n1, j, k屬于所有以 j為 頭 的弧的集合 ) 第二步 :事件 i的最早發(fā)生時間 ,從 vl(n1)=ve(n1)起向后遞推 . vl(匯點(diǎn) ) = ve(匯點(diǎn) )； vl(i) = Min{vl(k) – dut(i, j)} (i=n2,n1…0, i,j屬于所有以 i為尾的弧的集合 ) 第三步 :求各個活動的最早開始時間和最晚發(fā)生時間 ,確定關(guān)鍵路徑 關(guān)鍵路徑 意義 : p186 用 AOE網(wǎng)來估算某些工程的時間是非常有用的 ,關(guān)鍵活動的速度的提高是有限的 ,只有在 不改變網(wǎng)的關(guān)鍵路徑的前提 下 ,提高關(guān)鍵活動的效率才有效 ，關(guān)鍵活動受諸多方面的影響 ,如果某個條件改變可 ,可能會改變關(guān)鍵活動 . 如果網(wǎng)中有 多條關(guān)鍵路徑 ,要提高整個工期的速度 ,則要 同時提高 在幾條關(guān)鍵路徑上的活動的效率 . 典型用途： 交通網(wǎng)絡(luò)中常常提出這樣的問題：從甲地到乙地之間是否有公路連通 ?在有多條通路的情況下，哪一條路最短 ? 問題抽象： 在 帶權(quán)有向圖 中 A點(diǎn)（源點(diǎn)）到達(dá) B點(diǎn)（終點(diǎn)）的多條路徑中，尋找一條各邊權(quán)值之和最小 的路徑，即最短路徑 （注：最短路徑與最小生成樹不同，路徑上不一定包含 n個頂點(diǎn)） v1 v2 v5 v3 v6 v4 v7 9 15 12 6 4 2 3 8 5 11 16 從 v1到 v7共有 5條路徑 : v v v v7： 20 v v v v v7： 14 v v v7： 23 v v v v7： 17 v v v v7： 24 問題： 從頂點(diǎn) V1到 V7存在幾條路徑，長度為多少？ 兩種常見的最短路徑問題： 一、單源最短路徑 — 用 Dijkstra（ 迪杰斯特拉） 算法 二、所有頂點(diǎn)間的最短路徑 — 用 Floyd（ 弗洛伊德） 算法 一頂點(diǎn)到其余各頂點(diǎn) 任意兩頂點(diǎn)之間 迪杰斯特拉算法的基本思想： 依 最短路徑的長度 遞增的次序求得各條路徑。 源點(diǎn) v1 … v2 首先引入一個輔助向量 D， 它的分量 D[i]表示當(dāng)前所有找到的從始點(diǎn) V到每個終點(diǎn) Vi的最短路徑的長度。其初態(tài)為：若從 V到 Vi有弧，則 D[i]為弧上的權(quán)值，否則為無窮大；顯然，長度為 D[j]=Min{D[i]| Vi? V} 的路徑是從 V出發(fā)的最短一條路徑，此路徑為(V, Vj )。 下一條次短的路徑可通過下面的算法求得： 設(shè)次短路徑的終點(diǎn)是 Vk ， 則這條路徑或者是 (V, Vk ) ,或者是 (V, Vj, Vk ) 。 其長度或者是從 V到 Vk的弧上的權(quán)值，或者是D(j)和從 Vj到 Vk的弧上的權(quán)值之和。 例 ： 有向圖如下圖，求 V0到其它各頂點(diǎn)的最短路徑。 解： 根據(jù)上面的算法，其求解過程如下表所示。 終點(diǎn) 從 V0到各終點(diǎn)的弧值和最短路徑 V1 V2 V3 V4 V5 Vj ? ? ? ? ? 10 (V0,V2) 60 (V0,V2,V3) 50 (V0,V4,V3) 30 (V0,V4) 30 (V0,V4) 100 (V0,V5) 100 (V0,V5) 90 (V0,V4,V5) 60 (V0,V4,V3 ,V5) V2 V4 V3 V5 ０ １ ２ 3 4 5 100 10 5 50 30 10 60 20 作業(yè) 2 假設(shè)圖 G采用鄰接表存儲，設(shè)計一個算法，輸出圖 G中從頂點(diǎn) u到 v的所有簡單路徑。 設(shè)圖中各邊上的權(quán)值均相等，試以鄰接表為存儲結(jié)構(gòu)，分別寫出算法： （ 1）求頂點(diǎn) i到頂點(diǎn) j（ i≠j）的最短路徑 （ 2）求源點(diǎn) i到其余各頂點(diǎn)的最短路徑。 要求輸出路徑上的所有頂點(diǎn)（提示：利用 BFS遍歷的思想）。 圖 存儲結(jié)構(gòu) 遍 歷 鄰接矩陣 鄰 接 表 十字鏈表 鄰接多重表 深度優(yōu)先搜索 廣度優(yōu)先搜索 無向圖的應(yīng)用 應(yīng)用 圖的連通分量 圖的生成樹 最小生成樹 Prim算法 Kruskal算法 最短路徑 Dijkstra算法 Floyd算法 （利用 DFS） 第七章 小結(jié) 有向圖的應(yīng)用 DG圖 拓?fù)渑判? 關(guān)鍵路徑