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,…
画个图就懂了

全部评论

相关推荐

点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务