【文章內(nèi)容簡介】 兩結點對應的單鏈表，沒有鄰接矩陣方便。 42 鄰接表與鄰接矩陣有什么異同之處 1. 聯(lián)系： 鄰接表中每個鏈表對應于鄰接矩陣中的一行，鏈表中結點個數(shù)等于一行中非零元素的個數(shù)。 2. 區(qū)別： ① 對于任一確定的無向圖，鄰接矩陣是唯一的（行列號與頂點編號一致），但鄰接表不唯一（鏈接次序與頂點編號無關）。 ② 鄰接矩陣的空間復雜度為 O(n2),而鄰接表的空間復雜度為 O(n+e)。 3. 用途： 鄰接矩陣多用于稠密圖的存儲（ e接近 n(n1)/2)； 鄰接表多用于稀疏圖的存儲（ en2) 主要內(nèi)容 圖的定義 圖的存儲表示 圖的第一個應用：拓撲排序 圖的搜索 最小生成樹 查找最短路徑 圖的第一個應用：拓撲排序 45 活動網(wǎng)絡 (Activity Network) ? 計劃、施工過程、生產(chǎn)流程、程序流程等都是“工程”。除了很小的工程外，一般都把工程分為若干個叫做“活動”的子工程。完成了這些活動，這個工程就可以完成了。 ? 例如，計算機專業(yè)學生的學習就是一個工程，每一門課程的學習就是整個工程的一些活動。其中有些課程要求先修課程，有些則不要求。這樣在有的課程之間有領先關系，有的課程可以并行地學習。 用頂點表示活動的網(wǎng)絡 (AOV網(wǎng)絡 ) 46 舉例 C1 高等數(shù)學 C2 程序設計基礎 C3 離散數(shù)學 C1, C2 C4 數(shù)據(jù)結構 C3, C2 C5 高級語言程序設計 C2 C6 編譯方法 C5, C4 C7 操作系統(tǒng) C4, C9 C8 普通物理 C1 C9 計算機原理 C8 課程代號 課程名稱 先修課程 47 建圖 學生課程學習工程圖 C8 C3 C5 C4 C9 C6 C7 C1 C2 48 AOV網(wǎng)絡 ? 用有向圖表示一個工程。在這種有向圖中，用頂點表示活動，用有向邊 Vi, Vj表示活動 Vi 必須先于活動 Vj 進行。這種有向圖叫做 頂點表示活動的 AOV網(wǎng)絡 (Activity On Vertices)。 ? 在 AOV網(wǎng)絡中不能出現(xiàn)有向回路 , 即有向環(huán)。 ? 如果出現(xiàn)了有向環(huán)，則意味著某項活動應以自己作為先決條件。 ? 對給定的 AOV網(wǎng)絡，必須先判斷它是否存在有向環(huán)。 49 拓撲排序 ? 檢測有向環(huán)的一種方法是對 AOV網(wǎng)絡構造它的拓撲有序序列。即將各個頂點 (代表各個活動 )排列成一個線性有序的序列，使得 AOV網(wǎng)絡中所有應存在的前驅和后繼關系都能得到滿足。 ? 這種構造 AOV網(wǎng)絡全部頂點的拓撲有序序列的運算就叫做拓撲排序。 ? 如果通過拓撲排序能將 AOV網(wǎng)絡的所有頂點都排入一個拓撲有序的序列中 , 則該網(wǎng)絡中必定不會出現(xiàn)有向環(huán)。 50 拓撲排序 ? 如果 AOV網(wǎng)絡中存在有向環(huán)，此 AOV網(wǎng)絡所代表的工程是不可行的。 ? 例如 , 對學生選課工程圖進行拓撲排序 , 得到的拓撲有序序列為 C1 , C2 , C3 , C4 , C5 , C6 , C8 , C9 , C7 或 C1 , C8 , C9 , C2 , C5 , C3 , C4 , C7 , C6 C8 C3 C5 C4 C9 C6 C7 C1 C2 51 拓撲排序的方法 ① 輸入 AOV網(wǎng)絡。令 n 為頂點個數(shù)。 ② 在 AOV網(wǎng)絡中選一個沒有直接前驅的頂點 , 并輸出之 。 ③ 從圖中刪去該頂點 , 同時刪去所有它發(fā)出的有向邊 。 ④ 重復以上 ②、③步 , 直到 ? 全部頂點均已輸出，拓撲有序序列形成，拓撲排序完成；或 ? 圖中還有未輸出的頂點 , 但已跳出處理循環(huán)。說明圖中還剩下一些頂點 , 它們都有直接前驅。這時網(wǎng)絡中必存在有向環(huán)。 52 C0 C1 C2 C3 C4 C5 (a) 有向無環(huán)圖 C2 C5 C1 C0 C3 (b) 輸出頂點 C4 C4 C1 C2 C5 C3 (c) 輸出頂點 C0 C0 C2 C5 C1 C3 (d) 輸出頂點 C3 拓撲排序的過程 53 C1 C2 C5 (e) 輸出頂點 C2 C5 C1 (f) 輸出頂點 C1 C5 (g) 輸出頂點 C5 最后得到的拓撲有序序列為 C4 , C0 , C3 , C2 , C1 , C5 。它滿足圖中給出的所有前驅和后繼關系，對于本來沒有這種關系的頂點，如 C4和 C2，也排出了先后次序關系。 (h) 拓撲排序完成 拓撲排序的過程 54 C0 C1 C2 C3 C4 C5 C0 C1 C2 C3 0 C4 C5 0 0 1 2 3 4 5 count data adj 1 3 0 1 0 3 1 dest link 3 0 5 1 5 0 0 1 5 0 AOV網(wǎng)絡及其鄰接表表示 55 拓撲排序算法 ? 使用一個存放入度為零的頂點的鏈式棧 , 供選擇和輸出無前驅的頂點。 ? 拓撲排序算法可描述如下： ? 建立入度為零的頂點棧 。 ? 當入度為零的頂點棧不空時 , 重復執(zhí)行 ? 從頂點棧中退出一個頂點 , 并輸出之 。 ? 從 AOV網(wǎng)絡中刪去這個頂點和它發(fā)出的邊 , 邊的終頂點入度減一 。 ? 如果邊的終頂點入度減至 0, 則該頂點進入度為零的頂點棧 。 ? 如果輸出頂點個數(shù)少于 AOV網(wǎng)絡的頂點個數(shù) , 則報告網(wǎng)絡中存在有向環(huán)。 56 拓撲排序算法 。 。 。 1直到把所有頂點從圖中移除掉。 在實現(xiàn)的細節(jié)上存在挑戰(zhàn)， 但這正是拓撲排序的關鍵所在。 57 拓撲排序算法的實現(xiàn) ? 拓撲排序需要兩個方法。 ? 一個方法用來確定頂點是否有后繼頂點 ? 另一方法則是把頂點從圖中刪除 ? 下面先來看看確定沒有后繼頂點的方法。 ? 在鄰接矩陣中可以找到?jīng)]有后繼的頂點，這種頂點所在行對應的所有列都為零。 ? 方法會用嵌套的 for循環(huán)來逐行檢查每組列的內(nèi)容。 ? 如果在某列發(fā)現(xiàn) 1，就跳出內(nèi)部循環(huán)，并對下一行進行檢查。 ? 如果找到一行對應的所有列都為零，那么返回這個行號。 ? 如果兩層循環(huán)結束且沒有行號返回，那么返回 1，這表示不存在無后繼的頂點。 58 拓撲排序算法的實現(xiàn) ? 接下來需要明白如何從圖中移除頂點。 ? 需要做的第一件事就是從頂點列表中移除掉該頂點。這是很容易的。 ? 然后，就需要從鄰接矩陣中移除掉相應的行和列，同時還要把移除行上面的行向下移動并且把移除列右側的列向左移動，以此來填充移除頂點留下的行和列的空白。 ? 為了實現(xiàn)這個操作，這里編寫了名為 delVertex的方法，它包括兩個助手方法 moveRow和 moveCol 59 拓撲排序算法的實現(xiàn) ?