文章概述
广度优先搜索算法概述
广度优先搜索算法
广度优先算法是基于树或者图的，当然树也是一种特殊的图，因此我们先简单的介绍下图的相关知识。
介绍：图在计算机学科中是一种重要的数据结构，是树的拓展，由节点和边构成，边可以有权重，也可以有方向，当然，也可以没有。如下简单无向图：
有向图是方向的，用箭头表示：
背景
想要求一个地点到另一个地点，如下图所示，求A到D的最短距离，已知相邻节点之间的距离是相同的。
实现图：
首先用代码表示图，建立数据结构。
那么图如何表示呢，我们知道，图是由节点构成的，每个节点可能有邻居，如A的邻居有B、C，B的邻居是D，D没有邻居，那么我们可以用dict来表示这些关系
graph = {}
graph['A'] = ['B', 'C']
graph['B'] = ['D']
graph['C'] = ['E']
graph['D'] = []
graph['E'] = ['D']
广度优先搜索算法
算法描述：
1.创建一个队列，用于存储要检查的节点
2.从队列首部弹出一个节点
3.判断这个节点是否检查过，若检查过，重复执行步骤2
4.检查这个节点是否目的节点，是的话，完事，否则，将这个节点的邻居加入队列的尾部，重复2,3,4，一直到队列为空
from collections import deque
graph = {}
graph['A'] = ['B', 'C']
graph['B'] = ['D']
graph['C'] = ['E']
graph['D'] = []
graph['E'] = ['D']
def solution(start, end): #起点和终点
queue = deque() #创建一个队列
queue += graph[start] #先把起点的邻居加入队列，检查一级关系
searched = [start] # 已检查的点，防止造成死循环， 起点不用检查可以加进来
while queue:
address = queue.popleft() # 弹出节点
if address not in searched:
if address == end:
searched.append(end)
return searched # 返回所有已检查的节点，为后续打印最短路径做准备
else:
queue += graph[address]
searched.append(address)
return False
searched = solution('A','D')
如果searched 存在，就代表有路径可以让A通往D，其实这个代码实现了一种搜索算法，检索A到D是否存在可达路径，且搜索的时候走的是最短路径。
另外时间复杂度，这个过程我们使用到了队列，将每个节点添加进去的时间都是固定的，为O(1)，那么广度优先搜索算法的时间复杂度为O(V+E)，其中V为节点数，E为边数。
下面我们想个办法打印出这个最短路径来。
# 求搜索经历的最短路径
#接上面代码 searched 是一个列表
l = []
address = 'D'
l.append(address)
while address != 'A':
for i in searched:
if address in graph[i]:
l.append(i)
address = i
break
print(l[::-1])
我们根据目的节点，反向打印路径中节点，然后取反就是我们的最短路径了['A','B','D']
当然此算法还可以优化，大家可以发动脑筋。
网友评论