[演算法] 廣度優先搜尋法(Breadth-First Search)

學習使用新的抽象資料結構，即圖形，來建立網路模型。就可以透過圖形，使用廣度優先搜尋法，來回答 A 到 B 是否存在路徑，以及 A 到 B 的最短路徑這兩種問題。

什麼是圖形？

圖形是一組連接模型，例如 A 欠 B 錢、B 欠 C 錢、D 欠 B 及 C 錢，那我們可以用以下的圖形來描述：

整個圖形由 節點(Node) 和 邊(Edge) 所組成，A、B、C、D 就是四個節點，各節點之間的連接線就是邊，故上圖有四個邊。這就是圖形。

順便瞭解什麼是有向圖(Directed Graph)、無向圖(Undirected Graph)：「向」指的是方向，如 A 欠 B 錢，以下圖表示，箭頭是由 A 指向 B，這就是有向圖：

然而，若 B 同時也欠 A 錢，那麼圖形就表達成以下兩種其中一種都可以，右邊那個就是無向圖，沒有箭頭了，表示 A 欠 B 錢、B 也欠 A 錢：

資料結構：佇列(Queue)

佇列的運作方式與真實生活中的排隊完全一樣，先排隊的人，會先上車。所以是一種先入先出(FIFO：First In First Out)的資料結構。相較堆疊，堆疊是一種後入先出(LIFO：Last In First Out)的資料結構。

佇列與堆疊(Stack)類似，不可隨意存取佇列中的元素，而是必須完成僅有的新增(Enqueue)、刪除(Dequeue)兩個操作。

實作廣度優先搜尋法(Breadth-First Search)，使用 Node.js

回顧一下此演算法是要來回答以下兩個問題：

• A 到 B 是否存在路徑？
• A 到 B 的最短路徑為何？

exports.breadth_first_search = function(custom_obj, first_key, cb){
  var search_array = custom_obj[first_key]
  while(search_array.length > 0){
    var search_item = search_array[0]
    search_array.shift()
    if( cb(search_item) ){
      return true
    }else{
      search_array = search_array.concat(custom_obj[search_item])
    }
  }
  // 回傳 false，表示不存在路徑
  return false
}