What is the time complexity of breadth-first search?

Worst case O(V + E). Space complexity is O(V). The queue holds at most two levels, so peak memory is the graph's width.

Breadth-first search

easy

Every node at distance 1 is dequeued before any node at distance 2. Includes the single most common BFS bug: marking nodes on dequeue instead of on enqueue.

Worst O(V + E)Space O(V)

Loading the breadth-first search engine…

Where to go next

Depth-first search

easy

A stack instead of a queue - that is the only difference.

Dijkstra's algorithm

medium

Settle the closest unvisited node, then relax its edges.

A* and BFS pathfinding

medium

Paint a maze and watch three algorithms solve it differently.