Python BFS(广度优先搜索)

广度优先搜索（BFS）是一种遍历策略，从一个顶点开始，辐射状地优先遍历其周围较广的区域，找出最短路径。

BFS算法的实现需要使用队列来存储待访问的节点，并使用一个标记数组来记录已访问过的节点。

graph = {
    "A": ["B", "C"],
    "B": ["A", "C", "D"],
    "C": ["A", "B", "D", "F"],
    "D": ["B", "C", "E", "F"],
    "E": ["C", "D"],
    "F": ["D"],
}
def BFS(graph, start):
    # 起到队列的作用
    queue = []
    queue.append(start)
 
    #存储已经发现的节点
    seen = set()
    seen.add(start)
    #当队列不为空时判断是否还有未访问的节点
    while (len(queue) > 0):
 
        #从队列中取出一个节点
        vertex = queue.pop(0)
 
        #找到这个节点的所以根节点
        nodes = graph[vertex]
 
        #判断这些根节点有没有被访问过
        #如果没有放访问过把这个节点放入队列继续找它的子节点
        for w in nodes:
            if w not in seen:
                queue.append(w)
                seen.add(w)
        print(vertex)
BFS(graph,"A")