Data Structures & AlgorithmsIntroduction to Graph Algorithms

Introduction to Graph Algorithms

LevelIntermediate

Duration60 mins

TopicIntroduction to Graph Algorithms

2 / 5

Traversal — BFS and DFS

The Two Ways to Explore a Graph

Imagine you're exploring a cave system with multiple branching tunnels. You have two fundamental strategies:

Explore level by level: Check all tunnels at your current depth before going deeper. This ensures you find the nearest exit first.
Explore as deep as possible: Follow one tunnel until you hit a dead end, then backtrack and try another. This efficiently explores the full extent of each path.

These two strategies map directly to the two most fundamental graph algorithms: Breadth-First Search (BFS) and Depth-First Search (DFS). Together, they form the foundation upon which most graph algorithms are built.

Understanding these traversals deeply—not just their mechanics, but their characteristic behaviors and ideal use cases—is essential for mastering graph algorithms.

What You Will Learn

By the end of this page, you will understand the conceptual models behind BFS and DFS, their distinctive exploration patterns, why BFS finds shortest paths in unweighted graphs, when to choose each algorithm, and how they serve as building blocks for more advanced graph algorithms.

The Core Distinction: Queue vs Stack

At the heart of BFS and DFS lies a simple but profound difference: the data structure that holds vertices waiting to be explored.

BFS uses a Queue (FIFO — First In, First Out)

Vertices discovered first are explored first. This creates a "wavefront" effect where exploration spreads outward uniformly from the starting vertex. Vertices at distance 1 are explored before vertices at distance 2, which are explored before distance 3, and so on.

DFS uses a Stack (LIFO — Last In, First Out)

Vertices discovered most recently are explored first. This creates a "diving deep" effect where the algorithm ventures as far as possible along one path before backtracking. The natural recursion in programming provides an implicit stack via the call stack.

Breadth-First Search (BFS)

•Data Structure: Queue (FIFO)
•Exploration Pattern: Level by level, outward wave
•Memory Usage: O(w) where w is maximum "width" of graph
•Shortest Path: YES — finds shortest path by edge count
•Complete: YES — guaranteed to find a path if one exists
•Best For: Shortest paths, finding closest nodes, level-order tasks

Depth-First Search (DFS)

•Data Structure: Stack (LIFO) or recursion
•Exploration Pattern: Deep dive, then backtrack
•Memory Usage: O(h) where h is maximum "depth" of exploration
•Shortest Path: NO — may find longer paths first
•Complete: YES (with cycle detection) — explores all reachable nodes
•Best For: Cycle detection, topological sort, path existence, backtracking

The Unified Template

Both BFS and DFS can be written with the same template—only the data structure changes. Replace the queue with a stack, and BFS becomes DFS. This insight reveals that the "intelligence" isn't in complex logic but in the order of exploration dictated by the data structure.

Breadth-First Search: The Level-by-Level Explorer

BFS explores a graph like ripples spreading from a stone dropped in water. From the starting vertex, it first visits all immediate neighbors (distance 1), then all vertices reachable in exactly 2 edges, then 3, and so on.

Why BFS Finds Shortest Paths (Unweighted)

This level-by-level property is why BFS guarantees shortest paths in unweighted graphs. When BFS first reaches a vertex, it does so via a shortest path. Why? Because BFS explores ALL paths of length k before ANY path of length k+1. If there were a shorter path to vertex v, BFS would have found it in an earlier level.

The BFS Invariant:

When a vertex is dequeued, its distance from the source is finalized and optimal (for unweighted edges).

This invariant is the mathematical foundation of BFS's shortest-path guarantee.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
interface Graph {
    neighbors(vertex: number): number[];
}
 
function bfs(graph: Graph, start: number, numVertices: number): Map<number, number> {
    /**
     * BFS traversal that computes shortest distances from start vertex.
     * 
     * Time Complexity: O(V + E)
     * Space Complexity: O(V) for the queue and distance map
     * 
     * @returns Map from vertex to shortest distance from start
     */
    const distances = new Map<number, number>();
    const queue: number[] = [];
    
    // Initialize: start vertex has distance 0
    distances.set(start, 0);
    queue.push(start);
    
    while (queue.length > 0) {
        const current = queue.shift()!; // Dequeue (FIFO)
        const currentDist = distances.get(current)!;
        
        // Explore all neighbors
        for (const neighbor of graph.neighbors(current)) {
            // Only process unvisited vertices
            if (!distances.has(neighbor)) {
                // Distance to neighbor = current distance + 1
                distances.set(neighbor, currentDist + 1);
                queue.push(neighbor);
            }
        }
    }
    
    return distances;
}
 
