Graph Traversal
BFS and DFS — two ways to explore a graph
This concept builds on Recursion — Functions That Call Themselves, Sorting — Putting Things in Order. Consider exploring them first for the best experience.
Start at A: The Queue Holds One Node
The canvas draws 8 nodes labelled A to H joined by 7 edges. With BFS selected and A as the start node, the search marks A visited and places it alone in the queue strip under the graph. The yellow node is the one being visited now, and the dashed ring marks the start. Press the 'Step' button to visit one node at a time instead of watching the animation.
Level 1: A Hands Off to B and C
Visiting A adds its unvisited neighbours B and C to the back of the queue, so the strip reads B, C. Next B leaves the front and its new neighbours D and E join behind C: the queue reads C, D, E. B and C sit one edge from A, so the header labels them level 1. Watch each edge turn green once both of its ends have been visited.
Level 2: D, E and F Leave the Queue
Visiting C adds F, so the queue reads D, E, F: every node two edges from A, in the order it was discovered. D is a dead end, so visiting it adds nothing and the queue shrinks to E, F. Visiting E adds G and H, giving F, G, H. Notice that the search finishes the whole level 2 row before touching the bottom row.
Level 3: G and H Empty the Queue
F is another dead end, so after it the queue holds only G, H: the two nodes three edges from A. G leaves the front, then H, and nothing new joins because every neighbour has already been seen. When the last node leaves, the strip reports the queue as empty, which is the signal that every node reachable from A has been found.
Worked Example: BFS From A in 8 Visits
Read the finished run: the order line shows A, B, C, D, E, F, G, H, one visit per node. Before each visit the queue held 1, 2, 3, 3, 2, 3, 2 and 1 nodes, so it never grew past 3. The levels are A at 0, B and C at 1, D, E and F at 2, G and H at 3. The animation now holds here; press 'Step' or Reset to replay it.
Switch to DFS and Compare
Press 'DFS (Stack)' and the same graph is searched with a stack instead of a queue. From A the order becomes A, B, D, E, G, H, C, F: the search dives down the left branch to G and H before backing up to C. Choose a different 'Start node', or click any node, to see both orders change. Either search still visits each node exactly once.
How It Works — Step by Step
-
1
Start at A: The Queue Holds One Node
The canvas draws 8 nodes labelled A to H joined by 7 edges. With BFS selected and A as the start node, the search marks A visited and places it alone in the queue strip under the graph. The yellow node is the one being visited now, and the dashed ring marks the start. Press the 'Step' button to visit one node at a time instead of watching the animation.
-
2
Level 1: A Hands Off to B and C
Visiting A adds its unvisited neighbours B and C to the back of the queue, so the strip reads B, C. Next B leaves the front and its new neighbours D and E join behind C: the queue reads C, D, E. B and C sit one edge from A, so the header labels them level 1. Watch each edge turn green once both of its ends have been visited.
-
3
Level 2: D, E and F Leave the Queue
Visiting C adds F, so the queue reads D, E, F: every node two edges from A, in the order it was discovered. D is a dead end, so visiting it adds nothing and the queue shrinks to E, F. Visiting E adds G and H, giving F, G, H. Notice that the search finishes the whole level 2 row before touching the bottom row.
-
4
Level 3: G and H Empty the Queue
F is another dead end, so after it the queue holds only G, H: the two nodes three edges from A. G leaves the front, then H, and nothing new joins because every neighbour has already been seen. When the last node leaves, the strip reports the queue as empty, which is the signal that every node reachable from A has been found.
-
5
Worked Example: BFS From A in 8 Visits
Read the finished run: the order line shows A, B, C, D, E, F, G, H, one visit per node. Before each visit the queue held 1, 2, 3, 3, 2, 3, 2 and 1 nodes, so it never grew past 3. The levels are A at 0, B and C at 1, D, E and F at 2, G and H at 3. The animation now holds here; press 'Step' or Reset to replay it.
-
6
Switch to DFS and Compare
Press 'DFS (Stack)' and the same graph is searched with a stack instead of a queue. From A the order becomes A, B, D, E, G, H, C, F: the search dives down the left branch to G and H before backing up to C. Choose a different 'Start node', or click any node, to see both orders change. Either search still visits each node exactly once.
Key Takeaways
BFS uses a queue; DFS uses a stack
The data structure determines the traversal order. A queue gives level-by-level (breadth-first) exploration. A stack (or call stack for recursion) gives depth-first exploration.
BFS finds shortest paths in unweighted graphs
Because BFS explores nodes in order of their distance from the source, the first time it reaches a node is via the shortest path.
DFS is memory-efficient for deep graphs
DFS only needs to store nodes on the current path, making it more memory-efficient than BFS when the graph is very deep but not very wide.
Both run in O(V + E) time
Both BFS and DFS visit every vertex and edge at most once, giving O(V + E) time complexity where V is the number of vertices and E is the number of edges.
Connected Concepts
Hash Tables
Graph adjacency lists are often stored in hash tables for O(1) neighbor lookups.
Recursion
DFS has a natural recursive implementation — each call explores one branch of the graph.
Sorting
BFS guarantees shortest-path order in unweighted graphs, complementing sorting-based search strategies.
Graph Theory
Nodes, edges and adjacency lists: the structure every traversal walks over.
Dijkstra's Algorithm
Give every edge a weight and swap the plain queue for a priority queue, and breadth-first search becomes Dijkstra's shortest-path algorithm.
Topological Sort
Record nodes as depth-first search finishes them, read the list backwards, and every task comes after the tasks it depends on.
Percolation
Breadth-first search from the top row finds whether water can flow all the way through a grid of randomly opened squares.
Updated
- — New connections to Dijkstra's Algorithm, Topological Sort and Percolation.
- — Steps walk one breadth-first search from A level by level, with a Step button, a worked example and 2 new quiz items.