目錄

1. 隊列的基本概念

2. 廣度優先搜索（BFS）的基本概念

3. 隊列在BFS中的作用

4. BFS的實現細節

5. C++實現BFS

6. BFS的應用場景

7. 復雜度分析

8. 總結

---

1. 隊列的基本概念

隊列（Queue）是一種先進先出（FIFO, First In First Out）的線性數據結構。它有兩個主要操作：

• 入隊（Enqueue）：將元素添加到隊列的末尾。

• 出隊（Dequeue）：移除隊列的第一個元素。

在C++中，隊列可以通過STL中的std::queue來實現：

#include <queue>std::queue<int> q;
q.push(1);  // 入隊
q.pop();    // 出隊
int front = q.front();  // 獲取隊首元素

2. 廣度優先搜索（BFS）的基本概念

廣度優先搜索（BFS, Breadth-First Search）是一種用于遍歷或搜索樹或圖的算法。BFS從根節點（或任意節點）開始，逐層遍歷所有相鄰節點，直到找到目標節點或遍歷完所有節點。

BFS的核心思想是使用隊列來存儲待訪問的節點。具體步驟如下：

1. 將起始節點放入隊列。

2. 從隊列中取出一個節點，訪問它。

3. 將該節點的所有未訪問過的相鄰節點放入隊列。

4. 重復步驟2和3，直到隊列為空。

3. 隊列在BFS中的作用

隊列在BFS中起到了關鍵作用，它保證了節點按照層次順序被訪問。具體來說：

• 層次遍歷：隊列確保每一層的節點都在下一層節點之前被訪問。

• 避免重復訪問：通過標記已訪問的節點，可以避免重復訪問和無限循環。

4. BFS的實現細節

在實現BFS時，需要注意以下幾個關鍵點：

• 訪問標記：通常使用一個數組或哈希表來記錄哪些節點已經被訪問過。

• 隊列操作：每次從隊列中取出一個節點，訪問它，并將其未訪問的相鄰節點加入隊列。

• 終止條件：當隊列為空時，BFS結束。

5. C++實現BFS

下面是一個使用隊列實現BFS的C++代碼示例，假設我們有一個無向圖，用鄰接表表示：

#include <iostream>
#include <queue>
#include <vector>void BFS(int start, const std::vector<std::vector<int>>& graph) {std::vector<bool> visited(graph.size(), false);std::queue<int> q;q.push(start);visited[start] = true;while (!q.empty()) {int node = q.front();q.pop();std::cout << "Visited node: " << node << std::endl;for (int neighbor : graph[node]) {if (!visited[neighbor]) {q.push(neighbor);visited[neighbor] = true;}}}
}int main() {// 示例圖的鄰接表表示std::vector<std::vector<int>> graph = {{1, 2},    // 節點0的鄰居{0, 3, 4}, // 節點1的鄰居{0, 5},   // 節點2的鄰居{1},      // 節點3的鄰居{1},      // 節點4的鄰居{2}       // 節點5的鄰居};BFS(0, graph);  // 從節點0開始BFSreturn 0;
}

6. BFS的應用場景

BFS廣泛應用于各種場景，包括但不限于：

• 最短路徑問題：在無權圖中，BFS可以找到從起點到目標節點的最短路徑。

• 連通性檢測：BFS可以用于檢測圖中的連通分量。

• 狀態空間搜索：在解決某些問題時，BFS可以用于搜索狀態空間，如八數碼問題、迷宮問題等。

7. 復雜度分析

• 時間復雜度：BFS的時間復雜度為O(V + E)，其中V是頂點數，E是邊數。每個節點和每條邊都會被訪問一次。

• 空間復雜度：BFS的空間復雜度主要取決于隊列的大小，最壞情況下為O(V)。

8. 總結

????????“隊列+寬搜”是一種經典的算法思想，通過隊列的先進先出特性，BFS能夠有效地遍歷圖或樹結構，并解決許多實際問題。理解隊列在BFS中的作用以及如何正確實現BFS是掌握這一算法思想的關鍵。通過C++的實現，我們可以清晰地看到隊列如何幫助BFS逐層遍歷節點，并確保每個節點只被訪問一次。