python-数据结构 队列和广度优先搜索（BFS）

1.队列和广度优先搜索（BFS）

原题来自LeetCode
广度优先搜索（BFS）的一个常见应用是找出从根结点到目标结点的最短路径。在本文中，我们提供了一个示例来解释在 BFS 算法中是如何逐步应用队列的。

2.示例

如何使用 BFS 来找出根结点 A 和目标结点 G 之间的最短路径。
演示动画

3.python代码

我们使用了python自带的deque类来实现队列。

from collections import deque  # python自带的队列模型

point = dict()
point['A'] = ['B', 'C', 'D']
point['B'] = ['E']
point['C'] = ['E', "F"]
point['D'] = ['G']
point['F'] = ['G']
point['E'] = ['']
point['G'] = ['']


def search_G(name):
    """
    通过A节点寻找到达G的最短路径
    :param name:
    :return:
    """
    search_queue = deque()  # 建立一个双端队列
    search_queue += point[name]  # 将你的第一代子元素都加入到这个搜索队列中
    searched = []  # 这个数组用于记录检查过的元素
    search_order = [name]  # 列表用于记录找到G这个节点的广度优先遍历顺序
    while search_queue:  # 队列不为空时循环执行
        element = search_queue.popleft()  # 对队列中的第一项进行判断，出队
        if element not in searched:  # 仅当这个元素没被检查过时才检查
            search_order.append(element)  # 记录广度优先查找G的顺序
            if element == "G":  # 如果是G则说明找到了
                print(element + ' is been discovered')
                return search_order
            else:  # 如果element不是G，就将这个element的子元素都加入搜索队列
                search_queue += point[element]  # 将未搜索的元素添加到队列当中去
                searched.append(element)  # 将这个元素标记为检查过


print(search_G("A"))