演算法 in Golang：Breadth-first search

（BFS、廣度優先搜索）

最短路徑問題 Shortest-path problem

• 從 A 到 F 點有多條路徑

解決問題的演算法 Breadth-first Search（廣度優先搜索）

1. 將問題建模為圖（Graph）
2. 通過 Breadth-first Search 演算法來解決問題

圖（Graph）是什麼？

圖是用來對不同事物間如何關聯進行建模的一種方式

圖是一種數據結構

Breadth-first Search（BFS）廣度優先搜索演算法

1. 作用於圖（Graph）
2. 能夠回答兩類問題：
   1. 是否能夠從節點 A 到節點 B？
   2. 從 A 到 B 的最短路徑是什麼？

以社交網路為例

• 直接添加的朋友
  • 朋友的朋友...
  • 第一層沒找到再找第二層

數據結構 Queue

• 先進來的數據先處理（FIFO）先進先出原則
• 無法隨機的訪問 Queue 裡面的元素
• 相關操作：
  • enqueue：添加元素
  • dequeue：移除元素

例子

找到名為 Tom 的朋友

1. 把你所有的朋友都加到 Queue 裡面
2. 把 Queue 裡面第一個人找出來
3. 看他是不是 Tom
   1. 是 結束任務
   2. 否 把他所有的朋友加到 Queue 重覆操作

創建項目

~/Code/go via