什么时候用BFS

一.图的遍历
1.层级遍历
2.由点及面
3.拓扑排序
二.最短路径
求简单图最短路径，即所有边都等权或者无权的无向图中

能用BFS解决的问题一定不要用DFS
BFS和DFS的时间复杂度

BFS的时间复杂度：
若一个图有M条边N个点，参考算法导论

矩阵形式的BFS
通用的两种工具：

  1. 坐标变换矩阵
  2. 边界函数检查

BFS的一些注意
在无向图的遍历中除了拓扑排序用度来控制加入顺序和是否入列，其余BFS的使用都要结合HashSet来去重，因为一条边的两个端点AB，A在B的邻接表里，B也在A的邻接表里，重复添加没效率

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容