// Example: Finding shortest path in a social network
// 6 degrees of separation between any two people
function degreesOfSeparation(
    graph: Graph, 
    person1: number, 
    person2: number
): number {
    const distances = bfs(graph, person1, 0);
    return distances.get(person2) ?? -1; // -1 if not connected
}

Visualizing BFS Execution:

Consider this graph with start vertex A:

       A
      /|\
     B C D
    /|   |
   E F   G

BFS Execution:

Queue: [A] → Process A, add neighbors → Queue: [B, C, D]
Queue: [B, C, D] → Process B, add neighbors → Queue: [C, D, E, F]
Queue: [C, D, E, F] → Process C (no new neighbors) → Queue: [D, E, F]
Queue: [D, E, F] → Process D, add neighbors → Queue: [E, F, G]
Process E, F, G (no new neighbors) → Done

Discovery Order: A → B → C → D → E → F → G By Level: Level 0: {A}, Level 1: {B, C, D}, Level 2: {E, F, G}

Notice how vertices are discovered level by level, ensuring shortest-path distances.

Depth-First Search: The Deep Diver

DFS explores a graph like a maze-solver who always turns left (or follows some consistent rule) and backtracks only when hitting a dead end. It follows each path to its deepest point before exploring alternatives.

The Recursive Nature of DFS

DFS has a natural recursive structure: "Visit a vertex, then recursively visit all its unvisited neighbors." This elegant formulation makes DFS ideal for problems with recursive structure—trees, backtracking, and divide-and-conquer scenarios.

DFS Variants: Pre-order, Post-order, and In-order

The order in which we "process" versus "recurse" matters:

Pre-order: Process vertex, THEN recurse to children (used for copying, prefix traversal)
Post-order: Recurse to children, THEN process vertex (used for topological sort, tree deletion)
In-order: For binary trees—left, process, right (used for BST sorted traversal)

For general graphs, pre-order and post-order (discovery and finish times) are particularly important.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
interface Graph {
    neighbors(vertex: number): number[];
}
 
// Recursive DFS with discovery and finish times
function dfsRecursive(
    graph: Graph, 
    start: number
): { discoveryTime: Map<number, number>; finishTime: Map<number, number> } {
    const discoveryTime = new Map<number, number>();
    const finishTime = new Map<number, number>();
    let time = 0;
    
    function dfs(vertex: number): void {
        // Discovery: first time we see this vertex
        discoveryTime.set(vertex, time++);
        
        // Explore all neighbors
        for (const neighbor of graph.neighbors(vertex)) {
            if (!discoveryTime.has(neighbor)) {
                dfs(neighbor); // Recurse (implicit stack)
            }
        }
        
        // Finish: all descendants have been explored
        finishTime.set(vertex, time++);
    }
    
    dfs(start);
    return { discoveryTime, finishTime };
}
 
// Iterative DFS with explicit stack
function dfsIterative(graph: Graph, start: number): number[] {
    const visited = new Set<number>();
    const result: number[] = [];
    const stack: number[] = [start];
    
    while (stack.length > 0) {
        const current = stack.pop()!; // Pop (LIFO)
        
        if (visited.has(current)) continue; // Skip if already visited
        
        visited.add(current);
        result.push(current); // Pre-order processing
        
        // Push neighbors to stack
        // Reverse order to match recursive DFS order (optional)
        const neighbors = graph.neighbors(current);
        for (let i = neighbors.length - 1; i >= 0; i--) {
            if (!visited.has(neighbors[i])) {
                stack.push(neighbors[i]);
            }
        }
    }
    
    return result;
}

Visualizing DFS Execution:

Same graph, same start vertex A:

       A
      /|\
     B C D
    /|   |
   E F   G

DFS Execution (exploring leftmost first):

Stack: [A] → Pop A, push neighbors → Stack: [D, C, B]
Stack: [D, C, B] → Pop B, push neighbors → Stack: [D, C, F, E]
Stack: [D, C, F, E] → Pop E (no unvisited neighbors) → Stack: [D, C, F]
Stack: [D, C, F] → Pop F (no unvisited neighbors) → Stack: [D, C]
Stack: [D, C] → Pop C (no unvisited neighbors) → Stack: [D]
Stack: [D] → Pop D, push neighbors → Stack: [G]
Stack: [G] → Pop G → Done

Discovery Order: A → B → E → F → C → D → G

Notice the "deep dive" pattern: A → B → E, backtrack, F, backtrack, C, backtrack, D → G.

DFS Tree and Edge Classification:

DFS naturally produces a spanning tree (or forest). Edges in the original graph can be classified:

Tree edges: Edges in the DFS tree
Back edges: Edges to ancestors (indicate cycles!)
Forward edges: Edges to descendants (in directed graphs)
Cross edges: Edges to non-ancestors/descendants (in directed graphs)

