Depth vs Breadth First Search (DFS/BFS) Complete Guide

Algorithm • hard

Depth-first search (DFS) and breadth-first search (BFS) are the two foundational graph traversal strategies.

BFS expands in layers from a source node, while DFS goes deep along one branch before backtracking.

The most important correctness rule for both is visited-state tracking to avoid revisiting cycles.

Typical Complexity Baseline

Metric	Value
Complexity Note 1	`O(V + E)`

See It

Concept Diagram

A small animated SVG that illustrates the core idea the moving parts you need to keep in your head when you read the rest of the guide.

Graph traversal visit every reachable node once

Visited set prevents revisits. Order depends on whether you queue (BFS) or stack (DFS).

Step 1/9BFS from A. Visit A.

Speed

Watch First

Video Explainer

A quick visual walkthrough before the detailed sections pick the format that helps you learn fastest.

DFS vs BFS, When to Use Which?

Channel: AlgoMonster

Watch on YouTube →

Mechanics

Core Concepts

The building blocks and terminology you need before everything else clicks. Skim or deep-read.

Vertex

What it is Entity/node in graph.

Why it matters Vertex is a required building block for understanding how Depth vs Breadth First Search (DFS/BFS) stays correct and performant on large inputs.

Edge

What it is Connection between vertices.

Why it matters Edge is a required building block for understanding how Depth vs Breadth First Search (DFS/BFS) stays correct and performant on large inputs.

Adjacency list

What it is Compact representation for sparse graphs.

Why it matters Adjacency list is a required building block for understanding how Depth vs Breadth First Search (DFS/BFS) stays correct and performant on large inputs.

Visited set

What it is Tracks explored nodes to prevent loops.

Why it matters Visited set is a required building block for understanding how Depth vs Breadth First Search (DFS/BFS) stays correct and performant on large inputs.

Traversal frontier

What it is Stack/queue holding next nodes to process.

Why it matters Traversal frontier is a required building block for understanding how Depth vs Breadth First Search (DFS/BFS) stays correct and performant on large inputs.

Connected component

What it is Maximal set of nodes connected by paths.

Why it matters Maximal set of nodes connected by paths. In Depth vs Breadth First Search (DFS/BFS), this definition helps you reason about correctness and complexity when inputs scale.

Directed graph

What it is Edges have direction.

Why it matters Edges have direction. In Depth vs Breadth First Search (DFS/BFS), this definition helps you reason about correctness and complexity when inputs scale.

Undirected graph

What it is Edges are bidirectional.

Why it matters Edges are bidirectional. In Depth vs Breadth First Search (DFS/BFS), this definition helps you reason about correctness and complexity when inputs scale.

BFS layer

What it is Nodes reachable in equal number of edges from source.

Why it matters Nodes reachable in equal number of edges from source. In Depth vs Breadth First Search (DFS/BFS), this definition helps you reason about correctness and complexity when inputs scale.

DFS tree

What it is Traversal tree induced by depth-first exploration.

Why it matters Traversal tree induced by depth-first exploration. In Depth vs Breadth First Search (DFS/BFS), this definition helps you reason about correctness and complexity when inputs scale.

Walkthrough

Putting It All Together

Every frame of the concept diagram, laid out top-to-bottom so you can scroll through the algorithm at your own pace.

Step 1/9

BFS from A. Visit A.

Step 2/9

Visit B.

Step 3/9

Visit C.

Step 4/9

Visit D.

Step 5/9

Visit E.

Step 6/9

Visit H.

Step 7/9

Visit F.

Step 8/9

Visit G.

Step 9/9

Visit I.

Tradeoffs

How It Compares

When this technique wins, when it loses, and what to reach for instead.

vs. Tree traversal

Choose this when Choose graph traversal when cycles or arbitrary connectivity exist.

Tradeoff Tree traversal is simpler because no cycles by definition.

vs. Dijkstra

Choose this when Choose plain BFS/DFS for unweighted reachability/connectivity.

Tradeoff Weighted shortest paths need Dijkstra or variants.

vs. Union-Find

Choose this when Choose traversal when you need explicit paths/order exploration.

Tradeoff Union-Find is faster for repeated connectivity queries after unions.

In Production

Real-World Stories

Where this shows up at real companies and what the on-call engineer learned the hard way.

People-you-may-know and network analysis features depend on graph exploration patterns.

Takeaway Traversal logic powers social graph product features.

Airbnb

City, route, and region recommendation tasks rely on graph-like connectivity models.

Takeaway Graph traversals support practical recommendation pathing.

GitHub

Dependency graphs and CI relationship analysis use traversal to find impact radius.

Takeaway Traversal is key for change impact tooling.

Code

Implementation

A clean reference implementation in TypeScript, Python, and Go. Switch languages with the toggle.

