BFS计算最短路径（python)

我们这里所说的最短路径是从根节点到某一指定叶子节点的最短路径。

 如上图，我们把E,当成根节点，我们到B的最短路径就是ECB。

我们用代码来实现。我们用到的思路就是使用一个字典来存放节点的父节点，仔细看parent和ver 的关系，ver是取到的队头元素，我们用for循环在grep[ver]中找到子元素，所以我们可以反过来用parent[i] = ver 来存放子对父的key_value。

grap = {
    "A": ["B", "C"],
    "B": ["A", "C", "D"],
    "C": ["A", "B", "D", "E"],
    "D": ["B", "C", "E", "F"],
    "E": ["C", "D"],
    "F": ["D"]
}


# 存图

def BFS(grap, star):                    # BFS算法
    queue = []                          # 定义一个队列
    seen = set()                        # 建立一个集合，集合就是用来判断该元素是不是已经出现过
    queue.append(star)                  # 将任一个节点放入
    seen.add(star)                      # 同上
    parent = {star:None}                #存放parent元素
    while (len(queue) > 0):             # 当队列里还有东西时
        ver = queue.pop(0)              # 取出队头元素
        notes = grap[ver]               # 查看grep里面的key,对应的邻接点
        for i in notes:                 # 遍历邻接点
            if i not in seen:           # 如果该邻接点还没出现过
                queue.append(i)         # 存入queue
                seen.add(i)             # 存入集合
                parent[i] = ver         #将元素对应的parent元素存入字典中
    return parent


parent = BFS(grap, "E")
a = 'B'
while a != None:
    print(a)
    a = parent[a]