廣度優先搜尋（BFS）是一種根據佇列的圖形遍歷演算法，它從起始節點開始，逐層探索其鄰居節點，直到遍歷完所有可達節點。BFS 的核心思想是利用佇列來維護待存取的節點，並使用集合記錄已存取的節點，避免重複存取。這種逐層探索的特性使得 BFS 非常適合用於尋找圖中的最短路徑，特別是在無權圖或權重相同的圖中。在程式碼實作上，通常使用 collections 模組中的 deque 作為佇列，以提高效率。BFS 的時間複雜度為 O(V+E)，其中 V 是節點數，E 是邊數；空間複雜度為 O(V)，主要用於儲存佇列和已存取節點的集合。由於 BFS 需要儲存每一層的節點，因此在處理大規模圖形時，記憶體消耗可能會成為一個瓶頸。
廣度優先搜尋（BFS）演算法分析與應用
廣度優先搜尋（BFS）是一種重要的圖形遍歷演算法，廣泛應用於多個領域，如社交網路分析、網路爬蟲、電腦網路、人工智慧和生物資訊學等。本文將深入分析BFS的原理、應用、時間複雜度、空間複雜度以及最佳化技術。
BFS的基本原理
BFS從一個起始節點開始，逐層遍歷圖中的所有節點。它使用一個佇列來儲存待存取的節點，並使用一個集合來記錄已存取的節點，以避免重複存取。
程式碼範例：
from collections import deque
def bfs(graph, start):
visited = set() # O(V) 空間
queue = deque([start]) # 最壞情況下 O(V) 空間
visited.add(start)
while queue:
vertex = queue.popleft()
print(vertex, end=' ')
for neighbor in graph[vertex]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
# 範例用法
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
bfs(graph, 'A')
內容解密：
- 初始化一個佇列和一個集合，分別用於儲存待存取節點和已存取節點。
- 從起始節點開始，將其加入佇列和已存取集合。
- 當佇列不為空時，重複以下步驟：
- 從佇列中取出一個節點並列印。
- 遍歷該節點的所有鄰居節點，如果鄰居節點未被存取，則將其加入佇列和已存取集合。
BFS的應用
- 社交網路分析：BFS可用於找出社交網路中的連通元件，分析使用者之間的關係。
- 網路爬蟲：BFS可用於系統地瀏覽和索引網頁，發現新的網頁並提取相關資訊。
- 電腦網路：BFS用於廣播和路由協定，確保資料包的有效傳輸。
- 人工智慧：BFS可用於解決拼圖和遊戲，如八拼圖問題。
- 生物資訊學：BFS用於分析蛋白質網路，理解生物過程。
網路爬蟲範例：
from collections import deque
import requests
from bs4 import BeautifulSoup
def web_crawler_bfs(start_url, max_pages=10):
visited = set()
queue = deque([start_url])
count = 0
while queue and count < max_pages:
url = queue.popleft()
if url not in visited:
try:
response = requests.get(url)
soup = BeautifulSoup(response.text, 'html.parser')
print(f"Crawling: {url}")
title = soup.title.string if soup.title else "No title"
print(f"Title: {title}")
visited.add(url)
count += 1
for link in soup.find_all('a', href=True):
new_url = link['href']
if new_url.startswith('http'):
queue.append(new_url)
except Exception as e:
print(f"Error crawling {url}: {e}")
print(f"Crawled {count} pages")
# 範例用法
start_url = "https://example.com"
web_crawler_bfs(start_url)
內容解密：
- 初始化一個佇列和一個集合，分別用於儲存待爬取的URL和已爬取的URL。
- 從起始URL開始，將其加入佇列。
- 當佇列不為空且未達到最大爬取頁面數時，重複以下步驟：
- 從佇列中取出一個URL並爬取該頁面。
- 解析頁面內容，提取標題並列印。
- 將該URL加入已爬取集合。
- 提取頁面中的所有連結，將新的URL加入佇列。
BFS的時間複雜度和空間複雜度
- 時間複雜度：O(V + E)，其中V是節點數，E是邊數。因為BFS會存取每個節點一次並遍歷每條邊一次。
- 空間複雜度：O(V)，用於儲存佇列和已存取節點。
最佳化技術
- 雙向BFS：從起點和終點同時進行BFS，可以減少搜尋空間，特別適用於起點和終點距離較遠的情況。
- 記憶體高效BFS：使用生成器實作BFS，可以減少記憶體使用，適用於非常大的圖。
- 層級感知BFS：修改BFS以追蹤節點的層級或深度，可以在不使用額外空間的情況下實作。
雙向BFS範例：
from collections import deque
def bidirectional_bfs(graph, start, end):
if start == end:
return [start]
forward_queue = deque([(start, [start])])
backward_queue = deque([(end, [end])])
forward_visited = {start: [start]}
backward_visited = {end: [end]}
while forward_queue and backward_queue:
# 前向BFS
current, path = forward_queue.popleft()
for neighbor in graph[current]:
if neighbor in backward_visited:
return path + backward_visited[neighbor][::-1][1:]
if neighbor not in forward_visited:
new_path = path + [neighbor]
forward_visited[neighbor] = new_path
forward_queue.append((neighbor, new_path))
# 後向BFS
current, path = backward_queue.popleft()
for neighbor in graph[current]:
if neighbor in forward_visited:
return forward_visited[neighbor] + path[::-1][1:]
if neighbor not in backward_visited:
new_path = path + [neighbor]
backward_visited[neighbor] = new_path
backward_queue.append((neighbor, new_path))
return None # 找不到路徑
# 範例用法
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
path = bidirectional_bfs(graph, 'A', 'F')
print("最短路徑:", ' -> '.join(path) if path else "找不到路徑")
內容解密：
- 初始化兩個佇列和兩個集合，分別用於前向和後向BFS。
- 從起點和終點同時進行BFS，逐步擴充套件搜尋範圍。
- 當前向和後向BFS相遇時，合併路徑並傳回。
廣度優先搜尋（BFS）最佳化技術與變體
BFS 最佳化技術
在前面的章節中，我們探討了基本的廣度優先搜尋（BFS）演算法。現在，我們將探討幾種可以顯著提升 BFS 效能的最佳化技術。這些技術在特定場景下可以大幅改善演算法的效能。
1. 使用合適的資料結構
選擇合適的資料結構對於 BFS 的效能至關重要。以下是使用 deque 實作 BFS 的範例：
from collections import deque
def optimized_bfs(graph, start):
visited = set([start])
queue = deque([start])
while queue:
vertex = queue.popleft()
print(vertex, end=" ")
for neighbor in graph[vertex]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
# 範例用法
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
optimized_bfs(graph, 'A')
內容解密：
- 使用
deque作為佇列，可以提供 O(1) 的複雜度進行popleft操作，大幅提升佇列操作的效率。 visited集合用於記錄已存取的節點，避免重複存取。
2. 記錄層級資訊
在某些應用中，我們需要知道每個節點的層級。以下是修改後的 BFS 實作：
from collections import deque
def level_aware_bfs(graph, start):
visited = set([start])
queue = deque([(start, 0)])
while queue:
vertex, level = queue.popleft()
print(f"Level {level}: {vertex}")
for neighbor in graph[vertex]:
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, level + 1))
# 範例用法
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
level_aware_bfs(graph, 'A')
內容解密：
- 佇列中儲存
(vertex, level)元組，用於記錄每個節點的層級資訊。 - 在處理鄰居節點時，將層級加 1 繼續傳遞。
3. 提前終止搜尋
如果我們要搜尋特定的節點或條件，可以在滿足條件時提前終止搜尋：
from collections import deque
def early_termination_bfs(graph, start, target):
visited = set([start])
queue = deque([start])
while queue:
vertex = queue.popleft()
if vertex == target:
return True # 找到目標節點
for neighbor in graph[vertex]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return False # 未找到目標節點
# 範例用法
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
target = 'F'
result = early_termination_bfs(graph, 'A', target)
print(f"Target '{target}' found: {result}")
內容解密：
- 當找到目標節點時，立即傳回
True，終止搜尋。 - 若搜尋完成後仍未找到目標節點，則傳回
False。
BFS 變體
BFS 有多種變體，能夠在特定場景下提升演算法的效率。以下是三種重要的 BFS 變體：雙向 BFS、在加權圖上的 BFS，以及與深度優先搜尋（DFS）的比較。
1. 雙向 BFS
雙向 BFS 同時從起點和終點進行搜尋，當兩個搜尋相遇時終止。這種方法在某些圖問題中可以顯著減少搜尋空間。
from collections import deque
def bidirectional_bfs(graph, start, goal):
if start == goal:
return [start]
forward_queue = deque([(start, [start])])
backward_queue = deque([(goal, [goal])])
forward_visited = {start: [start]}
backward_visited = {goal: [goal]}
while forward_queue and backward_queue:
# 前向 BFS
path = explore(graph, forward_queue, forward_visited, backward_visited)
if path:
return path
# 後向 BFS
path = explore(graph, backward_queue, backward_visited, forward_visited)
if path:
return path[::-1]
return None
def explore(graph, queue, visited, other_visited):
current, path = queue.popleft()
for neighbor in graph[current]:
if neighbor in other_visited:
return path + other_visited[neighbor][::-1][1:]
if neighbor not in visited:
new_path = path + [neighbor]
visited[neighbor] = new_path
queue.append((neighbor, new_path))
return None
# 範例用法
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
path = bidirectional_bfs(graph, 'A', 'F')
print("Shortest path:", ' -> '.join(path) if path else "No path found")
內容解密：
- 同時從起點和終點進行搜尋，使用兩個佇列和兩個存取集合。
- 當兩個搜尋相遇時，合併路徑並傳回結果。
2. 加權圖上的 BFS
標準的 BFS 假設所有邊的權重相等，但在實際場景中，邊的權重可能不同。對於加權圖，可以使用優先佇列來實作 BFS，實質上轉化為 Dijkstra 演算法。
import heapq
def weighted_bfs(graph, start, goal):
queue = [(0, start, [])]
visited = set()
while queue:
(cost, node, path) = heapq.heappop(queue)
if node not in visited:
visited.add(node)
path = path + [node]
if node == goal:
return cost, path
for neighbor, weight in graph[node].items():
if neighbor not in visited:
heapq.heappush(queue, (cost + weight, neighbor, path))
return float('inf'), []
# 範例用法
graph = {
'A': {'B': 4, 'C': 2},
'B': {'A': 4, 'D': 3, 'E': 1},
'C': {'A': 2, 'F': 5},
'D': {'B': 3},
'E': {'B': 1, 'F': 2},
'F': {'C': 5, 'E': 2}
}
cost, path = weighted_bfs(graph, 'A', 'F')
print(f"Shortest path cost: {cost}")
print(f"Shortest path: {' -> '.join(path)}")
內容解密：
- 使用優先佇列（
heapq模組）來總是優先探索總成本最低的路徑。 - 記錄累計成本和路徑，並在到達目標節點時傳回結果。
BFS 與 DFS 的比較
瞭解 BFS 和 DFS 的特性有助於選擇合適的演算法。以下是兩者的主要區別：
- 探索順序：BFS 優先探索當前節點的所有鄰居，而 DFS 則盡可能深入探索每個分支。
- 記憶體使用：BFS 通常需要更多記憶體來儲存當前層級的所有節點，而 DFS 只需儲存當前路徑上的節點。
- 完整性：BFS 保證在無權圖中找到最短路徑，而 DFS 不一定能找到最短路徑。
- 應用場景：BFS 適合用於尋找最短路徑、層級遍歷和小深度圖的分析；DFS 則適合用於迷宮求解、拓撲排序和大深度圖的分析。
