文章概述

广度优先搜索算法概述

广度优先搜索算法

广度优先算法是基于树或者图的，当然树也是一种特殊的图，因此我们先简单的介绍下图的相关知识。
介绍：图在计算机学科中是一种重要的数据结构，是树的拓展，由节点和边构成，边可以有权重，也可以有方向，当然，也可以没有。如下简单无向图：

有向图是方向的，用箭头表示：

背景

想要求一个地点到另一个地点，如下图所示，求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']
当然此算法还可以优化，大家可以发动脑筋。