8.1 BFS 原理
廣度優先搜尋 (Breadth-First Search, BFS) 是一種圖形遍歷或搜尋演算法，從起始節點開始，並在進入下一層之前探索當前層的所有相鄰節點。
演算法步驟：
- 從選定的起始節點開始，並將其放入隊列。
- 當隊列不為空時，執行以下操作：
- 從隊列的頭取出節點並標記為已訪問。
- 對於每個未訪問的相鄰節點，將其添加到隊列中。
- 重複步驟 2，直到訪問完從起始節點可以達到的所有節點。
視覺化：
時間複雜度：
O(V + E)，其中 V 是節點數，E 是邊的數量。
每個節點和每條邊都會被訪問一次。
空間複雜度：
O(V)，因為使用隊列來存儲節點，還有一個用來存儲狀態（已訪問節點）的數組。
8.2 使用隊列實現 BFS
廣度優先搜尋可以很好的用隊列這種資料結構來實現。
使用隊列實現 BFS：
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
while queue:
vertex = queue.popleft()
if vertex not in visited:
visited.add(vertex)
print(vertex) # 處理節點
for neighbor in graph[vertex]:
if neighbor not in visited:
queue.append(neighbor)
# 使用範例：
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B'],
'F': ['C']
}
bfs(graph, 'A')
8.3 雙向廣度優先搜尋
BFS 常用於遊戲中，當需要在複雜的地形中找到兩點間的最短路徑時。這樣的問題可以轉化為圖中兩個節點之間的路徑搜尋。這樣的圖的邊就是地圖上所有可通行的路徑。
但是為了更快地找到路徑，通常從兩端開始搜尋。這就是為什麼使用雙向 BFS。
工作原理
雙向廣度優先搜尋 (Bidirectional BFS) 是 BFS 的優化版本，該算法從起始節點和目標節點同時進行兩次平行的圖形遍歷。遍歷繼續，直到兩個遍歷相遇，這大大減少了與經典 BFS 相比檢查的節點和邊的數量。
演算法步驟：
- 初始化兩個隊列：一個從起始節點開始的遍歷，另一個從目標節點開始。
- 初始化兩個已訪問節點集來跟踪從兩個方向訪問的節點。
- 從兩個隊列中進行交替的圖遍歷。
- 每一步檢查訪問節點集是否相交。如果找到了交集，則路徑存在。
- 該過程持續進行，直到找到交叉節點或隊列為空。
時間複雜度
在最佳情況下：O(2 * (V + E)) = O(V + E)，其中 V 是節點數，E 是邊的數量。
雙向 BFS 一般遍歷的節點數較單向 BFS 少，特別是在大圖中。
空間複雜度：
O(V) 用於存儲兩個隊列和兩個已訪問節點集。
雙向 BFS 的例子
例子非常長，該算法比單向搜尋長三倍左右，所以我就不舉例了。當你真的需要它時，你會能夠自己寫出來。
8.4 使用 BFS 解決的問題示例
使用 BFS 解決的經典問題示例：
1. 在無向圖中搜尋最短路徑：
BFS 用於在無向圖中從起始節點到目標節點的最短路徑（最小邊數）搜尋。
應用：
- 導航系統中用於搜尋點與點之間的最短路徑。
- 網絡分析中用於搜尋數據傳輸的最短路徑。
2. 圖的連通性檢查：
檢查圖是否連通，即是否存在任意兩個節點之間的路徑。
應用：
- 網絡分析中用於檢查網絡的連通性。
- 社交網絡分析中用於檢查用戶群體的連通性。
3. 迷宮生成：
使用 BFS 生成具有特定屬性隨機迷宮。
應用：
- 遊戲應用中用於迷宮創建。
- 機器人技術中用於導航算法的測試。
4. 樹中的廣度優先搜尋：
BFS 用於遍歷樹，以便在樹的每層執行操作（例如，打印每層的所有節點）。
應用：
- 數據可視化問題中，要求按層次顯示數據。
- 排程問題中，要求在每層次執行操作。
5. 圖的二分性檢查：
檢查圖是否為二分圖，即能否將節點分為兩個集合，使邊僅存在於不同集合的節點之間。
應用：
- 圖論中的圖的二分性檢查。
- 圖的著色問題中，需要檢查能否用兩種顏色給圖著色。
GO TO FULL VERSION