算法现学现卖——BFS

作者:杨润炜
日期:2020/4/15 23:10

BFS

  • 广度优先遍历;
  • 从根节点出发,向外一圈圈扩散地遍历,可以想像水波一样一圈圈向外扩散;

求最短or最远距离

  • 最短距离:利用广度优先的扩散式遍历的特点,当a扩散到b时,两点的距离就是遍历的层数;
  • 最远距离:最后遍历到的节点的层数;
  • 单源BFS适用找树,多源BFS适用搜图,因为树是有方向的,图可能有环路,所以用多源时需要判断节点是否被访问过,防止死循环

代码模板

  1. def BFS():
  2. distance = 0 # 距离
  3. queue = [start]
  4. while queue:
  5. distance += 1
  6. size = len(queue)
  7. # 遍历同一层的节点
  8. while size:
  9. node = queue.pop(0)
  10. if is_end():
  11. return distance
  12. # 节点访问判重,可以将访问过的节点存起来判断,也可以改变节点的值标识已被访问,这样可以节省空间
  13. if not visited:
  14. queue.append(new_node)
  15. size -= 1

对应的题目

01矩阵
地图分析

更多算法题解与总结

感谢您的阅读!
如果看完后有任何疑问,欢迎拍砖。
欢迎转载,转载请注明出处:http://www.yangrunwei.com/a/104.html
邮箱:glowrypauky@gmail.com
QQ: 892413924