ToolSphere
Back to all articles
student

BFS vs DFS: Graph Traversal Step by Step

2026-11-119 min read

Try it: free Graph Algorithm Visualizer

Trace graph searches, shortest paths and spanning trees

Open →

Graph traversal algorithms systematically visit every vertex reachable from a starting source by following its edges. In introductory computer science curricula like UC Berkeley CS 61B and MIT 6.1210, two fundamental approaches anchor graph theory: Breadth-First Search (BFS) and Depth-First Search (DFS).

While both algorithms explore connected graphs in O(|V| + |E|) time when implemented with adjacency lists, they use contrasting data structures and explore search spaces in fundamentally different orders. BFS expands outward uniformly like ripples on a pond using a FIFO queue, while DFS dives as deeply as possible along a single branch using a LIFO call stack before backtracking.

This guide compares BFS and DFS using the classic directed graph loaded in ToolSphere's graph algorithm visualizer. Every queue transition, call stack state, distance value, and timestamp below was computed by executing the site's tested graph library.

BFS vs DFS at a glance

The choice between BFS and DFS comes down to the structure of your question: do you need the fewest hops to a destination, or do you need to analyze the structural topology, nested components, or cycles of a network?

Feature Breadth-First Search (BFS) Depth-First Search (DFS)
Primary Data Structure FIFO Queue (First-In, First-Out) LIFO Stack or recursion call stack
Exploration Strategy Level by level in concentric frontiers Branch by branch until dead ends, then backtrack
Shortest Path Guarantees shortest path on unweighted graphs (minimum edges) Does not guarantee shortest paths
Time Complexity O(|V| + |E|) with adjacency list O(|V| + |E|) with adjacency list
Auxiliary Space O(|V|) proportional to the maximum breadth O(h) recursion depth (h ≤ |V|; O(log |V|) for balanced trees)
Key Output Metadata Distance d[v] (edge hops from source), predecessor p[v] Discovery time d[v], finish time f[v], tree parent p[v]
Edge Classifications Tree edges and cross edges Tree, back, forward, and cross edges
Primary Applications Shortest path (unweighted), bipartite check, peer-to-peer networks Cycle detection, topological sort, strongly connected components, mazes

The worked graph

Consider a directed graph with 5 vertices (s, t, x, y, z) and 10 directed edges, rooted at source vertex s. This corresponds to the default weighted graph in the visualizer (adapted from CLRS Chapter 24):

Vertices: s, t, x, y, z
Directed edges:
  s → t (weight 10)    y → t (weight 3)
  s → y (weight 5)     y → x (weight 9)
  t → x (weight 1)     y → z (weight 2)
  t → y (weight 2)     z → s (weight 7)
  x → z (weight 4)     z → x (weight 6)

Although edge weights are displayed for algorithms like Dijkstra or Bellman-Ford, BFS and DFS treat every edge as an unweighted connection of length 1. When a vertex has multiple outgoing edges, ties are broken alphabetically by vertex list order (s, t, x, y, z).

Breadth-First Search (BFS) step by step

BFS uses a first-in, first-out (FIFO) queue. When a vertex is dequeued, all its unvisited outgoing neighbors are discovered, marked with their edge distance from s, assigned a predecessor pointer, and appended to the back of the queue.

On this graph, starting at s, BFS discovers vertices in concentric distance layers:

  • Layer 0 (distance 0): s
  • Layer 1 (distance 1): t, y
  • Layer 2 (distance 2): x, z

The complete BFS visiting order is: s → t → y → x → z.

BFS execution trace

Here is the step-by-step state computed by running src/lib/algorithms/graph.ts:

Step Action Queue (front at left) Distances (s, t, x, y, z) Predecessor Tree
1 Initialize s s s:0, t:∞, x:∞, y:∞, z:∞ none
2 Dequeue s empty s:0, t:∞, x:∞, y:∞, z:∞ none
3 Discover t from s t s:0, t:1, x:∞, y:∞, z:∞ s → t
4 Discover y from s t, y s:0, t:1, x:∞, y:1, z:∞ s → t, s → y
5 Dequeue t y s:0, t:1, x:∞, y:1, z:∞ s → t, s → y
6 Discover x from t y, x s:0, t:1, x:2, y:1, z:∞ s → t, t → x, s → y
7 Dequeue y x s:0, t:1, x:2, y:1, z:∞ s → t, t → x, s → y
8 Discover z from y x, z s:0, t:1, x:2, y:1, z:2 s → t, t → x, s → y, y → z
9 Dequeue x z s:0, t:1, x:2, y:1, z:2 s → t, t → x, s → y, y → z
10 Dequeue z empty s:0, t:1, x:2, y:1, z:2 s → t, t → x, s → y, y → z
11 Complete empty s:0, t:1, x:2, y:1, z:2 s → t, t → x, s → y, y → z

Why BFS discovers y before x

At step 2, dequeuing s reveals neighbors t and y. Both are added to the queue at distance 1. Even though t leads to x, vertex y was already enqueued in Layer 1. Because the queue processes in FIFO order, y is dequeued before x can be dequeued.

This ensures BFS always checks every vertex at distance k before visiting any vertex at distance k + 1. The shortest unweighted paths from s are:

  • Path to t: s → t (1 hop)
  • Path to y: s → y (1 hop)
  • Path to x: s → t → x (2 hops)
  • Path to z: s → y → z (2 hops)

Depth-First Search (DFS) step by step

DFS explores as far along each branch as possible before backtracking. It maintains a global clock incremented on every event:

  1. Discovery time d[v]: when vertex v is first encountered and pushed onto the call stack.
  2. Finish time f[v]: when all outgoing edges of v have been examined and v is popped from the stack.

For a graph with |V| vertices, the timestamps range from 1 to 2|V| (here, 1 to 10).

The DFS discovery order is: s → t → x → z → y.

DFS execution trace

Here is the step-by-step state computed by running src/lib/algorithms/graph.ts:

Step Action Call Stack (top at right) Discovered d[v] Finished f[v] Active Vertex
1 Discover s s s:1 none s
2 Discover t s → t s:1, t:2 none t
3 Discover x s → t → x s:1, t:2, x:3 none x
4 Discover z s → t → x → z s:1, t:2, x:3, z:4 none z
5 Finish z s → t → x s:1, t:2, x:3, z:4 z:5 z
6 Finish x s → t s:1, t:2, x:3, z:4 z:5, x:6 x
7 Discover y s → t → y s:1, t:2, x:3, z:4, y:7 z:5, x:6 y
8 Finish y s → t s:1, t:2, x:3, z:4, y:7 z:5, x:6, y:8 y
9 Finish t s s:1, t:2, x:3, z:4, y:7 z:5, x:6, y:8, t:9 t
10 Finish s empty s:1, t:2, x:3, z:4, y:7 z:5, x:6, y:8, t:9, s:10 s
11 Complete empty s:1, t:2, x:3, z:4, y:7 z:5, x:6, y:8, t:9, s:10 none

Final DFS timestamps and parenthesis structure

Every vertex receives an interval [d[v], f[v]]:

s: [1, 10]
t: [2, 9]
x: [3, 6]
z: [4, 5]
y: [7, 8]

According to the Parenthesis Theorem, for any two vertices, their intervals are either completely disjoint or one is strictly nested inside the other. Writing open parentheses for discovery and close parentheses for finish produces a well-formed nested expression:

(s (t (x (z z) x) (y y) t) s)
 1  2  3  4 5  6   7 8  9 10

Notice how z [4, 5] is nested inside x [3, 6], which is nested inside t [2, 9], which is nested inside s [1, 10]. Vertex y [7, 8] is also nested inside t [2, 9], but its interval is completely disjoint from x [3, 6].

Why DFS visits y last

In BFS, y was discovered in step 4 because s → y is a direct edge. In DFS, s chooses neighbor t first. From t, DFS explores x, and from x it explores z.

