Python实现 宽度/广度优先搜索算法, 深度优先搜索算法
1. 二叉树图2. 宽度/广度优先搜索算法(Breadth First Search，BSF)3. 深度优先搜索算法4. 宽度/广度优先搜索算法实现5. 深度优先搜索算法实现6. 完整代码实现1. 二叉树图
2. 宽度/广度优先搜索算法(Breadth First Search，BSF)
工作原理:
从图中某顶点v出发，首先访问定点v在访问了v之后依次访问v的各个未曾访问过的邻接点；然后分别从这些邻接点出发依次访问它们的邻接点，并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问;直至图中所有已被访问的顶点的邻接点都被访问到;如果此时图中尚有顶点未被访问，则需要另选一个未曾被访问过的顶点作为新的起始点，重复上述过程，直至图中所有顶点都被访问到为止。
换句话说，广度优先搜索遍历图的过程是以v为起点，由近至远，依次访问和v有路径相通且路 径长度为1,2…的顶点。
如上图的BFS访问顺序为：A->B->C->D->E->F
3. 深度优先搜索算法
工作原理:
从顶点v出发，首先访问该顶点;然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图;直至图中所有和v有路径相通的顶点都被访问到。若此时尚有其他顶点未被访问到，则另选一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止
如上图的BFS访问顺序为：A->B->D->E->C->F
4. 宽度/广度优先搜索算法实现
# 宽度优先算法的实现def BFS(self, root):#首先判断根节点是否为空节点if root != None:search_queue = deque()search_queue.append(root)visited = []else:print('root is None')return -1while search_queue:person = search_queue.popleft()self.order.append(person)if (not person in visited) and (person in self.neighbor.keys()):search_queue += self.neighbor[person]visited.append(person)
5. 深度优先搜索算法实现
# 深度优先算法的实现def DFS(self, root):# 首先判断根节点是否为空节点if root != None:search_queue = deque()search_queue.append(root)visited = []else:print('root is None')return -1while search_queue:person = search_queue.popleft()self.order.append(person)if (not person in visited) and (person in self.neighbor.keys()):tmp = self.neighbor[person]tmp.reverse()for index in tmp:search_queue.appendleft(index)visited.append(person)
6. 完整代码实现
# -*- coding: utf-8 -*-from collections import deque # 线性表的模块# 首先定义一个创建图的类，使用邻接矩阵class Graph(object):def __init__(self, *args, **kwargs):self.order = [] # visited orderself.neighbor = {}def add_node(self, node):key, val = nodeif not isinstance(val, list):print('节点输入时应该为一个线性表') # 避免不正确的输入self.neighbor[key] = val# 宽度优先算法的实现def BFS(self, root):#首先判断根节点是否为空节点if root != None:search_queue = deque()search_queue.append(root)visited = []else:print('root is None')return -1while search_queue:person = search_queue.popleft()self.order.append(person)if (not person in visited) and (person in self.neighbor.keys()):search_queue += self.neighbor[person]visited.append(person)# 深度优先算法的实现def DFS(self, root):# 首先判断根节点是否为空节点if root != None:search_queue = deque()search_queue.append(root)visited = []else:print('root is None')return -1while search_queue:person = search_queue.popleft()self.order.append(person)if (not person in visited) and (person in self.neighbor.keys()):tmp = self.neighbor[person]tmp.reverse()for index in tmp:search_queue.appendleft(index)visited.append(person)def clear(self):self.order = []def node_print(self):for index in self.order:print(index, end=' ')if __name__ == '__main__':# 创建一个二叉树图g = Graph()g.add_node(('A', ['B', 'C']))g.add_node(('B', ['D', 'E']))g.add_node(('C', ['F']))# 进行宽度优先搜索g.BFS('A')print('宽度优先搜索:')print(' ', end=' ')g.node_print() # A B C D E Fg.clear()# 进行深度优先搜索print('\n\n深度优先搜索:')print(' ', end=' ')g.DFS('A')g.node_print() # A B D E C Fprint()
