先說明廣度優(yōu)先搜索BFS就是寬度優(yōu)先搜索二者通常沒有區(qū)別真正相對的是 深度優(yōu)先搜索DFS。所以嚴格說只有 DFS 和 BFS 兩類。下面寫三段代碼DFS、BFS廣度/寬度、優(yōu)先隊列搜索方便對比。pythonfrom collections import dequeimport heapqgraph {A: [B, C],B: [D, E],C: [F],D: [],E: [G],F: [],G: []}# 1. 深度優(yōu)先 DFS用遞歸/棧一條路走到黑def dfs(node, visitedNone):if visited is None:visited set()visited.add(node)print(node, end )for nxt in graph[node]:if nxt not in visited:dfs(nxt, visited)print(DFS 深度優(yōu)先)dfs(A)print(\n)# 輸出A B D E G C F# 2. 廣度優(yōu)先 / 寬度優(yōu)先 BFS用隊列一層一層訪問def bfs(start):q deque([start])visited {start}while q:node q.popleft()print(node, end )for nxt in graph[node]:if nxt not in visited:visited.add(nxt)q.append(nxt)print(BFS 廣度優(yōu)先 寬度優(yōu)先)bfs(A)print(\n)# 輸出A B C D E F G# 3. 優(yōu)先隊列搜索不是按層也不是一路到底而是按“優(yōu)先級”擴展# 這里示例字母越大越優(yōu)先用 -ord(x) 當優(yōu)先級def best_first(start, priority):pq [(priority(start), start)]visited set()while pq:_, node heapq.heappop(pq)if node in visited:continuevisited.add(node)print(node, end )for nxt in graph[node]:if nxt not in visited:heapq.heappush(pq, (priority(nxt), nxt))print(優(yōu)先隊列搜索)best_first(A, lambda x: -ord(x))print()# 輸出A C F B E G D對比總結(jié)算法 數(shù)據(jù)結(jié)構(gòu) 特點 示例輸出DFS 深度優(yōu)先 棧 / 遞歸 一條路走到底不按層 A B D E G C FBFS 廣度/寬度優(yōu)先 隊列 一層一層訪問無權(quán)圖可求最短路徑 A B C D E F G優(yōu)先隊列搜索 堆 每次選優(yōu)先級最高/代價最小的節(jié)點 取決于優(yōu)先級關(guān)鍵區(qū)別· 深度優(yōu)先 DFS先深入走不動再回頭。· 廣度優(yōu)先 BFS也叫寬度優(yōu)先先訪問離起點近的所有節(jié)點再訪問下一層?！?優(yōu)先隊列搜索不關(guān)心層數(shù)只關(guān)心“誰優(yōu)先級更高”常用于 Dijkstra、A*、最佳優(yōu)先搜索等。文章僅供參考用。