Graph Traversal: DFS and BFS
Depth-First Search (DFS) dives as deep as it can and backs up at dead ends, using a stack. Breadth-First Search (BFS) spreads out level by level, using a queue. Draw your own graph and watch both visit every vertex and every edge.
Editing: click empty space to add a vertex · click one vertex, then another, to add (or remove) the edge between them · drag a vertex to move it · in ✖ mode click a vertex or an edge to delete it. Ties are broken alphabetically, like the textbook.
How to read this
Vertex colors. Blue is the vertex being processed (DFS: the top of the stack; BFS: the front of the queue). Yellow is the neighbor being checked. Purple vertices are waiting on the stack or in the queue. Green vertices are finished (popped or dequeued).
Numbers under vertices. DFS shows two numbers like Levitin's Figure 3.10: the order the vertex was pushed (first reached), then the order it was popped (became a dead end). BFS shows the visit order and the level (distance in edges from the root).
Edges. Solid orange edges are tree edges (they discovered a new vertex). Dashed purple edges are DFS back edges (to an ancestor that is still on the stack). Dashed yellow edges are BFS cross edges (to a vertex already seen, on the same or the next level). Any back or cross edge means the graph has a cycle.
Matrix vs lists. With an adjacency matrix, finding the neighbors of a vertex means reading its whole row of |V| entries, so a traversal costs Θ(|V|²). With adjacency lists you only read the real neighbors, for Θ(|V| + |E|) in total. The "entries read" counter shows the difference.
Try this
- Load the two-component preset and run DFS from a. Check the push order a, c, d, f, b, e and the pop order d, e, b, f, c, a. Then g, h, i, j pushed and j, i, h, g popped: the outer loop restarts once, so the forest has 2 trees.
- Switch to BFS on the same graph. The visit order becomes a, c, d, e, f, b, then g, h, j, i. Every non-tree edge is a cross edge between the same or neighboring levels.
- Load the tree preset. Neither traversal finds a single back or cross edge: that's how DFS and BFS prove a graph is acyclic.
- Toggle adjacency matrix vs lists on the 3 × 3 grid. Entries read: |V|² = 81 vs 2|E| = 24. Same traversal, very different work.
- In ✖ mode, delete the edge a–d from the two-component preset. Which back edge disappears from the DFS forest?