python 图的广度优先搜索BFS

python 图的广度优先搜索BFS 前言

图的广度优先搜索，采用队列方式
手绘有向图

程序

import queue
from queue import Queue
graph = {
    "a": ["b", "c"],
    "b": ["a", "d"],
    "c": ["a", "d"],
    # "d": [ "e"],
    "d": ["c", "e"],  # add loop
    "e": ["d"]
}

##
vis= []
q = queue.Queue()
def bfs(v):
    q.put(v)  # 进队列
    vis.append(v) # 加入访问过的列表
    while not q.empty():
        u = q.get()
        # print(u)
        for vi in graph[u]:
            if vi not in vis:
                vis.append(vi)
                q.put(vi)
    return vis


bfs("e")
vis

结果展示

['e', 'd', 'c', 'a', 'b']