Zi 字媒體

此篇文章瀏覽量： 1,006 學習使用新的抽象資料結構，即圖形，來建立網路模型。就可以透過圖形，使用廣度優先搜尋法，來回答 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 } 若覺得文章有幫助，請多分享，讓其他同好也能吸收網站技能知識。 Facebook Twitter