At z, all outgoing edges (z → s and z → x) lead to vertices already on the stack. Vertex z finishes at time 5. Control backtracks to x, which has no more unvisited edges and finishes at time 6. Control backtracks to t. Only now does t examine its second neighbor, discovering y at time 7.

DFS prioritizes depth over proximity. The path taken from s to y in the DFS tree is s → t → y, completely bypassing the direct edge s → y.

Edge classification in DFS

DFS timestamps categorize every edge in a directed graph into four mutually exclusive types:

Type          Condition on Intervals                     Graph Example
─────────────────────────────────────────────────────────────────────────────
Tree Edge     Edge is followed to discover a new vertex  s → t, t → x, x → z, t → y
Back Edge     Target v is an ancestor on stack:          y → t, z → s, z → x
              d[v] < d[u] < f[u] < f[v]
Forward Edge  Target v is descendant, not a tree edge:   s → y
              d[u] < d[v] < f[v] < f[u]
Cross Edge    Target v finished before u was discovered: y → x, y → z
              d[v] < f[v] < d[u] < f[u]

Detecting cycles with back edges

In directed graphs, a graph has a directed cycle if and only if DFS produces at least one back edge. In our example:

  • Edge y → t points to t (interval [2, 9]), which is currently on the call stack. This reveals the directed cycle: t → y → t.
  • Edge z → s points to ancestor s (interval [1, 10]), revealing the cycle: s → t → x → z → s.
  • Edge z → x points to ancestor x (interval [3, 6]), revealing the cycle: x → z → x.

If a graph has no back edges, it is a Directed Acyclic Graph (DAG), and sorting the vertices in decreasing order of their finish times yields a valid topological sort.

Implementation comparison

Here is how both algorithms are implemented in clean, idiomatic TypeScript or Python.

Breadth-First Search (BFS) implementation

function bfs(adj: Record<string, string[]>, start: string): string[] {
  const visited = new Set<string>([start]);
  const queue: string[] = [start];
  const order: string[] = [];

  while (queue.length > 0) {
    const u = queue.shift()!;
    order.push(u);

    for (const v of adj[u] ?? []) {
      if (!visited.has(v)) {
        visited.add(v); // Mark visited immediately on enqueue!
        queue.push(v);
      }
    }
  }

  return order;
}

[!IMPORTANT]
Always mark a vertex as visited when you enqueue it, not when you dequeue it. If you wait until dequeue, a vertex with multiple incoming edges can be added to the queue multiple times, causing redundant computation and memory exhaustion.

Depth-First Search (DFS) implementation

function dfs(adj: Record<string, string[]>, start: string) {
  const discovered: Record<string, number> = {};
  const finished: Record<string, number> = {};
  const order: string[] = [];
  let time = 0;

  function visit(u: string) {
    discovered[u] = ++time;
    order.push(u);

    for (const v of adj[u] ?? []) {
      if (!discovered[v]) {
        visit(v);
      }
    }

    finished[u] = ++time;
  }

  visit(start);
  return { order, discovered, finished };
}

Common pitfalls to avoid

  1. Using DFS to find shortest paths: DFS returns an arbitrary valid path, not the shortest one. In our worked graph, the path from s to y in the DFS tree is 2 hops (s → t → y), even though the direct edge s → y is 1 hop. Use BFS or Dijkstra for shortest paths.
  2. Confusing tree depth with shortest distance: In DFS, the depth of a vertex in the recursion tree depends on edge ordering and does not reflect minimum distance from the source.
  3. Queue memory in wide graphs: On graphs with high branching factors (like peer-to-peer or social networks), the BFS queue can grow to hold a substantial fraction of all vertices at once (O(|V|)). DFS uses memory proportional only to the current path depth (O(h)), which is often much smaller.
  4. Neglecting disconnected components: If a graph has disconnected vertices or unreachable components, a single BFS or DFS pass from source s will not visit every vertex. Run an outer loop over all vertices in the graph to discover full forests.

Explore the interactive visualizer

