Two common graph traversals visit every reachable node. BFS expands outward by distance; DFS follows a path deeply before backtracking. Here their frontier is maintained with a queue or a stack.
A simulator showing BFS and DFS visiting order and frontier contents
1. Choose a method, then click a start node (currently A)
2. Run the traversal
Each step removes a frontier node and visits it, or skips it if already visited. Click a graph node before starting to change the start node.
Queue for BFS, stack for DFS
BFS appends newly discovered neighbors to the queue and removes from its front. Nodes one edge away are processed before nodes two edges away, which makes BFS useful for shortest paths in unweighted graphs.
DFS pushes neighbors onto a stack and removes the newest first. It follows a path deeply before backtracking, which is useful for mazes, cycle detection, and topological sorting. Recursive implementations use the call stack instead of an explicit stack.
With adjacency lists, both traversals take O(V + E) time for V vertices and E edges.