Back Edges and Cycle Detection

A back edge (edge to an ancestor in the DFS tree) indicates a cycle. This is the foundation of DFS-based cycle detection: if during DFS you encounter an edge to a vertex that's "in progress" (visited but not finished), you've found a cycle. This is why DFS is the preferred algorithm for cycle detection.

When to Use BFS vs DFS

Choosing between BFS and DFS isn't arbitrary—each has characteristics that make it ideal for specific problem types. Here's a comprehensive decision guide:

Use BFS When:

Finding shortest paths (unweighted): BFS's level-by-level exploration guarantees the first path found is the shortest.
Finding the closest/nearest: "Find the nearest hospital," "Find closest matching node"—BFS explores by distance.
Level-order processing: When you need to process nodes level by level (e.g., binary tree level-order traversal).
Web crawling for shallow content: Discovering pages within k links of the homepage.
Social network distance: "Degrees of separation" problems.

Use DFS When:

Cycle detection: DFS's "in-progress" state naturally reveals back edges (cycles).
Topological sorting: DFS finish times give topological order for DAGs.
Path finding (any path, not shortest): DFS finds A path; if you just need existence, DFS is fine.
Backtracking problems: Sudoku, N-Queens, maze solving—DFS's recursive structure matches backtracking.
Connected components / Strongly connected components: DFS efficiently partitions graphs.
Deep exploration preferred: When solutions are "deep" in the search space (e.g., game trees).

BFS vs DFS Decision Matrix
Scenario	BFS	DFS	Why
Shortest path (unweighted)	✓ Optimal	✗ Suboptimal	BFS explores by distance
Shortest path (weighted)	✗ Use Dijkstra	✗ Use Dijkstra	Neither handles weights correctly
Cycle detection	✓ Possible	✓ Natural fit	DFS back edges indicate cycles
Topological sort	✓ Kahn's algorithm	✓ Using finish times	Both work; DFS is often simpler
Finding any path	✓ Works	✓ Works	DFS often faster due to less memory
All paths between two nodes	✓ Works	✓ Natural fit	DFS backtracking structure suits this
Spanning tree	✓ BFS tree	✓ DFS tree	Both produce valid spanning trees
Bipartite check	✓ With 2-coloring	✓ With 2-coloring	Both work equally well
Memory-constrained	✗ Wide frontiers costly	✓ Depth-limited	DFS stack is often smaller

Memory Trade-off

In graphs shaped like wide, shallow trees, BFS can require O(V) memory for the frontier (all nodes at one level). In deep, narrow graphs, DFS's stack is more economical. Consider graph shape when memory is constrained.

Classic Applications of BFS and DFS

Let's examine specific problems where BFS and DFS shine, understanding why each algorithm is the right choice:

Application 1: Shortest Path in a Maze (BFS)

Given a grid where 0 is passable and 1 is a wall, find the shortest path from top-left to bottom-right.

Why BFS? Each cell-to-cell move has equal cost (1 step). BFS explores all cells at distance k before any at distance k+1, guaranteeing when we reach the destination, it's via the shortest path.

Application 2: Detecting Cycles in a Directed Graph (DFS)

Determine if a directed graph contains any cycles.

Why DFS? We track three states for each vertex: unvisited, in-progress (on current path), and completed. If we encounter an in-progress vertex, we've found a back edge—a cycle. BFS doesn't naturally track "currently exploring this path" state.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
enum Color {
    WHITE,  // Unvisited
    GRAY,   // In progress (on current DFS path)
    BLACK   // Completed (fully explored)
}
 
function hasCycle(graph: Map<number, number[]>, numVertices: number): boolean {
    const color = new Array(numVertices).fill(Color.WHITE);
    
    function dfs(vertex: number): boolean {
        color[vertex] = Color.GRAY; // Mark as in-progress
        
        for (const neighbor of graph.get(vertex) || []) {
            if (color[neighbor] === Color.GRAY) {
                // Back edge found! Neighbor is on current path = cycle
                return true;
            }
            if (color[neighbor] === Color.WHITE) {
                if (dfs(neighbor)) return true; // Cycle found deeper
            }
        }
        
        color[vertex] = Color.BLACK; // Fully explored
        return false;
    }
    
    // Check all vertices (graph may be disconnected)
    for (let v = 0; v < numVertices; v++) {
        if (color[v] === Color.WHITE) {
            if (dfs(v)) return true;
        }
    }
    
    return false;
}

Application 3: Connected Components (DFS or BFS)

Find all connected components in an undirected graph.

Why Either Works? Both fully explore all reachable vertices from a starting point. Run traversal from each unvisited vertex; each run discovers one component.