You can interactively test and modify this exact graph on the Graph Algorithm Visualizer.

Use the visualizer controls to:

  • Switch between BFS and DFS to inspect the queue or stack side by side.
  • Step through the animation using the Next and Previous buttons.
  • Compare with weighted shortest path algorithms like Dijkstra and Bellman-Ford.
  • Run Prim and Kruskal to construct minimum spanning trees on undirected graphs.

Frequently asked questions

When should I choose BFS over DFS?
Choose BFS when you need the shortest path on an unweighted graph, when exploring nodes close to the source first (such as finding nearby friends in a social network), or when searching shallow solutions in large trees. Choose DFS when you need to detect cycles, compute topological orderings, find strongly connected components, or solve puzzles and mazes where you exhaust branches before backtracking.

Why does BFS guarantee the shortest path on unweighted graphs?
BFS explores vertices in order of increasing distance from the source. It discovers all vertices at distance 1 before any at distance 2, and all vertices at distance k before any at distance k + 1. The first time BFS encounters any vertex, it is guaranteed to have found it via the minimum number of edge hops.

Can BFS or DFS find shortest paths on weighted graphs?
Neither basic BFS nor DFS finds shortest paths when edges have varying weights. BFS treats all edges as having weight 1. If edge weights are non-negative, use Dijkstra's algorithm (which replaces the standard FIFO queue with a min-priority queue). If edge weights can be negative, use the Bellman-Ford algorithm.

What is the difference between discovery time and finish time in DFS?
Discovery time d[v] is the integer counter timestamp recorded when vertex v is first visited and pushed onto the call stack. Finish time f[v] is the timestamp recorded when all edges leaving v have been fully explored and v is popped from the call stack. The interval [d[v], f[v]] captures the active lifetime of v in the search tree.

How does DFS detect cycles in directed versus undirected graphs?
In directed graphs, a cycle exists if and only if DFS encounters a back edge to a vertex currently active on the recursion call stack (a vertex with a discovery time but no finish time). In undirected graphs, a cycle exists if DFS encounters an adjacent vertex that has already been visited and is not the immediate parent of the current vertex.

Why must BFS mark vertices as visited upon enqueue rather than upon dequeue?
If a vertex is marked visited only when it is dequeued, multiple parent vertices can discover that same unvisited neighbor and push redundant copies into the queue. This can cause the queue size and runtime to explode exponentially on dense graphs. Marking on enqueue guarantees every vertex enters the queue at most once.

What are tree edges, back edges, forward edges, and cross edges?
Tree edges are edges in the DFS forest traversed to discover unvisited vertices. Back edges connect a vertex to an ancestor on the active call stack, indicating cycles. Forward edges connect a vertex to a descendant in the DFS tree that was already discovered via another path. Cross edges connect vertices across different branches or trees where the destination vertex was already completed and popped from the stack.

Can BFS be implemented recursively?
While DFS naturally mirrors the recursion call stack, BFS cannot easily be implemented with direct recursion because each recursive call frame operates like a LIFO stack. A recursive BFS requires passing the entire queue level down the recursion chain, which is less efficient and more complex than an iterative queue loop.

What happens if a graph is disconnected or has unreachable components?
A single traversal starting from one source vertex will visit only the vertices in that source's connected component (in undirected graphs) or reachable component (in directed graphs). To traverse the entire graph, wrap the traversal in an outer loop over all vertices in the graph, starting a new search whenever an unvisited vertex is found.

How does DFS compute a topological sort of a directed acyclic graph?
In a directed acyclic graph (DAG), no back edges can exist. As vertices finish exploration in DFS, their finish times reflect dependencies: if there is an edge from u to v, then v finishes before u (f[v] < f[u]). Sorting vertices by decreasing finish time (or prepending each vertex to a linked list upon finishing) produces a valid topological order.

Use the Data Structure Visualizer to trace tree and heap operations. For a related walkthrough, read Master Theorem: 10 Solved Examples.

Looking for other tools?

Explore ToolSphere Homepage →