BFS的基本概念

BFS 是廣度優先搜索（Breadth-First Search）的縮寫，是一種圖遍歷算法。它從給定的起始節點開始，逐層遍歷圖中的節點，直到遍歷到目標節點或者遍歷完所有可達節點。

BFS 算法的核心思想是先訪問當前節點的所有鄰居節點，然后再訪問鄰居節點的鄰居節點，依此類推，直到遍歷完整個圖。

BFS 模版

BFS 使用隊列（Queue）數據結構來輔助實現，它按照先進先出（FIFO）的順序管理待訪問的節點。用**集合（Set）**來輔助節點是否已經被訪問，算法的基本流程如下：

• 將起始節點放入隊列中，并標記為已訪問。
• 從隊列中取出一個節點，訪問該節點,判斷該節點是否符合條件。
• 將該節點的所有未訪問過的鄰居節點加入隊列，并標記為已訪問。
• 重復步驟 2 和步驟 3，直到隊列為空。

模版1：不必記錄深度

function BFS(start, target) {const queue = []; // 核心數據結構const visited = new Set(); // 避免走回頭路// 將起始節點放入隊列中，并標記為已訪問。queue.push(start); visited.add(start);while (queue.length > 0) {const sz = queue.length;const cur = queue.shift();/* 劃重點：這里判斷是否到達終點 */if (cur === target)return step;/* 將 cur 的所有未訪問過的鄰居節點加入隊列，并標記為已訪問。 */for (const x of cur.adj()) {if (!visited.has(x)) {queue.push(x);visited.add(x);}}}
}

模版2：需要記錄深度的

function BFS(start, target) {const queue = []; // 核心數據結構const visited = new Set(); // 避免走回頭路// 將起始節點放入隊列中，并標記為已訪問。queue.push(start); visited.add(start);let step = 0; // 記錄擴散的步數while (queue.length > 0) {const sz = queue.length;/* 將當前隊列中的所有節點向四周擴散 */for (let i = 0; i < sz; i++) {const cur = queue.shift();/* 劃重點：這里判斷是否到達終點 */if (cur === target)return step;/* 將 cur 的所有未訪問過的鄰居節點加入隊列，并標記為已訪問。 */for (const x of cur.adj()) {if (!visited.has(x)) {queue.push(x);visited.add(x);}}}/* 劃重點：更新步數在這里 */step++;}
}

BFS 算法通常用于以下場景：

• 尋找兩個節點之間的最短路徑。
• 在樹或圖中尋找特定深度或層級的節點。
• 檢查圖是否是連通的。
• 拓撲排序。
• 解決迷宮問題等。

例題

111 二叉樹的最小深度

給定一個二叉樹，找出其最小深度。

最小深度是從根節點到最近葉子節點的最短路徑上的節點數量。

說明：葉子節點是指沒有子節點的節點。

var minDepth = function(root) {if(root === null){return 0;}// 記錄深度let step = 0;// BFS關鍵數據結構let queue = [];let visited = new Set();queue.push(root);visited.add(root);while(queue.length > 0){let size = queue.length;for(let i = 0;i<size;i++){/* 劃重點：這里判斷是否到達終點 */let node = queue.shift();if(node.left === null && node.right === null){return step+1;}/* 將 cur 的所有未訪問過的鄰居節點加入隊列，并標記為已訪問。 */if(node.left !== null && !visited.has(node.left)){queue.push(node.left);visited.add(node.left);}if(node.right !== null && !visited.has(node.right)){queue.push(node.right);visited.add(node.right);}}step++;}return step;
};

863.二叉樹中所有距離為 K 的結點

給定一個二叉樹（具有根結點 root）， 一個目標結點 target ，和一個整數值 k 。

返回到目標結點 target 距離為 k 的所有結點的值的列表。 答案可以以 任何順序 返回。

思路：
需要我們在樹中尋找特定深度或層級的節點，但是又不是從根節點開始，因此需要我們將樹 轉化成 圖。
可以通過哈希表和DFS將樹轉化成圖

var distanceK = function(root, target, k) {// 起點是target，先通過哈希表+DFS將樹轉化成圖const parents = getParents(root);// 結果數組let ans = []// BFS關鍵數據結構let queue = []const visited = new Set()queue.push(target);visited.add(target.val);// 記錄深度let step = 0;while(queue.length){// 遍歷每一層的節點const len = queue.length;for(let i = 0;i<len;i++){// 判斷當前節點是否符合條件。const node = queue.shift();if(step === k){ans.push(node.val);}// 將相鄰的節點都放入到if(node.left && !visited.has(node.left.val)){queue.push(node.left);visited.add(node.left.val);}if(node.right && !visited.has(node.right.val)){queue.push(node.right);visited.add(node.right.val);}if(parents.has(node.val) && !visited.has(parents.get(node.val).val)){queue.push(parents.get(node.val));visited.add(parents.get(node.val).val);}}// 遍歷完一層后深度+1step++;}return ans;};function getParents(root) {const parents = new Map();const findParents = (root) => {if (root.left) {parents.set(root.left.val, root);findParents(root.left);}if (root.right) {parents.set(root.right.val, root);findParents(root.right);}};findParents(root);return parents;
}