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