广度优先搜索_深度优先搜索和广度优先搜索[09]

搜索与遍历

绝大多数搜索的处理叫暴力搜索，或者说比较简单朴素的搜索。如果数据结构本身没有任何特点，很普通的树或者图，我们要做的一件事就是把所有节点都遍历一次。

每个节点都要访问一次每个节点仅仅要访问一次对于节点的访问顺序不限深度优先搜索（Depth-First-Search）广度优先搜索（Breadth-First-Search）也可以根据现实业务场景自定义优先级优先（启发式搜索）

一、深度优先搜索（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)

二、广度优先搜索（Breadth-First-Search）

1. 访问顺序

想象成水波纹，一层一层向外扩散。

2. 代码模板

# BFS代码（队列和循环实现）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...

三、搜索顺序对比