function findConnectedComponents(graph: Graph, numVertices: number): number[][] {
    const visited = new Set<number>();
    const components: number[][] = [];
    
    for (let v = 0; v < numVertices; v++) {
        if (!visited.has(v)) {
            const component: number[] = [];
            // DFS to find all vertices in this component
            dfs(graph, v, visited, component);
            components.push(component);
        }
    }
    
    return components;
}

Application 4: Topological Sort (DFS)

Order vertices of a DAG so that for every edge (u, v), u comes before v.

Why DFS? The DFS finish order (reversed) gives topological order. When we finish a vertex, all its dependencies have finished—so it should come after them. Reversing means it comes before vertices that depend on it.

Topological Sort Intuition

Think of finishing in DFS as "I've explored everything reachable from here." A vertex finishes after all its reachable vertices finish. So vertices with no dependencies (the "last" in dependency order) finish first. Reversing gives us dependency order—prerequisites before dependents.

Time and Space Complexity Analysis

Both BFS and DFS have the same asymptotic complexity, but understanding the details is crucial:

Time Complexity: O(V + E)

Each vertex is visited exactly once: O(V)
Each edge is examined exactly once (twice for undirected, counted as once per direction): O(E)
Total: O(V + E)

This is optimal—you can't do better than looking at each vertex and edge once.

Space Complexity: O(V)

Visited set/array: O(V)
Queue (BFS) or Stack (DFS): O(V) in the worst case
- BFS worst case: Complete graph level—all V-1 neighbors in queue
- DFS worst case: Path graph—all V vertices on stack

In Practice:

The actual space usage depends on graph structure:

Graph Shape	BFS Queue Size	DFS Stack Size
Complete graph K_n	O(n) (all neighbors at once)	O(n) (path through all)
Balanced binary tree	O(n/2) (widest level)	O(log n) (height)
Long path graph	O(1) (one neighbor at a time)	O(n) (entire path)
Wide, shallow DAG	O(width) (could be O(n))	O(depth) (could be O(1))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
// IMPORTANT: JavaScript array.shift() is O(n), not O(1)!
// For performance-critical BFS, use a proper queue implementation.
 
class EfficientQueue<T> {
    private items: T[] = [];
    private head = 0;
    
    enqueue(item: T): void {
        this.items.push(item);
    }
    
    dequeue(): T | undefined {
        if (this.head >= this.items.length) return undefined;
        const item = this.items[this.head];
        this.head++;
        // Periodically compact to avoid memory leak
        if (this.head > 1000 && this.head > this.items.length / 2) {
            this.items = this.items.slice(this.head);
            this.head = 0;
        }
        return item;
    }
    
    isEmpty(): boolean {
        return this.head >= this.items.length;
    }
}
 
// BFS with efficient queue
function bfsEfficient(graph: Graph, start: number): number[] {
    const visited = new Set<number>([start]);
    const result: number[] = [];
    const queue = new EfficientQueue<number>();
    queue.enqueue(start);
    
    while (!queue.isEmpty()) {
        const current = queue.dequeue()!;
        result.push(current);
        
        for (const neighbor of graph.neighbors(current)) {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue.enqueue(neighbor);
            }
        }
    }
    
    return result;
}

Watch for Hidden Quadratic Behavior

Using array.shift() in JavaScript/TypeScript for BFS turns O(V + E) into O(V² + E) because shift() is O(V). Always use a proper queue with O(1) dequeue for large graphs. Similarly, ensure your adjacency list access is O(1) or O(degree), not O(V).

Building Blocks for Advanced Algorithms

BFS and DFS aren't just algorithms—they're building blocks upon which more sophisticated algorithms are constructed:

BFS → Dijkstra's Algorithm

Dijkstra's algorithm is "BFS with a priority queue." Where BFS uses a simple queue and treats all edges as equal, Dijkstra uses a priority queue to always process the vertex with minimum cumulative distance. The structure is nearly identical:

BFS:     while queue not empty: process min-discovery-time vertex
Dijkstra: while pq not empty:   process min-distance vertex

DFS → Topological Sort

The DFS finish order, reversed, gives topological order. This is because when we finish a vertex, all vertices reachable from it have already finished—meaning they should come after it in dependency order.

DFS → Strongly Connected Components (Kosaraju/Tarjan)

Both Kosaraju's and Tarjan's SCC algorithms use DFS. Kosaraju runs DFS twice (once on the graph, once on the reversed graph). Tarjan uses DFS with lowlink values. Both exploit DFS's tree structure and finish times.

BFS → Bipartite Checking

A graph is bipartite if we can 2-color it (no adjacent vertices share a color). BFS naturally handles this: alternate colors at each level. If we ever try to color a vertex with a color it already has, the graph isn't bipartite.

