BFS广度优先搜索之算法框架

BFS 和 DFS 的区别

• BFS：用来搜索 最短路径 比较合适，如：求二叉树最小深度、最少步数、最少交换次数，一般与 队列 搭配使用，空间复杂度比 DFS 大很多
• DFS：适合搜索全部的解，如：寻找最短距离，一般与 栈 搭配使用

def BFS(start, target):"""计算从 start 到 target 的最近距离"""q = []	# 队列，先进先出visited = {}	# 避免走回头路q.append(start)	# 将起点加入队列visited.add(start)	step = 0	# 记录扩散步数while q:for i in range(len(q)):cur = q.pop()# 判断是否达到终点if cur == target:return step# 将 cur 相邻的节点加入队列for j in cur.adj():if j not in visited:q.insert(0, j)	# 队列：先进先出visited.add(j)# 更新步数step += 1