深度优先遍历简称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 = edgeif 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()# 递归 DFSdef depth_first_search(self, root = None):order = []def dfs(node):self.visited[node] = Trueorder.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过的单独处理，再做一次dfsfor node in self.nodes():if node not in self.visited:dfs(node)self.visited = {}print(order)# print('final visited', self.visited)return order# 非递归 DFSdef 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] = Trueprint('self.visited', self.visited)breakelse: stack.pop() if root:stack.append(root)order.append(root)self.visited[root] = Truedfs()    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# BFSdef breadth_first_search(self,root=None):que = []order = []def bfs():while len(que) > 0: # 队列非空node = que.pop(0) # 从左侧开始弹出  list对象有pop但是没有popleftself.visited[node] = Truefor 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