Graph Traversal

BFS and DFS — two ways to explore a graph

Computer Science Algorithms intermediate 12 min

This concept builds on Recursion — Functions That Call Themselves, Sorting — Putting Things in Order. Consider exploring them first for the best experience.

Step 1 of 6

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

Step 1 of 6
  1. 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. 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. 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. 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. 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. 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.

Added
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.