From Traversal to Advanced Algorithm
Base Algorithm	Extension	Key Modification
BFS	Dijkstra's Shortest Path	Queue → Priority Queue; add edge weights
BFS	0-1 BFS	Use deque; 0-weight edges go to front
BFS	Multi-source BFS	Initialize queue with multiple start vertices
BFS	Bidirectional BFS	BFS from both source and target; meet in middle
DFS	Topological Sort	Reverse DFS finish order
DFS	Cycle Detection	Track in-progress vertices; back edge = cycle
DFS	Articulation Points	Track discovery times and lowlinks
DFS	Tarjan's SCC	Lowlink values identify strongly connected components
DFS	Euler Path/Circuit	DFS with edge removal

Master the Fundamentals

Once you deeply understand BFS and DFS—their invariants, their data structures, their exploration patterns—advanced algorithms become natural extensions. Dijkstra is just 'weighted BFS.' Tarjan's SCC is just 'DFS with clever bookkeeping.' The fundamentals unlock everything.

Summary: Mastering Graph Traversal

BFS and DFS are the two fundamental ways to systematically explore a graph. Understanding their differences, strengths, and applications is essential for graph algorithm mastery.

Key Takeaways

•The core distinction is the data structure: BFS uses a queue (FIFO), DFS uses a stack (LIFO/recursion).
•BFS explores level-by-level: This guarantees shortest paths in unweighted graphs.
•DFS explores depth-first: This naturally supports cycle detection, topological sort, and backtracking.
•Both have O(V + E) time complexity: Optimal for exploring every vertex and edge once.
•Space complexity depends on graph shape: BFS = O(width), DFS = O(depth).
•Choose based on problem requirements: Shortest path → BFS. Cycle detection, topological sort → DFS.
•They're building blocks: Most advanced graph algorithms extend BFS or DFS.

What's Next:

With traversal algorithms understood, the next page explores shortest path algorithms—Dijkstra and Bellman-Ford. You'll see how Dijkstra extends BFS to handle weighted graphs, and how Bellman-Ford handles the challenging case of negative edge weights.

Page Complete

You now understand the two fundamental graph traversal algorithms. BFS and DFS form the foundation of graph algorithmics—nearly every graph algorithm you'll encounter is built upon or inspired by these traversal patterns. Next, we'll explore how to find shortest paths in weighted graphs.

2 / 5

Loading learning content...

Data Structures & AlgorithmsIntroduction to Graph Algorithms

Introduction to Graph Algorithms

LevelIntermediate

Duration60 mins

TopicIntroduction to Graph Algorithms

2 / 5

Traversal — BFS and DFS

The Two Ways to Explore a Graph

Imagine you're exploring a cave system with multiple branching tunnels. You have two fundamental strategies:

Explore level by level: Check all tunnels at your current depth before going deeper. This ensures you find the nearest exit first.
Explore as deep as possible: Follow one tunnel until you hit a dead end, then backtrack and try another. This efficiently explores the full extent of each path.

Understanding these traversals deeply—not just their mechanics, but their characteristic behaviors and ideal use cases—is essential for mastering graph algorithms.

What You Will Learn

The Core Distinction: Queue vs Stack

At the heart of BFS and DFS lies a simple but profound difference: the data structure that holds vertices waiting to be explored.

BFS uses a Queue (FIFO — First In, First Out)

DFS uses a Stack (LIFO — Last In, First Out)

Breadth-First Search (BFS)

•Data Structure: Queue (FIFO)
•Exploration Pattern: Level by level, outward wave
•Memory Usage: O(w) where w is maximum "width" of graph
•Shortest Path: YES — finds shortest path by edge count
•Complete: YES — guaranteed to find a path if one exists
•Best For: Shortest paths, finding closest nodes, level-order tasks

Depth-First Search (DFS)

•Data Structure: Stack (LIFO) or recursion
•Exploration Pattern: Deep dive, then backtrack
•Memory Usage: O(h) where h is maximum "depth" of exploration
•Shortest Path: NO — may find longer paths first
•Complete: YES (with cycle detection) — explores all reachable nodes
•Best For: Cycle detection, topological sort, path existence, backtracking

The Unified Template

Breadth-First Search: The Level-by-Level Explorer

Why BFS Finds Shortest Paths (Unweighted)

The BFS Invariant:

When a vertex is dequeued, its distance from the source is finalized and optimal (for unweighted edges).

This invariant is the mathematical foundation of BFS's shortest-path guarantee.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
interface Graph {
    neighbors(vertex: number): number[];
}
 
