2022年 11月 4日

BFS算法 （python)

广度优先搜索（也称宽度优先搜索，缩写BFS，以下采用广度来描述）是连通图的一种遍历策略。因为它的思想是从一个顶点V0开始，辐射状地优先遍历其周围较广的区域，故得名。

也就是我们在数据结构中学习过的BFS算法。按层数的遍历。在这里我不在赘述，在CSDN搜BFS也能找到原理。

我们的BFS是queue来维护，而DFS是stack维护。

 同上图所示，我们从A开始得到它的一个BFS就是ABCDEF。我们使用代码实现该程序。

  1. grap = {
  2.     "A":["B","C"],
  3.     "B":["A","C","D"],
  4.     "C":["A","B","D","E"],
  5.     "D":["B","C","E","F"],
  6.     "E":["C","D"],
  7.     "F":["D"]
  8. }
  9. #存图
  10.  
  11. def BFS(grap,star):                #BFS算法
  12.     queue = []                     #定义一个队列
  13.     seen = set()                   #建立一个集合，集合就是用来判断该元素是不是已经出现过
  14.     queue.append(star)             #将任一个节点放入
  15.     seen.add(star)                 #同上
  16.     while (len(queue)>0) :         #当队列里还有东西时
  17.         ver =  queue.pop(0)        #取出队头元素
  18.         notes = grap[ver]          #查看grep里面的key,对应的邻接点
  19.         for i in notes:            #遍历邻接点
  20.             if i not in seen:      #如果该邻接点还没出现过
  21.                 queue.append(i)    #存入queue
  22.                 seen.add(i)        #存入集合
  23.         print(ver)                 #打印队头元素
  24.  
  25.  
  26. print(BFS(grap,"A"))