搜索與遍歷

絕大多數(shù)搜索的處理叫暴力搜索，或者說比較簡單樸素的搜索。如果數(shù)據(jù)結(jié)構(gòu)本身沒有任何特點，很普通的樹或者圖，我們要做的一件事就是把所有節(jié)點都遍歷一次。

• 每個節(jié)點都要訪問一次
• 每個節(jié)點僅僅要訪問一次
• 對于節(jié)點的訪問順序不限
  • 深度優(yōu)先搜索（Depth-First-Search）
  • 廣度優(yōu)先搜索（Breadth-First-Search）
  • 也可以根據(jù)現(xiàn)實業(yè)務(wù)場景自定義優(yōu)先級優(yōu)先（啟發(fā)式搜索）

一、深度優(yōu)先搜索（Depth-First-Search）

1.DFS訪問順序

樹訪問順序

圖訪問順序

2.代碼模板

# 示例代碼 def dfs(node):if node in visited:# already visitedreturnvisited.add(node)# process current node # ... # logic heredfs(node.left)dfs(node.right)#遞歸寫法（常用） visited = set() def dfs(node,visited):visited.add(node)# process current node here.# ... for next_node in node.children():if not next_node in visited:dfs(next node,visited)# 非遞歸寫法(模擬遞歸，用棧來解決) def DFS(self,tree):if tree.root is None:return []visited, stack = [], [tree.root]while stack:node = stack.pop()visited.add(node)process(node)nodes = generate_related_nodes(node)stack.push(nodes)# other processing work...# 遞歸寫法修改后的代碼模板(推薦記憶) visited = set() def dfs(node,visited):if node in visited: # terminator# already visitedreturnvisited.add(node)# process current node here.... for next_node in node.children():if not next_node in visited:dfs(next_node,visited)

二、廣度優(yōu)先搜索（Breadth-First-Search）

1. 訪問順序

想象成水波紋，一層一層向外擴散。

訪問順序

2. 代碼模板

# BFS代碼（隊列和循環(huán)實現(xiàn)） def BFS(graph, start, end):queue = []queue.append([start])visited.add(start)while queue:node = queue.pop()visited.add(node)process(node)nodes = generate_related_nodes(node)queue.push(nodes)# other processing work...

三、搜索順序?qū)Ρ?/h2>

DFS與BFS對比

總結(jié)

以上是生活随笔為你收集整理的广度优先搜索_深度优先搜索和广度优先搜索[09]的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。