深度优先遍历简称DFS(Depth First Search),广度优先遍历简称BFS(Breadth First Search),它们是遍历图当中所有顶点的两种方式。下面分别介绍两种基本的搜索算法。
理论介绍
深度优先遍历DFS
DFS属于图算法的一种,是针对图和树的遍历算法。深度优先搜索是图论中的经典算法,利用深度优先搜索算法可以产生目标图的相应拓扑排序表,利用拓扑排序表可以方便的解决很多相关的图论问题,如最大路径问题等等。一般用堆或栈来辅助实现DFS算法。其过程简要来说是对每一个可能的分支路径深入到不能再深入为止,如果遇到死路就往回退,回退过程中如果遇到没探索过的支路,就进入该支路继续深入,每个节点只能访问一次。
广度优先遍历BFS
广度优先搜索(也称宽度优先搜索)是连通图的一种遍历算法,也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和广度优先搜索类似的思想。属于一种盲目搜寻法,目的是系统地展开并检查图中的所有节点,以找寻结果。换句话说,它并不考虑结果的可能位置,彻底地搜索整张图,直到找到结果为止。基本过程,BFS是从根节点开始,沿着树(图)的宽度遍历树(图)的节点。如果所有节点均被访问,则算法中止。一般用队列数据结构来辅助实现BFS算法。
广度优先搜索应用:层序遍历、最短路径、求二叉树的最大高度、
由点到面遍历图、拓扑排序
深度优先搜索应用:先序遍历,中序遍历,后序遍历
图解
假设从0开始访问所有节点,可能的路径有哪些?
(1)DFS方法
首先选择1,然后到7、8,发现走不动了。
然后退回到7,再探索节点10。回退到1,探索9:
再退回到景点0,后续依次探索2、3、5、4、6,走完所有节点:
二叉树的前序、中序、后序遍历,本质上可以认为是深度优先遍历。是一种回溯思想。
(2)BFS方法
首先探索节点0的相邻节点1、2、3、4:
接着,探索与节点0相隔一层的7、9、5、6:
最后,探索与节点0相隔两层的节点8、10:
可以看出,BFS是一层一层的由内向外遍历,二叉树的层序遍历本质上可以认为是广度优先遍历。
代码框架
DFS
非递归:
1.利用栈实现
2.从源节点开始把节点按照深度放入栈,然后弹出
3.每弹出一个点,把该节点下一个没有进过栈的邻接点放入栈
4.直到栈为空
BFS
1.利用队列实现
2.从源节点开始依次按照宽度进队列,然后弹出
3.每弹出一个节点,就把该节点所有没有进过队列的邻接点放入队列
4.直到队列为空
供参考:
class Graph:
# *args 把参数打包成tuple供函数调用。**kwargs把 x = a,y=b打包成字典{x:a,y:b}供函数调用
def __init__(self, *args, **kwargs):
self.neighbors = {}
self.visited = {}
def add_nodes(self, nodes):
for node in nodes:
self.add_node(node)
def add_node(self, node):
print('self.nodes()',self.nodes())
if node not in self.nodes():
self.neighbors[node] = [node]
def add_edge(self, edge):
u, v = edge
if u not in self.neighbors[v] and v not in self.neighbors[u]:
self.neighbors[u].append(v)
if u != v: # 没有自环
self.neighbors[v].append(u)
def nodes(self):
return self.neighbors.keys()
# 递归 DFS
def depth_first_search(self, root = None):
order = []
def dfs(node):
self.visited[node] = True
order.append(node)
for n in self.neighbors[node]:
if n not in self.visited:
dfs(n)
if root:
dfs(root) # dfs(0)
# print('visited', self.visited)
#对于不连通的结点(即dfs(root)完仍是没有visit过的单独处理,再做一次dfs
for node in self.nodes():
if node not in self.visited:
dfs(node)
self.visited = {}
print(order)
# print('final visited', self.visited)
return order
# 非递归 DFS
def depth_first_search_2(self, root=None):
stack = []
order = []
def dfs():
while stack:
print('stack',stack)
node = stack[-1] # 栈顶元素
for n in self.neighbors[node]:
if n not in self.visited:
order.append(n)
stack.append(n)
# stack.append(self.neighbors[n])
self.visited[n] = True
print('self.visited', self.visited)
break
else:
stack.pop()
if root:
stack.append(root)
order.append(root)
self.visited[root] = True
dfs()
for node in self.nodes():
if node not in self.visited:
stack.append(node)
order.append(node)
self.visited[node] = True
dfs()
# self.visited = {} # 非必须
print(order)
return order
# BFS
def breadth_first_search(self,root=None):
que = []
order = []
def bfs():
while len(que) > 0: # 队列非空
node = que.pop(0) # 从左侧开始弹出 list对象有pop但是没有popleft
self.visited[node] = True
for n in self.neighbors[node]:
print('self.visited', self.visited)
print('que', que)
if n not in self.visited and n not in que:
que.append(n)
order.append(n)
if root:
que.append(root)
order.append(root)
bfs()
for node in self.nodes():
if not node in self.visited:
que.append(node)
order.append(node)
self.visited = {}
print(order)
return order
参考:
https://blog.csdn.net/weixin_40314737/article/details/80893507