0---1 BFS
简介0-1 bfs
bfs可以O(V+E)求解边权全为1的图上最短路。
而当边权只有0或1时，使用其它最短路算法是有些浪费的，此时可以使用bfs的变种：0-1 bfs来快速求解，复杂度仍为O(V+E).
01bfs维护一个双端队列，当边权为0时，使用push_front，当边权为1时，使用push_back.
节点的出队顺序是这样的：0,0,0,0,0,1,1,1,1,2,2,2,3,3,3,…
画个图就懂了
2019-07-26 12:59 已编辑 西南科技大学 客户端其它
关注
全部评论
相关推荐
投递TP-LINK等公司7个岗位 07-15 19:18
华南理工大学 Java 
LazyBreeze：项目尽量体现你对技术的理解和深度，不是说把中间件用一下就完事了，你项目里面提到集群和分布式，你真在服务器上部署过吗，感觉太假了，第二个项目说自己用了微服务的什么组件，只是用了没有自己的思考，很难让面试官注意到你的简历。针对某几个技术点自己多思考一下，考虑一下有没有别的替代方案，可以写一下，即使没有真的实现
点赞 评论 收藏
分享
有礼貌的干饭人G了：校友直接投就好了，我简历上项目就只有一个原封不动的外卖也进了一家不错的独角兽
点赞 评论 收藏
分享
查看6道真题和解析