BFS全名Breadth-first search中文叫「廣度優先搜尋」，我個人覺得比DFS還要好理解很多，也因為他是「廣度」優先的原因，感覺就像「擴散」開來的感覺，以下我們就用Tree來感受一下BFS跟DFS的差別吧！

實作BFS

在實作BFS的時候我們會使用Queue，還記的DFS因為是用Stack來實作的關係我們可以使用迴圈的Call Stack或是一般的Stack，但是Queue就只能直接在程式碼裡面撰寫沒有那種類似Call Stack的東西可以用囉。

以樹來說，一開始會把root加進我們的Queue，然後從Queue裡面Pop出來，再分別把左右節點放進Queue裡面，然後我們再把Queue裡剛加進的左右節點Pop出來，把他們相對應的子節點再加入Queue中，一直持續以上的動作一直到我們Queue為空，這樣就完成我們的BFS囉！

BFS使用時機

上一篇我們說到DFS時有說到，很多情況下DFS跟BFS都可以處理，但BFS更擅長於處理每一「層」的這種問題，也因為我們要存的是層的資料所以記憶體有時候會用的多一點，想想看在Tree的結構裡面，DFS最多只會需要樹的高度的記憶體空間，但是BFS會需要整層節點數的空間，節點數是會比樹高度還要多的。

這邊我認為一樣大家先有這個概念比較重要，之後遇到的問題越來越多後就能夠更知道到底應該使用DFS還是BFS了。

如何知道我在BFS的第幾層？

這個問題是我當初在練習BFS遇到的問題，聽起來很白癡，但是如果能幫助到讀者那我覺得也相當有意義。
如果我們看剛剛講的最基本BFS的流程會發現，如果今天我希望是印出這個節點的值跟他在第幾階，我是沒辦法知道他在第幾階的，因為我們就是不斷pop然後append，我們無從得知這個節點是在第幾階。
那解決辦法其實很簡單，就是我可以用for迴圈去決定我在「這一層」要Pop多少次，那個多少次可以用len(queue)來去獲取。這邊提供給各位圖片跟程式碼做參考囉。

        queue = deque()
        layer = 0
        if root:
            queue.append(root)
        while queue:
            level_res = []
            for _ in range(len(queue)):
                node = queue.popleft()
                print(node.val, layer)
                if node.left: queue.append(node.left)
                if node.right: queue.append(node.right)
            layer += 1

BFS當然也不只可以用在Tree，也可以用在圖，這邊我們就來看一下BFS搜圖的效果吧。