先說(shuō)明廣度優(yōu)先搜索BFS就是寬度優(yōu)先搜索二者通常沒(méi)有區(qū)別真正相對(duì)的是 深度優(yōu)先搜索DFS。所以嚴(yán)格說(shuō)只有 DFS 和 BFS 兩類(lèi)。下面寫(xiě)三段代碼DFS、BFS廣度/寬度、優(yōu)先隊(duì)列搜索方便對(duì)比。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用隊(duì)列一層一層訪(fǎng)問(wèn)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)先隊(duì)列搜索不是按層也不是一路到底而是按“優(yōu)先級(jí)”擴(kuò)展# 這里示例字母越大越優(yōu)先用 -ord(x) 當(dāng)優(yōu)先級(jí)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)先隊(duì)列搜索)best_first(A, lambda x: -ord(x))print()# 輸出A C F B E G D對(duì)比總結(jié)算法 數(shù)據(jù)結(jié)構(gòu) 特點(diǎn) 示例輸出DFS 深度優(yōu)先 棧 / 遞歸 一條路走到底不按層 A B D E G C FBFS 廣度/寬度優(yōu)先 隊(duì)列 一層一層訪(fǎng)問(wèn)無(wú)權(quán)圖可求最短路徑 A B C D E F G優(yōu)先隊(duì)列搜索 堆 每次選優(yōu)先級(jí)最高/代價(jià)最小的節(jié)點(diǎn) 取決于優(yōu)先級(jí)關(guān)鍵區(qū)別· 深度優(yōu)先 DFS先深入走不動(dòng)再回頭?！?廣度優(yōu)先 BFS也叫寬度優(yōu)先先訪(fǎng)問(wèn)離起點(diǎn)近的所有節(jié)點(diǎn)再訪(fǎng)問(wèn)下一層?！?優(yōu)先隊(duì)列搜索不關(guān)心層數(shù)只關(guān)心“誰(shuí)優(yōu)先級(jí)更高”常用于 Dijkstra、A*、最佳優(yōu)先搜索等。文章僅供參考用。