初識廣度優先搜尋與解題套路 | 算法必看知識十八

原文連結

初識廣度優先搜尋

在講解廣度優先搜尋之前，我們來看看幾個常見的資料結構，連結清單、樹、圖。

先來看看其中比較簡單的資料結構 – 連結清單，它和數組類似，也是一個線性的結構，簡單來說就是一條路徑，你從頭開始周遊，最終會将連結清單上面的節點都通路到，到達終點。

相比數組來說，連結清單在記憶體中的存儲可以不是一段連續的區域。

連結清單節點中會有一個變量用來指明其下一個節點，将連結清單的表示用代碼寫出來，就會是下面這樣：

class ListNode {
    int val;
    ListNode next;
}           

其中 val 表示的是這個節點上面值，next 表示的是這個節點的下一個節點。

講完連結清單，我們來看看另外一個資料結構 – 二叉樹，它其實是連結清單的一個延伸，這裡，一個節點的下一個節點不再隻有一個節點了，可能會有兩個節點，如果把樹的結構用代碼表示出來，就會是：

class TreeNode {
   int val;
   TreeNode left, right;
}           

你可能會問，多叉樹如何表示呢？這個也簡單，一個樹節點會有多個子節點：

class TreeNode {
    int val;
    List<TreeNode> children;
}           

不管是兩個節點還是多個節點，樹當中是有層級關系的， 就是 parent 和 children 的關系。

對于一般的樹結構來說，一個節點内隻會儲存其 children 的資訊，不會儲存其 parent 的資訊，給你一個樹節點，你隻會往其 children 的方向走， 也就是說，樹的周遊其實是有方向性的。

最後我們來看看圖，圖的話分為有向圖和無向圖，樹其實是算有向圖當中的一種，有向無向，主要是看邊，如果兩個節點連在一起，它們之間是互通的話就是無向圖，如果隻能從一個節點到另一個節點，反之可能不行，那就是有向圖，不管是有向圖還是無向圖，在代碼中，我們都可以表示下面這樣：

class GraphNode {
    int val;
    List<Integer> neighbors;
}
           

這不就是前面多叉樹的表示方法嗎？沒錯，但是圖中的關系不再是 parent 和 children 的關系了，而是鄰居的關系，這裡也沒有層級結構了，每個節點都是平等的。

講完了這幾個資料結構，我們再回過頭來看看廣度優先搜尋這個算法，這個算法經常被用在樹上和圖上，我們來思考一下這個問題，如果給你一個連通圖上的一個節點，如何才能得到圖上所有的節點呢？

這個思路其實很簡單。

首先我們知道，我們可以把給定節點和其鄰居加入到答案中，但是鄰居還有鄰居，是以我們還是得繼續這個過程，直到把所有的點都找到，這之中我們可能會遇到一種情況就是，我們通路到了之前找到過的點，是以，這裡我們還需要一個判重的機制。

這裡有一點是，每個點隻可能找到其鄰居，也就是說隻會往其周圍的點找，一次隻向外擴散一格，解決廣度優先搜尋問題，我們會使用隊列這麼一個 FIFO 的資料結構， 這不難了解，先找到的點我們先考慮其鄰居。

問題分類

上面我們簡單介紹了一下廣度優先搜尋這個算法，那麼它可以用來解決什麼樣的問題呢？

• 層級周遊
• 由點到面周遊圖
• 拓撲排序
• 求最短路徑

我們一個一個來講解，首先是層級周遊，前面講過，每個節點隻會找到其周圍的節點，你可以想象成目前層的節點隻可能找到下一層的節點（前一層周遊過不考慮），是以我們可以把一層找到的東西放在一起，這也就是用層這個概念對找到的所有節點進行歸類。

第二點是周遊圖，其實就是上面中的例子“給定連通圖上面的一個節點，需要找到這個圖中的所有節點”，你可能會問，周遊整個圖有什麼用呢？如果我們知道來所有節點的數量，其實通過周遊整個圖我們還可以判斷一個圖的連通性，如果從一個點出發找不到某些點，那麼說明其實這不是一個連通的圖，有些節點不在圖上，被分開了。

第三點是拓撲排序，這裡可以參考我之前寫的一篇文章

拓撲排序原理和習題分析

。

第四點，也是比較常用的就是找出圖上兩點的最短路徑，當然這裡是有條件的，就是這個圖必須是簡單的連通圖，什麼是簡單圖，就是邊沒有權重，或者說權重都為固定的值。從一個點出發，找到下一層的所有點，從下一層的點出發，找到下下層的所有點，每到一層就算走一步，當我們找到我們要找的點，此時的步數就是最後的答案。

對于廣度優先搜尋的時間和空間複雜度的分析也是比較簡單，一般問題都需要周遊整個圖，是以時間複雜度是 O(N + M)，空間複雜度是 O(N)，這裡的 N 表示的是節點的總數量，M 表示的是邊的數量，有些圖中，比如說全連通圖(M = N^2)，我們周遊的時候，會嘗試去走所有的邊，對于空間來說的話，一般隻會記錄通路過的節點和目前層的節點，不會去考慮邊的情況，是以時間複雜度和空間複雜度在這裡還是不太一樣的。

廣度優先搜尋就說到這裡，這裡我沒有列出很多的題目，了解算法本身，及其适合解決的問題是關鍵，廣度優先搜尋主要适合解決層級周遊、由點及面周遊圖、拓撲排序以及在求在簡單圖上兩點之間的最短距離，了解了這些原理性的東西後，再去刷一些題目去鞏固這些知識點，最後才能對這個算法了然于心。

作者 | P.yh

來源 | 五分鐘學算法