[演算法] 廣度優先搜尋法(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
}

您可在此處留言

搶先留言!

avatar
  Subscribe  
Notify of