深度優先搜尋(Depth-First Search,DFS)與廣度優先搜尋(Breadth-First Search, BFS)是兩種特別常用的演算法，DFS演算法其實就是回溯演算法，在前幾個章節有提及．

今天我們會開始注重於BFS演算法的範本，其核心概念就是

將一些問題抽象成圖，從圖的某一個點開始，往四周擴散．

最常見的寫法都是利用佇列的資料結構，一次將一個節點周圍的所有節點都加入佇列之中．

BFS相對於DFS的主要差別就在，雖然BFS找到的一定是最的路徑，相對來說，所需要的空間複雜度會比DFS大上很多．

BFS框架

最常利用到BFS演算法的情景主要會是這樣:

在一個圖中，找到從起點start到終點target的最短距離．

讓我們為這個情境加上點肉:有一個迷宮，有些地方是牆壁不能行走，從起點到終點最短的距離是多少，如果這迷宮走到邊緣會傳送到另外一邊呢？

或者連連看遊戲，消除兩個方塊不只需要圖案相同，還要兩個方塊之間的連線，不能轉彎超過兩次以上．當點擊兩個方塊的時候，遊戲程式設計師是怎麼找到最短連線，並且畫在畫面上呢？

大概的結構如下

fun BFS(start:Node,target:Node):Int{
    val queue: Queue<Node>  = LinkedList()//核心的資料
    val visited:MutableSet<Node> = mutableSetOf()//記錄已經走過的節點 避免重複
    queue.offer(start)//把起點加入佇列
    visited.add(start)

    var step:Int = 0//紀錄擴散的步數
    while(queue.isNotEmpty()){
        val size = queue.size
        
        for(i in 0..size){//將目前佇列中所有節點往外擴散
            val currentNode = queue.poll()
            if(currentNode == target){//到達終點 返回答案
                return step
            }
            currentNode.arrond().forEach{//把currentNode附近的節點都加入佇列
                if(!visited.contains(it)){
                    queue.offer(it)
                    visited.add(it)
                }
            }
        }
        step++
    }
    
}

這樣有點難理解，我們用一個簡單的例子來實際演練一次:”求一個二元樹的最小高度”