《數(shù)據(jù)結(jié)構(gòu)與算法之美》，王爭 著

標(biāo)簽：數(shù)據(jù)結(jié)構(gòu)、算法

第9章 圖

一、圖的表示

這一部分介紹了

• 圖的定義

• 鄰接矩陣的存儲方法

• 鄰接表的存儲方法

• 如何用圖存儲微博、微信等社交網(wǎng)絡(luò)中的好友關(guān)系

筆記：鄰接表（鄰接表+逆鄰接表）存儲結(jié)構(gòu)適合存儲大規(guī)模的滿足網(wǎng)狀結(jié)構(gòu)特征的數(shù)據(jù)集；將鄰接表中的鏈表改為其他支持快速查找的數(shù)據(jù)結(jié)構(gòu)，如平衡二叉樹、跳表和哈希表等，即優(yōu)化了存儲空間，又保證了查詢效率高。

?

二、深度優(yōu)先搜索和廣度優(yōu)先搜索

這一部分介紹了

• 什么是搜索算法

• 廣度優(yōu)先搜索

• 深度優(yōu)先搜索

• 如何用廣度優(yōu)先搜索找出社交網(wǎng)絡(luò)中的三度好友關(guān)系

筆記：深度優(yōu)先搜索和廣度優(yōu)先搜索是數(shù)據(jù)結(jié)構(gòu)和算法課程和教材中，圖部分的必學(xué)知識點(diǎn)，原因無他，就是太常用，太基本的圖搜索算法。

?

三、拓?fù)渑判?/p>

這一部分介紹了

• 什么是拓?fù)渑判?/p>

• 利用Kahn算法實現(xiàn)拓?fù)渑判?/p>

• 利用深度優(yōu)先搜索實現(xiàn)拓?fù)渑判?/p>

• 利用拓?fù)渑判驒z測環(huán)

• 如何利用拓?fù)渑判虼_定代碼源文件的編譯依賴關(guān)系

筆記：圖的拓?fù)渑判蛞彩且环N常用和基本的圖算法，教材中的兩種實現(xiàn)算法也是算法設(shè)計的經(jīng)典案例。

?

四、單源最短路徑

這一部分介紹了

• 最短路徑算法介紹

• Dijkstra算法的原理與實現(xiàn)

• Dijkstra算法的性能分析

• Dijkstra算法思想的應(yīng)用（作者介紹了一個翻譯系統(tǒng)的實現(xiàn)）

• 單源最短路徑的應(yīng)用：地圖軟件如何計算最優(yōu)出行路線

?五、多源最短路徑

這一部分介紹了

• Floyd的原理與實現(xiàn)

• Floyd算法的性能分析

• 如何用Floyd算法解決傳遞閉包問題

?六、啟發(fā)式搜索

這一部分介紹了

• 什么是次優(yōu)路線

• A*算法的原理與實現(xiàn)

• A*算法與Dijkstra算法的對比

• 如何用A*算法實現(xiàn)游戲中的尋路功能

?筆記：圖的路徑搜索問題是經(jīng)典問題，教材中必講，考試必考，科研和實際工程項目中應(yīng)用廣泛。教材中的內(nèi)容都是基本的原理，掌握這些原理，為科研和實際工程項目中的實際應(yīng)用打下良好的基礎(chǔ)。

?

七、最小生成樹

這一部分介紹了

• 什么是最小生成樹

• Kruskal算法的原理與實現(xiàn)

• Prim算法的原理與實現(xiàn)

• 如何隨機(jī)生成游戲中的迷宮地圖

?八、最大流

這一部分介紹了

• 什么是最大流

• Ford-Fulkerson方法

• Edmonds-Karp算法

• 最大流的一個非常經(jīng)典應(yīng)用：最大二分匹配

• 如何解決單身交友聯(lián)誼中的最多匹配問題

?

本章筆記：圖及其相關(guān)算法是數(shù)據(jù)結(jié)構(gòu)和算法教材中必有，必考部分，圖是一種比較復(fù)雜（或稱為高級）的數(shù)據(jù)結(jié)構(gòu)，圖的相關(guān)算法也比較復(fù)雜，但是圖的經(jīng)典算法，應(yīng)用廣泛，不得不學(xué)；而且經(jīng)典圖算法的算法設(shè)計思路或方法也是算法設(shè)計方法的經(jīng)典案例。