Graph traversal and shortest paths
Graphs generalise trees by dropping the single-parent restriction, so traversal has to track visited nodes or risk looping forever. BFS explores in expanding rings from the source; DFS commits to one path until it dead-ends and then backtracks.
That difference decides which to reach for. BFS finds the fewest-edges path on an unweighted graph; DFS suits cycle detection, topological ordering, and connected components. Dijkstra extends BFS with a priority queue to handle non-negative edge weights.
Time and space complexity
| Algorithm | Time | Space | Use case |
|---|---|---|---|
| BFS | O(V + E) | O(V) | Shortest path, unweighted |
| DFS | O(V + E) | O(V) | Cycles, components, topological sort |
| Dijkstra | O((V + E) log V) | O(V) | Shortest path, non-negative weights |
| Bellman-Ford | O(V × E) | O(V) | Handles negative edges |
| Topological sort | O(V + E) | O(V) | Dependency ordering, DAGs only |
How to use this visualizer
Pick a traversal and a starting node.
Step through and watch the frontier — a queue for BFS, a stack or recursion for DFS.
Follow the visited set and see why revisiting is skipped.
On Dijkstra, watch tentative distances get relaxed as shorter paths appear.
Frequently asked questions
Use BFS when you need the shortest path in an unweighted graph or the minimum number of steps, because it reaches every node by the fewest edges first. Use DFS for cycle detection, topological sorting, connected components, and exhaustive path exploration. BFS uses memory proportional to the widest level; DFS uses memory proportional to the deepest path.
Start every node at infinite distance except the source at zero. Repeatedly extract the unvisited node with the smallest tentative distance from a priority queue, then relax each outgoing edge — if travelling through the current node reaches a neighbour more cheaply, update that neighbour. Once a node is extracted its distance is final. With a binary heap this runs in O((V + E) log V).
Dijkstra assumes that once it extracts the closest unvisited node, no cheaper route to it can appear later. A negative edge breaks that assumption, since a longer-looking detour can become cheaper further along. Bellman-Ford handles negative weights by relaxing every edge V-1 times, at O(V × E), and can also report negative cycles.
In an undirected graph, run DFS and report a cycle if you reach a visited node that is not the immediate parent. In a directed graph, track nodes on the current recursion stack — an edge back to a node still on the stack is a back edge and proves a cycle. Alternatively, run Kahn's topological sort: if it emits fewer than V nodes, a cycle exists.