function bfs(graph: Graph, start: number, numVertices: number): Map<number, number> {
    /**
     * BFS traversal that computes shortest distances from start vertex.
     * 
     * Time Complexity: O(V + E)
     * Space Complexity: O(V) for the queue and distance map
     * 
     * @returns Map from vertex to shortest distance from start
     */
    const distances = new Map<number, number>();
    const queue: number[] = [];
    
    // Initialize: start vertex has distance 0
    distances.set(start, 0);
    queue.push(start);
    
    while (queue.length > 0) {
        const current = queue.shift()!; // Dequeue (FIFO)
        const currentDist = distances.get(current)!;
        
        // Explore all neighbors
        for (const neighbor of graph.neighbors(current)) {
            // Only process unvisited vertices
            if (!distances.has(neighbor)) {
                // Distance to neighbor = current distance + 1
                distances.set(neighbor, currentDist + 1);
                queue.push(neighbor);
            }
        }
    }
    
    return distances;
}
 
// Example: Finding shortest path in a social network
// 6 degrees of separation between any two people
function degreesOfSeparation(
    graph: Graph, 
    person1: number, 
    person2: number
): number {
    const distances = bfs(graph, person1, 0);
    return distances.get(person2) ?? -1; // -1 if not connected
}

Visualizing BFS Execution:

Consider this graph with start vertex A:

       A
      /|\
     B C D
    /|   |
   E F   G

BFS Execution:

Queue: [A] → Process A, add neighbors → Queue: [B, C, D]
Queue: [B, C, D] → Process B, add neighbors → Queue: [C, D, E, F]
Queue: [C, D, E, F] → Process C (no new neighbors) → Queue: [D, E, F]
Queue: [D, E, F] → Process D, add neighbors → Queue: [E, F, G]
Process E, F, G (no new neighbors) → Done

Discovery Order: A → B → C → D → E → F → G By Level: Level 0: {A}, Level 1: {B, C, D}, Level 2: {E, F, G}

Notice how vertices are discovered level by level, ensuring shortest-path distances.

Depth-First Search: The Deep Diver

The Recursive Nature of DFS

DFS Variants: Pre-order, Post-order, and In-order

The order in which we "process" versus "recurse" matters:

Pre-order: Process vertex, THEN recurse to children (used for copying, prefix traversal)
Post-order: Recurse to children, THEN process vertex (used for topological sort, tree deletion)
In-order: For binary trees—left, process, right (used for BST sorted traversal)

For general graphs, pre-order and post-order (discovery and finish times) are particularly important.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
interface Graph {
    neighbors(vertex: number): number[];
}
 
// Recursive DFS with discovery and finish times
function dfsRecursive(
    graph: Graph, 
    start: number
): { discoveryTime: Map<number, number>; finishTime: Map<number, number> } {
    const discoveryTime = new Map<number, number>();
    const finishTime = new Map<number, number>();
    let time = 0;
    
    function dfs(vertex: number): void {
        // Discovery: first time we see this vertex
        discoveryTime.set(vertex, time++);
        
        // Explore all neighbors
        for (const neighbor of graph.neighbors(vertex)) {
            if (!discoveryTime.has(neighbor)) {
                dfs(neighbor); // Recurse (implicit stack)
            }
        }
        
        // Finish: all descendants have been explored
        finishTime.set(vertex, time++);
    }
    
    dfs(start);
    return { discoveryTime, finishTime };
}
 
// Iterative DFS with explicit stack
function dfsIterative(graph: Graph, start: number): number[] {
    const visited = new Set<number>();
    const result: number[] = [];
    const stack: number[] = [start];
    
    while (stack.length > 0) {
        const current = stack.pop()!; // Pop (LIFO)
        
        if (visited.has(current)) continue; // Skip if already visited
        
        visited.add(current);
        result.push(current); // Pre-order processing
        
        // Push neighbors to stack
        // Reverse order to match recursive DFS order (optional)
        const neighbors = graph.neighbors(current);
        for (let i = neighbors.length - 1; i >= 0; i--) {
            if (!visited.has(neighbors[i])) {
                stack.push(neighbors[i]);
            }
        }
    }
    
    return result;
}

Visualizing DFS Execution:

Same graph, same start vertex A:

       A
      /|\
     B C D
    /|   |
   E F   G

DFS Execution (exploring leftmost first):

Stack: [A] → Pop A, push neighbors → Stack: [D, C, B]
Stack: [D, C, B] → Pop B, push neighbors → Stack: [D, C, F, E]
Stack: [D, C, F, E] → Pop E (no unvisited neighbors) → Stack: [D, C, F]
Stack: [D, C, F] → Pop F (no unvisited neighbors) → Stack: [D, C]
Stack: [D, C] → Pop C (no unvisited neighbors) → Stack: [D]
Stack: [D] → Pop D, push neighbors → Stack: [G]
Stack: [G] → Pop G → Done

