Specialized BFS

0-1 BFS Algorithm

Efficient shortest path algorithm for graphs where edge weights are only 0 or 1. By using a Double-Ended Queue (Deque), it achieves linear complexity O(V + E), bypassing the overhead of a Priority Queue.

Time ComplexityO(V + E)

Space ComplexityO(V)

Try Interactive Simulator

Deque Strategy

Weight 0 edges are unshifted to the front, while weight 1 edges are pushed to the back. This maintains the sorted order naturally.

Why 0-1?

If all weights are the same, BFS works. If they are 0/1, we can still avoid Dijkstra's sorting by prioritizing 0-weight "free" moves.

🖱️ Click to Add • ↔️ Drag to Move • ⌨️ Shift+Drag to Join • 🔘 Double-Click to Toggle Weight

Loading Lab...

Specialized BFS

0-1 BFS Algorithm

Time ComplexityO(V + E)

Space ComplexityO(V)

Try Interactive Simulator

Deque Strategy

Weight 0 edges are unshifted to the front, while weight 1 edges are pushed to the back. This maintains the sorted order naturally.

Why 0-1?

If all weights are the same, BFS works. If they are 0/1, we can still avoid Dijkstra's sorting by prioritizing 0-weight "free" moves.

🖱️ Click to Add • ↔️ Drag to Move • ⌨️ Shift+Drag to Join • 🔘 Double-Click to Toggle Weight

Zero One Bfs

Zero One Bfs

0-1 BFS Algorithm

Deque Strategy

Why 0-1?

0-1 BFS Algorithm

Deque Strategy

Why 0-1?