Two ways to explore a graph

The graph is the same. The question changes.

A graph consists of vertices (nodes) and edges (connections). A traversal visits the vertices reachable from a chosen starting point. Breadth-first search and depth-first search both do this, but organize the work differently.

In this lab, edges are undirected: if A connects to B, you can travel either way. Both traversal tools ignore edge weights. Changing a cost will not change their order.

Breadth first: expand the boundary.

BFS keeps a first-in, first-out queue. Discover the starting node, put it in the queue, and repeatedly remove the oldest entry. Add its undiscovered neighbors to the back. Mark nodes when they are discovered so cycles cannot add them repeatedly.

Consider a tree with edges A–B, A–C, B–D, B–E, and C–F. Starting at A and considering B before C gives the order A, B, C, D, E, F. Nodes one edge away appear before nodes two edges away. This is why BFS finds minimum-hop paths in an unweighted graph. Princeton’s BFS reference describes this shortest-path property.

Depth first: follow a branch.

DFS descends through an unvisited neighbor and returns only when that branch has no unexplored neighbor. An explicit stack or recursive calls keep track of the route back. On the same tree, visiting B first can produce A, B, D, E, C, F.

A DFS tree records how the search discovered nodes. Its route to a target need not have the fewest edges. Traversal order also depends on neighbor order; different valid orders do not imply different connectivity. See Princeton’s undirected graph chapter for both methods.

Reading the trace.

The playground shows a node when it is processed. BFS displays queued nodes as the frontier; DFS displays active ancestor calls. The green route after completion is the parent-chain route to your target. For DFS, that is a traversal-tree route, not a promise of shortest distance.

With adjacency lists, either search needs O(V + E) time in the reachable graph and O(V) auxiliary memory. Playback and rendering add their own work. A disconnected graph needs a new starting point in each component to visit every node.