Algorithm • hard

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

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)`

Video Explainer

Prefer video learning? This explainer gives a quick visual walkthrough of the core idea before you dive into the detailed sections below.

DFS vs BFS, When to Use Which?

Channel: AlgoMonster

Full video link:

https://www.youtube.com/watch?v=cS-198wtfj0

Depth vs Breadth First Search Visualizer

Compare BFS queue expansion and DFS stack expansion while tracking visited nodes.

Depth vs Breadth First Search VisualizerStep 1 / 3

Start BFS from node A.

Graph

A-[B,C], B-[D], C-[D,E], D-[F], E-[F]

Queue

[A]

Visited

{A}

Rule

Add neighbors only if unvisited.

Core Concepts

Learn the core building blocks and terminology in one place before comparisons, so the mechanics are clear and duplicates are removed.

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.

Putting It All Together

This walkthrough connects the core concepts of Depth vs Breadth First Search (DFS/BFS) into one end-to-end execution flow.

Step 1

Vertex

Entity/node in graph.

Before

Graph nodes: 0..5
Start node: 0
Visited={0}

→

After

Queue=

Visited={0,1,2}

Transition

BFS: dequeue node 0

→Enqueue unvisited neighbors 1,2

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

Step 2

Edge

Connection between vertices.

Before

Queue=

Current level distance=1

→

After

Queue for next level populated
Shortest unweighted distances expand by layers

Transition

Process node 1 then 2

→Enqueue unseen neighbors

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

Step 3

Adjacency list

Compact representation for sparse graphs.

Before

DFS stack=

Need full component exploration

→

After

One path explored to depth
Backtrack when branch ends

Transition

Pop one node

→Push one neighbor branch deeply

Why this step 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.

Step 4

Visited set

Tracks explored nodes to prevent loops.

Before

Potential cycle edge found
Need loop-safe traversal

→

After

No infinite traversal loops
Complexity remains O(V+E)

Transition

Check visited before pushing

→Skip already visited nodes

Why this step 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.

How It Compares

vs Tree traversal

When to choose this: Choose graph traversal when cycles or arbitrary connectivity exist.

Tradeoff: Tree traversal is simpler because no cycles by definition.

vs Dijkstra

When to choose this: Choose plain BFS/DFS for unweighted reachability/connectivity.

Tradeoff: Weighted shortest paths need Dijkstra or variants.

vs Union-Find

When to choose this: Choose traversal when you need explicit paths/order exploration.

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

Real-World Stories and Company Examples

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.

Implementation Guide

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)

Language

BFS and DFS traversal from source

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
}

Common Problems and Failure Modes

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.

Tips and Tricks

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.

When to Use

Use these signals to decide if this data structure/algorithm is the right fit before implementation.

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 (including 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.

LeetCode Progression (Easy to Hard)

Back to DSA Guide Catalog

#	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)`