---
# System prepended metadata

title: 廣度優先搜尋（Breadth-First Search，BFS）

---

從圖的某個節點，沿著邊遍歷所有尚未接觸的節點，直到找到目標，或者尋遍所有節點為止。

這種演算法能解決兩種問題
1. 節點A與B之間是否有路徑存在
2. 節點A到B的最短路徑為何

![](https://hackmd.io/_uploads/S1rlRmnFn.png)

但因為不同節點其實有『等』的差別，所以最好方式是從最近的關係開始往外擴張。

EX: 
A: [B, C, D]
D: [H, G]
H: [K, L]

---
所以要搭配queue的方式，去處理哪些應該要先搜尋

![](https://hackmd.io/_uploads/Hk2H1V2Kn.png)

```ruby=
def person_is_seller?(name)
  name[-1] == "m"
end

class Graph < Hash
  def search(name)
    search_queue = []
    search_queue += self[name]
    # The "searched" Hash is how you keep track of which people you've searched before. We use a hash because hash lookups are fast!
    searched = {}

    until search_queue.empty?
      person = search_queue.shift
      # Only search this person if you haven't already searched them.
      next if searched[person]
      return person if yield person
      search_queue += self[person]
      # Marks this person as searched
      searched[person] = true
    end

    false
  end
end


# %w(string1 string2 ...) is a shorter way to define arrays of strings
graph = Graph.new
graph["you"] = %w(alice bob claire)
graph["bob"] = %w(anuj peggy)
graph["alice"] = %w(peggy)
graph["claire"] = %w(thom jonny)
graph["anuj"] = []
graph["peggy"] = []
graph["thom"] = []
graph["jonny"] = []

# we begin the search from vertex "you" and pass the match criterion in the block, then we tap the search result
graph.search("you"){|person| person_is_seller?(person)}.tap{|person| puts "#{person} is a mango seller!" if person}
```