野生前端的資料結構基礎練習（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 每個頂點隻出現一次

三.小結