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