Discovery Order: A → B → E → F → C → D → G

Notice the "deep dive" pattern: A → B → E, backtrack, F, backtrack, C, backtrack, D → G.

DFS Tree and Edge Classification:

DFS naturally produces a spanning tree (or forest). Edges in the original graph can be classified:

Tree edges: Edges in the DFS tree
Back edges: Edges to ancestors (indicate cycles!)
Forward edges: Edges to descendants (in directed graphs)
Cross edges: Edges to non-ancestors/descendants (in directed graphs)

Back Edges and Cycle Detection

When to Use BFS vs DFS

Choosing between BFS and DFS isn't arbitrary—each has characteristics that make it ideal for specific problem types. Here's a comprehensive decision guide:

Use BFS When:

Finding shortest paths (unweighted): BFS's level-by-level exploration guarantees the first path found is the shortest.
Finding the closest/nearest: "Find the nearest hospital," "Find closest matching node"—BFS explores by distance.
Level-order processing: When you need to process nodes level by level (e.g., binary tree level-order traversal).
Web crawling for shallow content: Discovering pages within k links of the homepage.
Social network distance: "Degrees of separation" problems.

Use DFS When:

Cycle detection: DFS's "in-progress" state naturally reveals back edges (cycles).
Topological sorting: DFS finish times give topological order for DAGs.
Path finding (any path, not shortest): DFS finds A path; if you just need existence, DFS is fine.
Backtracking problems: Sudoku, N-Queens, maze solving—DFS's recursive structure matches backtracking.
Connected components / Strongly connected components: DFS efficiently partitions graphs.
Deep exploration preferred: When solutions are "deep" in the search space (e.g., game trees).

BFS vs DFS Decision Matrix
Scenario	BFS	DFS	Why
Shortest path (unweighted)	✓ Optimal	✗ Suboptimal	BFS explores by distance
Shortest path (weighted)	✗ Use Dijkstra	✗ Use Dijkstra	Neither handles weights correctly
Cycle detection	✓ Possible	✓ Natural fit	DFS back edges indicate cycles
Topological sort	✓ Kahn's algorithm	✓ Using finish times	Both work; DFS is often simpler
Finding any path	✓ Works	✓ Works	DFS often faster due to less memory
All paths between two nodes	✓ Works	✓ Natural fit	DFS backtracking structure suits this
Spanning tree	✓ BFS tree	✓ DFS tree	Both produce valid spanning trees
Bipartite check	✓ With 2-coloring	✓ With 2-coloring	Both work equally well
Memory-constrained	✗ Wide frontiers costly	✓ Depth-limited	DFS stack is often smaller

Memory Trade-off

Classic Applications of BFS and DFS

Let's examine specific problems where BFS and DFS shine, understanding why each algorithm is the right choice:

Application 1: Shortest Path in a Maze (BFS)

Given a grid where 0 is passable and 1 is a wall, find the shortest path from top-left to bottom-right.

Why BFS? Each cell-to-cell move has equal cost (1 step). BFS explores all cells at distance k before any at distance k+1, guaranteeing when we reach the destination, it's via the shortest path.

Application 2: Detecting Cycles in a Directed Graph (DFS)

Determine if a directed graph contains any cycles.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
enum Color {
    WHITE,  // Unvisited
    GRAY,   // In progress (on current DFS path)
    BLACK   // Completed (fully explored)
}
 
function hasCycle(graph: Map<number, number[]>, numVertices: number): boolean {
    const color = new Array(numVertices).fill(Color.WHITE);
    
    function dfs(vertex: number): boolean {
        color[vertex] = Color.GRAY; // Mark as in-progress
        
        for (const neighbor of graph.get(vertex) || []) {
            if (color[neighbor] === Color.GRAY) {
                // Back edge found! Neighbor is on current path = cycle
                return true;
            }
            if (color[neighbor] === Color.WHITE) {
                if (dfs(neighbor)) return true; // Cycle found deeper
            }
        }
        
        color[vertex] = Color.BLACK; // Fully explored
        return false;
    }
    
    // Check all vertices (graph may be disconnected)
    for (let v = 0; v < numVertices; v++) {
        if (color[v] === Color.WHITE) {
            if (dfs(v)) return true;
        }
    }
    
    return false;
}

Application 3: Connected Components (DFS or BFS)

Find all connected components in an undirected graph.

Why Either Works? Both fully explore all reachable vertices from a starting point. Run traversal from each unvisited vertex; each run discovers one component.