Implement both traversals from scratch with explicit queue/stack buffers and boolean visited arrays so you can see exactly how frontier expansion differs.

Complexity: Time O(V+E), Space O(V) for both BFS and DFS (iterative)

BFS and DFS traversal from source

Language

function bfsOrder(adjacencyByNode: number[][], startNode: number): number[] {
  const visitedNodes = new Array<boolean>(adjacencyByNode.length).fill(false)
  const queueBuffer = new Array<number>(Math.max(1, adjacencyByNode.length * 2)).fill(0)
  let queueHeadIndex = 0
  let queueTailIndex = 0
  const traversalOrder: number[] = []

  visitedNodes[startNode] = true
  queueBuffer[queueTailIndex] = startNode
  queueTailIndex += 1

  while (queueHeadIndex < queueTailIndex) {
    const currentNode = queueBuffer[queueHeadIndex]
    queueHeadIndex += 1
    traversalOrder.push(currentNode)

    const neighborNodes = adjacencyByNode[currentNode] ?? []
    for (const neighborNode of neighborNodes) {
      if (visitedNodes[neighborNode]) {
        continue
      }

      visitedNodes[neighborNode] = true
      queueBuffer[queueTailIndex] = neighborNode
      queueTailIndex += 1
    }
  }

  return traversalOrder
}

function dfsOrder(adjacencyByNode: number[][], startNode: number): number[] {
  const visitedNodes = new Array<boolean>(adjacencyByNode.length).fill(false)
  const nodeStack: number[] = [startNode]
  const traversalOrder: number[] = []

  while (nodeStack.length > 0) {
    const currentNode = nodeStack.pop()!
    if (visitedNodes[currentNode]) {
      continue
    }

    visitedNodes[currentNode] = true
    traversalOrder.push(currentNode)

    const neighborNodes = adjacencyByNode[currentNode] ?? []
    for (let neighborIndex = neighborNodes.length - 1; neighborIndex >= 0; neighborIndex -= 1) {
      const neighborNode = neighborNodes[neighborIndex]
      if (!visitedNodes[neighborNode]) {
        nodeStack.push(neighborNode)
      }
    }
  }

  return traversalOrder
}

Watch Out

Common Problems and Failure Modes

The bugs and edge cases that bite engineers most often. Skim before you ship.

Forgetting visited tracking and reprocessing nodes indefinitely.
Choosing adjacency matrix for sparse graphs and wasting memory.
Confusing BFS shortest path guarantee with weighted graphs.
Not resetting state across disconnected components.
Recursion depth overflows in deep DFS without iterative fallback.

Pro Tips

Tips and Tricks

Small habits that pay off every time you reach for this pattern.

Model graph clearly first: directed/undirected, weighted/unweighted.
Visited tracking is non-negotiable when cycles are possible.
BFS is shortest path for unweighted graphs; DFS is exploration-oriented.
Separate graph-building code from traversal code for easier debugging.

Pattern Recognition

When to Use

Concrete signals that tell you this is the right pattern both at work and on LeetCode.

Real-system usage signals

Models real systems: dependencies, networks, roads, social relationships.
Supports connectivity, component counting, path existence, and layer-based distances.
Works with sparse and dense graph representations.

LeetCode-specific tips (pattern-identification signals)

Identification signal: entities and relationships form general connections, not strict tree hierarchy.
Identification signal: connected components, reachability, or path existence are asked explicitly.
If cycles are possible, include visited-tracking and pick BFS/DFS based on shortest-path vs exploration needs.
For Depth vs Breadth First Search (DFS/BFS) questions, start by naming the core invariant before writing code.
Use the constraint section to set time/space target first, then pick the data structure/algorithm.
Solve one tiny example by hand and map each transition to your variables before implementing.
Run adversarial cases: empty input, duplicates, max-size input, and sorted/reverse patterns when relevant.
During interviews, explain why your approach is the right pattern for this prompt, not just why the code works.

Practice

LeetCode Progression

A curated easy-to-hard problem ladder. Each one reinforces a specific aspect of the pattern.

#	Problem	Difficulty	Typical Complexity
1	Find if Path Exists in Graph	Easy	`O(V+E)`
2	Number of Provinces	Medium	`O(V^2)`
3	Number of Islands	Medium	`O(m*n)`
4	Clone Graph	Medium	`O(V+E)`
5	Course Schedule	Medium	`O(V+E)`
6	Pacific Atlantic Water Flow	Medium	`O(m*n)`
7	Graph Valid Tree	Medium	`O(V+E)`
8	Word Ladder	Hard	`O(V+E)`
9	Alien Dictionary	Hard	`O(V+E)`
10	Critical Connections in a Network	Hard	`O(V+E)`