定义

·广度优先搜索指出是否有从A到B的路径。

·如果有，广度优先搜索将找出最短路径。

·面临类似于寻找最短路径的问题时，可尝试使用图来建立模型，再使用广度优先搜索来解决问题。

·有向图中的边为箭头，箭头的方向指定了关系的方向，例如，rama→adit表示rama欠adit钱。

·无向图中的边不带箭头，其中的关系是双向的，例如，ross-rachel表示"ross与rachel约会，而rache也与ross约会"。

·队列是先进先出（FIFO）的。

·栈是后进先出（LIFO）的。

·你需要按加入顺序检查搜索列表中的人，否则找到的就不是最短路径，因此搜索列表必须是队列。

·对于检查过的人，务必不要再去检查，否则可能导致无限循环。

#广度优先算法

graph={

"A":["B","C"],

"B":["A","C","D"],

"C":["A","B","D","E"],

"D":["B","C","E","F"],

"E":["C","D"],

"F":["D"]

}

def BFS(graph,s):

    #创建队列queue

    queue=[]

    #加入变量起点根s

    queue.append(s)

    # 邻居节点，判断是否重复遍历

    seen=set()#创建一个集合

    seen.add(s)#加入

    relpace=0#记录所走步长

    while queue:

        # 添加一个节点，比如"A"为vertex

        vertex=queue.pop(0)

        # 队列先进先出，所以是pop（0）先出

        # nodes为"A"的临近节点

        nodes=graph[vertex]

        #w为遍历nodes的集合

       

        for w in nodes:

             

            if w not in seen:

                # 如果w不在seen中，w则加入集合和字典

                queue.append(w)

                seen. add(w)

                     

        # 当遍历到F        

        if vertex=="F":

            break  

        print(vertex)    

        relpace +=1

    print(relpace)

BFS(graph,"A")