function findConnectedComponents(graph: Graph, numVertices: number): number[][] {
    const visited = new Set<number>();
    const components: number[][] = [];
    
    for (let v = 0; v < numVertices; v++) {
        if (!visited.has(v)) {
            const component: number[] = [];
            // DFS to find all vertices in this component
            dfs(graph, v, visited, component);
            components.push(component);
        }
    }
    
    return components;
}

Application 4: Topological Sort (DFS)

Order vertices of a DAG so that for every edge (u, v), u comes before v.

Topological Sort Intuition

Time and Space Complexity Analysis

Both BFS and DFS have the same asymptotic complexity, but understanding the details is crucial:

Time Complexity: O(V + E)

Each vertex is visited exactly once: O(V)
Each edge is examined exactly once (twice for undirected, counted as once per direction): O(E)
Total: O(V + E)

This is optimal—you can't do better than looking at each vertex and edge once.

Space Complexity: O(V)

Visited set/array: O(V)
Queue (BFS) or Stack (DFS): O(V) in the worst case
- BFS worst case: Complete graph level—all V-1 neighbors in queue
- DFS worst case: Path graph—all V vertices on stack

In Practice:

The actual space usage depends on graph structure:

Graph Shape	BFS Queue Size	DFS Stack Size
Complete graph K_n	O(n) (all neighbors at once)	O(n) (path through all)
Balanced binary tree	O(n/2) (widest level)	O(log n) (height)
Long path graph	O(1) (one neighbor at a time)	O(n) (entire path)
Wide, shallow DAG	O(width) (could be O(n))	O(depth) (could be O(1))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
// IMPORTANT: JavaScript array.shift() is O(n), not O(1)!
// For performance-critical BFS, use a proper queue implementation.
 
class EfficientQueue<T> {
    private items: T[] = [];
    private head = 0;
    
    enqueue(item: T): void {
        this.items.push(item);
    }
    
    dequeue(): T | undefined {
        if (this.head >= this.items.length) return undefined;
        const item = this.items[this.head];
        this.head++;
        // Periodically compact to avoid memory leak
        if (this.head > 1000 && this.head > this.items.length / 2) {
            this.items = this.items.slice(this.head);
            this.head = 0;
        }
        return item;
    }
    
    isEmpty(): boolean {
        return this.head >= this.items.length;
    }
}
 
// BFS with efficient queue
function bfsEfficient(graph: Graph, start: number): number[] {
    const visited = new Set<number>([start]);
    const result: number[] = [];
    const queue = new EfficientQueue<number>();
    queue.enqueue(start);
    
    while (!queue.isEmpty()) {
        const current = queue.dequeue()!;
        result.push(current);
        
        for (const neighbor of graph.neighbors(current)) {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue.enqueue(neighbor);
            }
        }
    }
    
    return result;
}

Watch for Hidden Quadratic Behavior

Building Blocks for Advanced Algorithms

BFS and DFS aren't just algorithms—they're building blocks upon which more sophisticated algorithms are constructed:

BFS → Dijkstra's Algorithm

BFS:     while queue not empty: process min-discovery-time vertex
Dijkstra: while pq not empty:   process min-distance vertex

DFS → Topological Sort

DFS → Strongly Connected Components (Kosaraju/Tarjan)

BFS → Bipartite Checking

From Traversal to Advanced Algorithm
Base Algorithm	Extension	Key Modification
BFS	Dijkstra's Shortest Path	Queue → Priority Queue; add edge weights
BFS	0-1 BFS	Use deque; 0-weight edges go to front
BFS	Multi-source BFS	Initialize queue with multiple start vertices
BFS	Bidirectional BFS	BFS from both source and target; meet in middle
DFS	Topological Sort	Reverse DFS finish order
DFS	Cycle Detection	Track in-progress vertices; back edge = cycle
DFS	Articulation Points	Track discovery times and lowlinks
DFS	Tarjan's SCC	Lowlink values identify strongly connected components
DFS	Euler Path/Circuit	DFS with edge removal

Master the Fundamentals

Summary: Mastering Graph Traversal

BFS and DFS are the two fundamental ways to systematically explore a graph. Understanding their differences, strengths, and applications is essential for graph algorithm mastery.

Key Takeaways

•The core distinction is the data structure: BFS uses a queue (FIFO), DFS uses a stack (LIFO/recursion).
•BFS explores level-by-level: This guarantees shortest paths in unweighted graphs.
•DFS explores depth-first: This naturally supports cycle detection, topological sort, and backtracking.
•Both have O(V + E) time complexity: Optimal for exploring every vertex and edge once.
•Space complexity depends on graph shape: BFS = O(width), DFS = O(depth).
•Choose based on problem requirements: Shortest path → BFS. Cycle detection, topological sort → DFS.
•They're building blocks: Most advanced graph algorithms extend BFS or DFS.

What's Next:

Page Complete

2 / 5