一、認識廣度優先搜索算法

廣度優先搜索(BFS)算法是圖的一種遍歷方法，它的核心思想是從圖的某一個節點開始，依次遍歷相鄰節點，再從這些相鄰節點繼續向外層節點遍歷，直到連通圖的所有節點均被訪問到。

如上圖所示，A、B、C、D、E、F六個節點構成了連通圖。我們使用廣度優先搜索算法對該連通圖進行遍歷，從A點出發，找到A點的相鄰節點B點和F點，再分別找到B點和F點的相鄰節點C點和E點，最終找到C點和E點的共同相鄰節點D點。因此我們得到的遍歷結果為ABFCED。

二、Leetcode常見廣度優先搜索形式

當我們打開Leetcode的廣度優先搜索標簽，查看相關算法題時會發現，很多題是將連通圖簡化為樹或二叉樹的形式展示。因此我們可以從樹/二叉樹的角度分析廣度優先搜索算法，只要搞懂了樹的廣度優先搜索，圖的廣度優先搜索只是相鄰節點的選擇差異罷了。
廣度優先搜索算法在樹/二叉樹中被簡化為層次遍歷算法，即從樹的根節點出發，依次遍歷根節點的孩子，再分別將這些孩子作為根節點，循環上述操作，直至將所有的節點全部遍歷結束。
如下圖所示，樹的層次遍歷就是一種特殊的廣度優先搜索。根據上文的遍歷規則不難得出樹的廣度優先搜索序列為ABCDEFG。

三、一道算法題講解具體的BFS實現思路

我選取了Leetcode上一道典型的廣度優先搜索算法給大家整理一下BFS的算法基本實現思路，題目如下：

思路: 從題意中我們不難看出，該題的核心問題就是求出二叉樹的每一層中最右邊的節點的值并將其存入數組最后返回該數組。很顯然，利用廣度優先搜索算法可以很容易將每一層的最右節點求出。
對于廣度優先搜索算法，我們需要申請一個輔助隊列幫助我們存儲每一層的每一個節點。首先需要對根節點判空，若根節點為空則直接返回一個空數組，否則將根節點存入隊列中。接下來我們需要將隊列中該層的所有節點取出，并找出它們的孩子節點存入隊列中。需要注意的是，到了最右節點時應將該節點的值存入數組。循環該過程直至遍歷二叉樹的所有節點即可得出最終的結果。

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int count = queue.size();
            TreeNode currentNode = null;
            while (count > 0) {
                count--;
                currentNode = queue.poll();
                if (currentNode.left != null) {
                    queue.add(currentNode.left);
                }
                if (currentNode.right != null) {
                    queue.add(currentNode.right);
                }
            }
            ans.add(currentNode.val);
        }
        return ans;
    }
}

算法復雜度分析：算法需要訪問該二叉樹中的每個節點并且每個節點的訪問時間為O(1)，所以最終的事件復雜度為O(n)。對于空間復雜度，我們申請了一個輔助隊列幫助存儲二叉樹節點，最終的空間復雜度也可表示為O(n)。