野生前端的數據結構基礎練習（8）——圖

網上的相關教程非常多，基礎知識自行搜索即可。

習題主要選自Orelly出版的《數據結構與演算法javascript描述》一書。

參考代碼可見:https://github.com/dashnowords/blogs/tree/master/Structure/graph

一.圖的基本知識

基本概念

圖是由邊的集合和點的集合組成的。如果圖的邊有方向（或者說圖中的頂點對是有序的）則成為有向圖，如果邊沒有方向則稱為無向圖。

基本建模

圖可以用來對現實中許多事物進行建模。比如交通流量，電腦網路等。

二.基本練習

1. 構建一個圖的類Graph

2. 圖的深度優先搜索（DFS）

   深度優先搜索從起始頂點開始，直到到達最後一個頂點，然後回溯，直到遍歷完隨後頂點或查找到指定頂點。深度優先是應用非常廣泛的基本搜索思想，往往藉助棧結構來實現。demo中的dfs.js直接使用函數的調用棧來追蹤搜索，如果數據量很大，則可以通過手動用一個數組來管理棧。

3. 圖的廣度優先搜索（BFS）

   廣度優先搜索從第一個頂點開始，嘗試訪問儘可能靠近它的頂點，搜索範圍基本是逐層移動的。它的實現依靠數據結構中的隊列來實現。

4. BFS查找最短路徑

   圖最常見的操作之一就是尋找從一個頂點到另一個頂點的最短路徑。書中示例中通過this.edgeTo這個數組來存儲頂點的訪問路徑，例如w節點是通過訪問v節點的臨近節點時訪問的，那麼就執行如下賦值this.edgeTo[w] = v，並將節點標記為已訪問，由於廣度優先搜索逐層擴展的特性，最終通過this.edgeTo迭代顯示出的路徑必然是搜索中最先實現標記的路徑，也就是最短的路徑，所以並不需要將每次訪問都記錄下來最終再比較步長。

5. 拓撲排序

   拓撲排序用於輸出一個有向無環圖所有頂點的線性序列，使之滿足：

   a 每個頂點只出現一次

   b 若存在一條從頂點A到B的路徑，那麼序列中A一定出現在B前面。

   書中給出的示例在輸出時描述有誤，導致輸出結果與真實的排序是相反的，在拓撲排序時採用了棧結構，入棧順序是反的，正確的輸出順序是按照出棧順序來輸出。

三.小結

圖論是非常複雜的領域，對數學基礎要求較高，感興趣的讀者可以自行繼續研究。至此，基本數據結構的課就補完了，希望你也認真做了練習，完成了這個基本的掃盲過程。