Fundamental Algorithms

BFS vs DFS — When to Use Which

Table of Contents

Breadth-First Search and Depth-First Search with deep intuition, decision frameworks, advanced variants, and complete solutions for classic problems.

The Idea

Explore the graph level by level. Visit all neighbors of the current node before moving deeper. Think of dropping a stone into a pond --- the ripples spread outward evenly in all directions.

BFS uses a queue (FIFO) to process nodes in the order they were discovered.

Visual Walkthrough

Graph (adjacency list):
1 --- 2 --- 5
|     |
3 --- 4 --- 6

Adjacency:
  1: [2, 3]
  2: [1, 5, 4]
  3: [1, 4]
  4: [2, 3, 6]
  5: [2]
  6: [4]

BFS from node 1:

Queue state          | Visit    | Level
---------------------|----------|------
[1]                  | 1        | 0
[2, 3]               | 2, 3     | 1      (neighbors of 1)
[5, 4]               | 5, 4     | 2      (unvisited neighbors of 2, 3)
[6]                  | 6        | 3      (unvisited neighbors of 5, 4)
[]                   | done     |

Visit order: 1 -> 2 -> 3 -> 5 -> 4 -> 6

Level visualization (wavefront):
                1           Level 0
              /   \
            2       3       Level 1
          /   \     |
        5       4---+       Level 2
                |
                6           Level 3

Why BFS Finds Shortest Paths in Unweighted Graphs

BFS processes nodes in order of their distance from the source. When node v is first discovered via node u, the path source -> ... -> u -> v is a shortest path because:

  1. u was discovered at distance d
  2. All nodes at distance d are processed before nodes at distance d+1
  3. Therefore v is at distance d+1, and no shorter path to v exists

This property only holds for unweighted graphs (or equivalently, all edges have weight 1).

Implementation

#include <bits/stdc++.h>
using namespace std;

// Basic BFS
void bfs(int start, vector<vector<int>>& adj) {
    int n = adj.size();
    vector<bool> visited(n, false);
    queue<int> q;

    visited[start] = true;
    q.push(start);

    while (!q.empty()) {
        int node = q.front();
        q.pop();

        // Process node here
        cout << node << " ";

        for (int neighbor : adj[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;  // Mark BEFORE pushing (critical!)
                q.push(neighbor);
            }
        }
    }
}

Why mark visited BEFORE pushing, not after popping?

If we mark after popping, the same node can be pushed multiple times by different neighbors, wasting time and space:

Bad (mark on pop):           Good (mark on push):
  Queue: [1]                  Queue: [1]
  Pop 1, mark 1               Push neighbors 2,3
  Push 2 (unmarked)           of 1, mark 2,3
  Push 3 (unmarked)           Queue: [2, 3]
  Queue: [2, 3]              Pop 2
  Pop 2, mark 2              Push 5 (unvisited), mark 5
  Push 5                     Push 4 (unvisited), mark 4
  Push 4 (unmarked)          Queue: [3, 5, 4]
  Queue: [3, 5, 4]           Pop 3
  Pop 3, mark 3              4 already visited, skip
  Push 4 (unmarked! again!)  Queue: [5, 4]
  Queue: [5, 4, 4]  <-- DUPLICATE!

BFS with Distance Tracking

// Returns shortest distance from start to all nodes
vector<int> bfsDistance(int start, vector<vector<int>>& adj) {
    int n = adj.size();
    vector<int> dist(n, -1);  // -1 means unreachable
    queue<int> q;

    dist[start] = 0;
    q.push(start);

    while (!q.empty()) {
        int node = q.front();
        q.pop();

        for (int neighbor : adj[node]) {
            if (dist[neighbor] == -1) {
                dist[neighbor] = dist[node] + 1;
                q.push(neighbor);
            }
        }
    }
    return dist;
}

BFS with Path Reconstruction

// Find shortest path from start to end, return the path
vector<int> bfsPath(int start, int end, vector<vector<int>>& adj) {
    int n = adj.size();
    vector<int> parent(n, -1);
    vector<bool> visited(n, false);
    queue<int> q;

    visited[start] = true;
    q.push(start);

    while (!q.empty()) {
        int node = q.front();
        q.pop();

        if (node == end) break;

        for (int neighbor : adj[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                parent[neighbor] = node;
                q.push(neighbor);
            }
        }
    }

    // Reconstruct path
    if (!visited[end]) return {};  // unreachable

    vector<int> path;
    for (int v = end; v != -1; v = parent[v]) {
        path.push_back(v);
    }
    reverse(path.begin(), path.end());
    return path;
}

BFS on a Grid

Many BFS problems use 2D grids instead of explicit graphs.

// BFS on a grid with 4-directional movement
int bfsGrid(vector<vector<int>>& grid, pair<int,int> start, pair<int,int> target) {
    int m = grid.size(), n = grid[0].size();
    vector<vector<bool>> visited(m, vector<bool>(n, false));
    queue<pair<int,int>> q;

    int dx[] = {0, 0, 1, -1};
    int dy[] = {1, -1, 0, 0};

    visited[start.first][start.second] = true;
    q.push(start);
    int steps = 0;

    while (!q.empty()) {
        int size = q.size();  // Process level by level
        for (int i = 0; i < size; i++) {
            auto [x, y] = q.front();
            q.pop();

            if (x == target.first && y == target.second) return steps;

            for (int d = 0; d < 4; d++) {
                int nx = x + dx[d];
                int ny = y + dy[d];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n
                    && !visited[nx][ny] && grid[nx][ny] != 1) {  // 1 = wall
                    visited[nx][ny] = true;
                    q.push({nx, ny});
                }
            }
        }
        steps++;
    }
    return -1;  // unreachable
}

BFS Properties Summary

Property Value
Time Complexity O(V + E)
Space Complexity O(V) for the queue (worst case: entire level of a wide graph)
Shortest Path Yes, in unweighted graphs
Data Structure Queue (FIFO)
Exploration Pattern Level-by-level wavefront
Complete Yes (always finds goal if it exists, in finite graphs)

The Idea

Go as deep as possible along each branch before backtracking. Like exploring a maze: follow one path all the way to a dead end, then backtrack and try the next branch.

DFS uses a stack (LIFO) --- either explicitly or implicitly via recursion.

Visual Walkthrough

Same graph:
1 --- 2 --- 5
|     |
3 --- 4 --- 6

DFS from node 1 (choosing neighbors in order of adjacency list):

adj[1] = [2, 3]
adj[2] = [1, 5, 4]
adj[3] = [1, 4]
adj[4] = [2, 3, 6]
adj[5] = [2]
adj[6] = [4]

Recursive trace:
dfs(1)
  visited = {1}
  -> dfs(2)
       visited = {1, 2}
       -> dfs(5)
            visited = {1, 2, 5}
            neighbor 2: already visited
            return (dead end)
       -> dfs(4)
            visited = {1, 2, 5, 4}
            neighbor 2: already visited
            -> dfs(3)
                 visited = {1, 2, 5, 4, 3}
                 neighbor 1: already visited
                 neighbor 4: already visited
                 return
            -> dfs(6)
                 visited = {1, 2, 5, 4, 3, 6}
                 neighbor 4: already visited
                 return
            return
       return
  neighbor 3: already visited
  return

Visit order: 1 -> 2 -> 5 -> 4 -> 3 -> 6

Stack visualization:
|6|    <- deepest point
|3|
|4|
|5|
|2|
|1|

Recursive DFS

void dfs(int node, vector<vector<int>>& adj, vector<bool>& visited) {
    visited[node] = true;
    // Process node here (pre-order)

    for (int neighbor : adj[node]) {
        if (!visited[neighbor]) {
            dfs(neighbor, adj, visited);
        }
    }

    // Process node here (post-order)
}

// Calling DFS for all components
void dfsAll(vector<vector<int>>& adj) {
    int n = adj.size();
    vector<bool> visited(n, false);
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            dfs(i, adj, visited);
        }
    }
}

Iterative DFS (using explicit stack)

void dfsIterative(int start, vector<vector<int>>& adj) {
    int n = adj.size();
    vector<bool> visited(n, false);
    stack<int> st;

    st.push(start);

    while (!st.empty()) {
        int node = st.top();
        st.pop();

        if (visited[node]) continue;  // May be pushed multiple times
        visited[node] = true;

        // Process node here

        // Push neighbors in reverse order to visit in original order
        for (int i = (int)adj[node].size() - 1; i >= 0; i--) {
            if (!visited[adj[node][i]]) {
                st.push(adj[node][i]);
            }
        }
    }
}

Subtle difference: Iterative DFS with a stack behaves slightly differently from recursive DFS. The recursive version processes nodes in a strict depth-first manner, while the iterative version may visit nodes in a different order because multiple entries can exist on the stack for the same node. The if (visited[node]) continue; check handles this.

DFS with Entry/Exit Times

Extremely useful for many advanced graph algorithms.

int timer = 0;
vector<int> tin, tout;  // entry and exit times

void dfs(int node, int parent, vector<vector<int>>& adj) {
    tin[node] = timer++;

    for (int neighbor : adj[node]) {
        if (neighbor != parent) {
            dfs(neighbor, node, adj);
        }
    }

    tout[node] = timer++;
}

// Node u is ancestor of v if and only if:
//   tin[u] < tin[v] && tout[u] > tout[v]

Example tree:       Entry/Exit times:
      1             1: [0, 11]
     / \            2: [1, 6]
    2   3           4: [2, 3]
   / \   \          5: [4, 5]
  4   5   6         3: [7, 10]
                    6: [8, 9]

Node 2 is ancestor of node 5?
  tin[2]=1 < tin[5]=4 and tout[2]=6 > tout[5]=5  -> YES

DFS on a Grid

void dfsGrid(vector<vector<int>>& grid, int x, int y,
             vector<vector<bool>>& visited) {
    int m = grid.size(), n = grid[0].size();
    if (x < 0 || x >= m || y < 0 || y >= n) return;
    if (visited[x][y] || grid[x][y] == 0) return;

    visited[x][y] = true;

    int dx[] = {0, 0, 1, -1};
    int dy[] = {1, -1, 0, 0};

    for (int d = 0; d < 4; d++) {
        dfsGrid(grid, x + dx[d], y + dy[d], visited);
    }
}

DFS Properties Summary

Property Value
Time Complexity O(V + E)
Space Complexity O(V) for recursion stack (or explicit stack)
Shortest Path No (finds A path, not the shortest)
Data Structure Stack (LIFO) / Recursion
Exploration Pattern Deep dive, then backtrack
Complete Yes (in finite graphs)

The Big Comparison

When to Use BFS

  1. Shortest path in unweighted graph --- BFS always finds it. DFS does not.

  2. Level-order traversal of a tree --- naturally produced by BFS.

  3. Multi-source BFS --- start from multiple sources simultaneously. Examples: rotting oranges, walls and gates, 01 matrix.

  4. Minimum steps/moves problems --- any problem asking for "minimum number of steps" in an unweighted graph screams BFS.

  5. Finding all nodes at distance k --- BFS gives you distance for free.

  6. 0-1 BFS --- graph with edge weights 0 and 1 only (use deque).

  7. Bidirectional BFS --- search from both ends to reduce complexity.

When to Use DFS

  1. Detect cycles in directed/undirected graphs --- natural with back edges.

  2. Topological sort --- DFS post-order gives reverse topological order.

  3. Path finding (find ANY path, all paths) --- DFS explores paths naturally.

  4. Connected components (both work, but DFS code is simpler).

  5. Flood fill / island problems --- DFS with recursion is clean and simple.

  6. Tree problems --- diameter, height, LCA, subtree queries. Trees are naturally recursive, so DFS fits perfectly.

  7. Backtracking --- inherently DFS (try a choice, recurse, undo choice).

  8. Strongly connected components --- Tarjan's and Kosaraju's use DFS.

  9. Articulation points and bridges --- require DFS tree properties.

  10. Check if graph is bipartite --- both work, DFS is slightly simpler.

Head-to-Head Comparison Table

Criteria BFS DFS Data Structure Queue (FIFO) Stack / Recursion (LIFO) Memory (tree) O(W) where W = width O(H) where H = height Memory (general graph) O(V) O(V) Shortest path (unwtd) YES NO Complete YES YES (finite graphs) Topological sort Kahn's algorithm Post-order reversal Cycle detection Harder (need indegree) Natural (back edges) Space on wide graphs BAD (entire level) GOOD Space on deep graphs GOOD BAD (stack overflow!) Implementation Queue-based loop Recursion or explicit stack

Memory Comparison on Trees

Wide Tree (balanced) 1 2 3 4 5 ... ... Width W can be O(n) BFS: O(W) BAD DFS: O(H) GOOD Deep Tree (skewed) 1 2 3 ... Height H can be O(n) BFS: O(1) GOOD DFS: O(H) BAD

Decision Flowchart

START Shortest path in unweighted graph? YES BFS NO Need topological sort? YES DFS / Kahn's NO Need cycle detection? YES DFS (easier) NO All paths / backtracking? YES DFS NO Tree / recursive structure? YES DFS NO Level-by-level needed? YES BFS NO Either works DFS often simpler

Advanced BFS Variants

Multi-Source BFS

Instead of starting from one source, start from ALL sources simultaneously. All sources are at distance 0. This is equivalent to adding a virtual source node connected to all real sources with weight-0 edges.

Key insight: Push all sources into the queue at the beginning.

Classic example: Rotting Oranges (LC 994)
Grid with fresh oranges (1) and rotten oranges (2).
Each minute, rotten oranges rot adjacent fresh ones.
Return minimum minutes until all oranges are rotten, or -1 if impossible.

    2  1  1        2  2  1        2  2  2        2  2  2        2  2  2
    1  1  0   ->   2  1  0   ->   2  2  0   ->   2  2  0   ->   2  2  0
    0  1  1        0  1  1        0  2  1        0  2  2        0  2  2
  t=0            t=1            t=2            t=3            t=4
                                                              (done!)

int orangesRotting(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    queue<pair<int,int>> q;
    int fresh = 0;

    // Add all rotten oranges as sources
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 2) q.push({i, j});
            else if (grid[i][j] == 1) fresh++;
        }
    }

    if (fresh == 0) return 0;

    int dx[] = {0, 0, 1, -1};
    int dy[] = {1, -1, 0, 0};
    int minutes = 0;

    while (!q.empty()) {
        int size = q.size();
        bool rotted = false;
        for (int i = 0; i < size; i++) {
            auto [x, y] = q.front();
            q.pop();
            for (int d = 0; d < 4; d++) {
                int nx = x + dx[d], ny = y + dy[d];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == 1) {
                    grid[nx][ny] = 2;
                    fresh--;
                    q.push({nx, ny});
                    rotted = true;
                }
            }
        }
        if (rotted) minutes++;
    }

    return fresh == 0 ? minutes : -1;
}

0-1 BFS

For graphs where edge weights are 0 or 1 only. Use a deque instead of a queue:

  • Weight 0 edge: push to front of deque
  • Weight 1 edge: push to back of deque

This maintains the invariant that the deque is sorted by distance, giving correct shortest paths without Dijkstra's overhead.

Example: Grid with free moves (weight 0) and paid moves (weight 1).

Why it works:
  Regular queue for BFS: [d, d, d, d+1, d+1, d+1]
  With 0-1 edges, we might discover a node at distance d from a node at distance d.
  Push it to FRONT so it's processed before d+1 nodes.

  Deque state:  [d, d, d, d, d+1, d+1]
                 ^front           back^

vector<int> bfs01(int start, vector<vector<pair<int,int>>>& adj) {
    // adj[u] = {(v, w)} where w is 0 or 1
    int n = adj.size();
    vector<int> dist(n, INT_MAX);
    deque<int> dq;

    dist[start] = 0;
    dq.push_back(start);

    while (!dq.empty()) {
        int u = dq.front();
        dq.pop_front();

        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                if (w == 0) dq.push_front(v);  // Free edge: high priority
                else dq.push_back(v);           // Cost-1 edge: low priority
            }
        }
    }
    return dist;
}

Time: O(V + E), same as regular BFS. Much faster than Dijkstra's O((V+E) log V).

Example: Minimum Cost to Make at Least One Valid Path in a Grid (LC 1368)

Grid with arrows. Moving in the arrow direction costs 0, other directions cost 1.

int minCost(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    // Directions: 1=right, 2=left, 3=down, 4=up
    int dx[] = {0, 0, 1, -1};
    int dy[] = {1, -1, 0, 0};

    vector<vector<int>> dist(m, vector<int>(n, INT_MAX));
    deque<pair<int,int>> dq;

    dist[0][0] = 0;
    dq.push_back({0, 0});

    while (!dq.empty()) {
        auto [x, y] = dq.front();
        dq.pop_front();

        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d], ny = y + dy[d];
            int cost = (grid[x][y] == d + 1) ? 0 : 1;  // 0 if following arrow

            if (nx >= 0 && nx < m && ny >= 0 && ny < n
                && dist[x][y] + cost < dist[nx][ny]) {
                dist[nx][ny] = dist[x][y] + cost;
                if (cost == 0) dq.push_front({nx, ny});
                else dq.push_back({nx, ny});
            }
        }
    }
    return dist[m-1][n-1];
}

Bidirectional BFS

Search from both source and target simultaneously. When the two search frontiers meet, we have found the shortest path.

Normal BFS: explores ~b^d nodes (b = branching factor, d = distance)
Bidirectional: explores ~2 * b^(d/2) nodes

For b=10, d=6:
  Normal:       10^6 = 1,000,000 nodes
  Bidirectional: 2 * 10^3 = 2,000 nodes  (500x faster!)

Visualization:
  Source                    Target
    *-->                <--*
    *--->              <---*
    *---->            <----*
    *----->          <-----*
    *------>  MEET!  <-----*

int bidirectionalBFS(int start, int end, vector<vector<int>>& adj) {
    if (start == end) return 0;

    int n = adj.size();
    vector<int> distS(n, -1), distT(n, -1);
    queue<int> qS, qT;

    distS[start] = 0; qS.push(start);
    distT[end] = 0;   qT.push(end);

    auto expand = [&](queue<int>& q, vector<int>& distA, vector<int>& distB) -> int {
        int size = q.size();
        int best = INT_MAX;
        for (int i = 0; i < size; i++) {
            int node = q.front(); q.pop();
            for (int neighbor : adj[node]) {
                if (distA[neighbor] == -1) {
                    distA[neighbor] = distA[node] + 1;
                    q.push(neighbor);
                }
                if (distB[neighbor] != -1) {
                    best = min(best, distA[neighbor] + distB[neighbor]);
                }
            }
        }
        return best == INT_MAX ? -1 : best;
    };

    while (!qS.empty() && !qT.empty()) {
        int result;
        // Expand the smaller frontier
        if (qS.size() <= qT.size()) {
            result = expand(qS, distS, distT);
        } else {
            result = expand(qT, distT, distS);
        }
        if (result != -1) return result;
    }
    return -1;  // unreachable
}

When to use: When the graph is very large and you know both source and target. Classic example: Word Ladder (LC 127).

Advanced DFS Concepts

DFS Tree and Edge Classification

When DFS runs on a directed graph, it classifies every edge into one of four types:

Edge Types in Directed Graph DFS:

Tree edge:     u -> v where v is first discovered via u
               (forms the DFS tree)

Back edge:     u -> v where v is an ANCESTOR of u in DFS tree
               INDICATES A CYCLE!

Forward edge:  u -> v where v is a DESCENDANT of u (but not tree edge)
               (u was discovered before v, but v was reached via another path)

Cross edge:    u -> v where v is neither ancestor nor descendant
               (v is in a different branch or already fully processed)

Visual:
            1
           / \
          2   3          Tree edges: solid lines
         /     \         Back edge:  4 -> 1 (dashed)
        4       5        Forward:    1 -> 4 (if direct edge exists)
         \               Cross:      4 -> 5 (if direct edge exists)
          (back to 1)

How to detect edge types using colors/states:

enum Color { WHITE, GRAY, BLACK };
// WHITE = undiscovered
// GRAY  = discovered but not finished (in current DFS path)
// BLACK = completely processed

void dfs(int u, vector<vector<int>>& adj, vector<Color>& color) {
    color[u] = GRAY;

    for (int v : adj[u]) {
        if (color[v] == WHITE) {
            // Tree edge u -> v
            dfs(v, adj, color);
        } else if (color[v] == GRAY) {
            // Back edge u -> v (CYCLE DETECTED!)
        } else {
            // color[v] == BLACK
            // Forward or cross edge
        }
    }

    color[u] = BLACK;
}

Cycle Detection

In Undirected Graphs

A cycle exists if DFS encounters an already-visited node that is NOT the parent.

bool hasCycleDFS(int node, int parent, vector<vector<int>>& adj,
                  vector<bool>& visited) {
    visited[node] = true;

    for (int neighbor : adj[node]) {
        if (!visited[neighbor]) {
            if (hasCycleDFS(neighbor, node, adj, visited))
                return true;
        } else if (neighbor != parent) {
            return true;  // Back edge found -> cycle!
        }
    }
    return false;
}

bool hasCycle(vector<vector<int>>& adj) {
    int n = adj.size();
    vector<bool> visited(n, false);
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            if (hasCycleDFS(i, -1, adj, visited))
                return true;
        }
    }
    return false;
}

In Directed Graphs

A cycle exists if DFS encounters a GRAY node (node in current path).

bool hasCycleDirected(int node, vector<vector<int>>& adj,
                       vector<int>& color) {
    color[node] = 1;  // GRAY (in current path)

    for (int neighbor : adj[node]) {
        if (color[neighbor] == 1) return true;   // Back edge -> cycle
        if (color[neighbor] == 0) {               // WHITE -> unexplored
            if (hasCycleDirected(neighbor, adj, color))
                return true;
        }
    }

    color[node] = 2;  // BLACK (fully processed)
    return false;
}

// color: 0=WHITE, 1=GRAY, 2=BLACK
bool hasCycleDirectedGraph(vector<vector<int>>& adj) {
    int n = adj.size();
    vector<int> color(n, 0);
    for (int i = 0; i < n; i++) {
        if (color[i] == 0) {
            if (hasCycleDirected(i, adj, color))
                return true;
        }
    }
    return false;
}

Topological Sort using DFS

Topological sort of a DAG (Directed Acyclic Graph): a linear ordering of vertices such that for every directed edge u -> v, u appears before v.

Key insight: In DFS post-order, a node is finished AFTER all its descendants. So reversing post-order gives topological order.

DAG:
  5 -> 0
  5 -> 2
  4 -> 0
  4 -> 1
  2 -> 3
  3 -> 1

DFS from 5: visit 0 (finish 0), visit 2 -> 3 -> 1 (finish 1, 3, 2), finish 5
DFS from 4: 0 visited, 1 visited, finish 4

Post-order: [0, 1, 3, 2, 5, 4]
Reversed:   [4, 5, 2, 3, 1, 0]

Verify: 5->0 (5 before 0), 5->2 (5 before 2), 4->0, 4->1, 2->3, 3->1. All satisfied!

vector<int> topoSortDFS(vector<vector<int>>& adj, int n) {
    vector<int> order;
    vector<bool> visited(n, false);

    function<void(int)> dfs = [&](int u) {
        visited[u] = true;
        for (int v : adj[u]) {
            if (!visited[v]) dfs(v);
        }
        order.push_back(u);  // Post-order
    };

    for (int i = 0; i < n; i++) {
        if (!visited[i]) dfs(i);
    }

    reverse(order.begin(), order.end());  // Reverse post-order = topo order
    return order;
}

Topological Sort using BFS (Kahn's Algorithm)

Repeatedly remove nodes with in-degree 0. If all nodes are removed, the graph is a DAG and the removal order is a valid topological sort.

Advantage over DFS: Can easily detect cycles (if not all nodes are removed, there's a cycle). Also useful when you need to process nodes in topological order level by level.

DAG:
  5 -> 0         In-degrees:
  5 -> 2           0: 2 (from 5, 4)
  4 -> 0           1: 2 (from 4, 3)
  4 -> 1           2: 1 (from 5)
  2 -> 3           3: 1 (from 2)
  3 -> 1           4: 0
                   5: 0

Step 1: Nodes with indegree 0: {4, 5}. Remove 4.
  Update: indegree[0]-- -> 1, indegree[1]-- -> 1
  Order: [4]

Step 2: Remove 5.
  Update: indegree[0]-- -> 0, indegree[2]-- -> 0
  Order: [4, 5]

Step 3: Nodes with indegree 0: {0, 2}. Remove 0.
  Order: [4, 5, 0]

Step 4: Remove 2.
  Update: indegree[3]-- -> 0
  Order: [4, 5, 0, 2]

Step 5: Remove 3.
  Update: indegree[1]-- -> 0
  Order: [4, 5, 0, 2, 3]

Step 6: Remove 1.
  Order: [4, 5, 0, 2, 3, 1]

All 6 nodes removed -> valid topological sort!

vector<int> kahnTopoSort(vector<vector<int>>& adj, int n) {
    vector<int> indegree(n, 0);
    for (int u = 0; u < n; u++) {
        for (int v : adj[u]) {
            indegree[v]++;
        }
    }

    queue<int> q;
    for (int i = 0; i < n; i++) {
        if (indegree[i] == 0) q.push(i);
    }

    vector<int> order;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        order.push_back(u);

        for (int v : adj[u]) {
            if (--indegree[v] == 0) {
                q.push(v);
            }
        }
    }

    // If order.size() != n, graph has a cycle!
    return order;
}

DFS vs BFS for Topological Sort

Criteria DFS Topo Sort Kahn's (BFS) Topo Sort Cycle Detection Need extra color array Natural (|order| < n) Multiple Orders Hard to enumerate Easy with priority queue Reverse Topo Direct (no reverse) Need to reverse Implementation Recursive, elegant Iterative, explicit Use Case General purpose Need cycle detect or lexicographically smallest

Finding Connected Components

// Count connected components in undirected graph
int countComponents(int n, vector<vector<int>>& adj) {
    vector<bool> visited(n, false);
    int components = 0;

    function<void(int)> dfs = [&](int u) {
        visited[u] = true;
        for (int v : adj[u]) {
            if (!visited[v]) dfs(v);
        }
    };

    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            dfs(i);
            components++;
        }
    }
    return components;
}

Bipartite Check (Using Either BFS or DFS)

A graph is bipartite if nodes can be colored with 2 colors such that no adjacent nodes share a color. Equivalent to: the graph has no odd-length cycles.

// BFS version
bool isBipartiteBFS(int n, vector<vector<int>>& adj) {
    vector<int> color(n, -1);

    for (int start = 0; start < n; start++) {
        if (color[start] != -1) continue;

        queue<int> q;
        q.push(start);
        color[start] = 0;

        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : adj[u]) {
                if (color[v] == -1) {
                    color[v] = 1 - color[u];
                    q.push(v);
                } else if (color[v] == color[u]) {
                    return false;  // Same color as neighbor -> not bipartite
                }
            }
        }
    }
    return true;
}

// DFS version
bool isBipartiteDFS(int node, int c, vector<vector<int>>& adj, vector<int>& color) {
    color[node] = c;
    for (int neighbor : adj[node]) {
        if (color[neighbor] == -1) {
            if (!isBipartiteDFS(neighbor, 1 - c, adj, color))
                return false;
        } else if (color[neighbor] == c) {
            return false;
        }
    }
    return true;
}

Articulation Points and Bridges (Tarjan's Algorithm)

These require DFS and cannot be easily done with BFS.

Articulation point: A vertex whose removal disconnects the graph. Bridge: An edge whose removal disconnects the graph.

Graph:
  1 --- 2 --- 3
        |     |
        4 --- 5 --- 6

Bridges: edge (5, 6)  -- removing it disconnects 6
Articulation points: 2 (removing disconnects {1} from {3,4,5,6})
                     5 (removing disconnects {6} from rest)

Key idea: Use DFS and track disc[u] (discovery time) and low[u] (lowest discovery time reachable from subtree of u).

void findBridges(int n, vector<vector<int>>& adj) {
    vector<int> disc(n, -1), low(n, -1);
    int timer = 0;
    vector<pair<int,int>> bridges;

    function<void(int, int)> dfs = [&](int u, int parent) {
        disc[u] = low[u] = timer++;

        for (int v : adj[u]) {
            if (v == parent) continue;
            if (disc[v] == -1) {
                dfs(v, u);
                low[u] = min(low[u], low[v]);
                if (low[v] > disc[u]) {
                    bridges.push_back({u, v});
                }
            } else {
                low[u] = min(low[u], disc[v]);
            }
        }
    };

    for (int i = 0; i < n; i++) {
        if (disc[i] == -1) dfs(i, -1);
    }

    cout << "Bridges:\n";
    for (auto [u, v] : bridges) {
        cout << u << " -- " << v << "\n";
    }
}

void findArticulationPoints(int n, vector<vector<int>>& adj) {
    vector<int> disc(n, -1), low(n, -1);
    vector<bool> isAP(n, false);
    int timer = 0;

    function<void(int, int)> dfs = [&](int u, int parent) {
        disc[u] = low[u] = timer++;
        int children = 0;

        for (int v : adj[u]) {
            if (v == parent) continue;
            if (disc[v] == -1) {
                children++;
                dfs(v, u);
                low[u] = min(low[u], low[v]);

                // u is AP if:
                // 1. u is root and has 2+ children
                if (parent == -1 && children > 1) isAP[u] = true;
                // 2. u is not root and low[v] >= disc[u]
                if (parent != -1 && low[v] >= disc[u]) isAP[u] = true;
            } else {
                low[u] = min(low[u], disc[v]);
            }
        }
    };

    for (int i = 0; i < n; i++) {
        if (disc[i] == -1) dfs(i, -1);
    }

    cout << "Articulation Points:\n";
    for (int i = 0; i < n; i++) {
        if (isAP[i]) cout << i << "\n";
    }
}

Strongly Connected Components (Kosaraju's Algorithm)

A strongly connected component (SCC) is a maximal set of vertices where every vertex is reachable from every other vertex (in a directed graph).

Directed graph:
  1 -> 2 -> 3 -> 1     (cycle: SCC {1, 2, 3})
  3 -> 4                (4 is its own SCC)
  4 -> 5 -> 6 -> 4     (cycle: SCC {4, 5, 6})

SCCs: {1, 2, 3}, {4, 5, 6}

Kosaraju's Algorithm (two DFS passes):

  1. DFS on original graph, push to stack on finish (post-order)
  2. Transpose the graph (reverse all edges)
  3. DFS on transposed graph in stack order --- each DFS tree is an SCC
vector<vector<int>> kosaraju(int n, vector<vector<int>>& adj) {
    // Step 1: DFS on original graph, record finish order
    vector<bool> visited(n, false);
    vector<int> order;

    function<void(int)> dfs1 = [&](int u) {
        visited[u] = true;
        for (int v : adj[u]) {
            if (!visited[v]) dfs1(v);
        }
        order.push_back(u);
    };

    for (int i = 0; i < n; i++) {
        if (!visited[i]) dfs1(i);
    }

    // Step 2: Build transpose graph
    vector<vector<int>> radj(n);
    for (int u = 0; u < n; u++) {
        for (int v : adj[u]) {
            radj[v].push_back(u);
        }
    }

    // Step 3: DFS on transpose in reverse finish order
    fill(visited.begin(), visited.end(), false);
    vector<vector<int>> sccs;

    function<void(int, vector<int>&)> dfs2 = [&](int u, vector<int>& comp) {
        visited[u] = true;
        comp.push_back(u);
        for (int v : radj[u]) {
            if (!visited[v]) dfs2(v, comp);
        }
    };

    for (int i = n - 1; i >= 0; i--) {
        int u = order[i];
        if (!visited[u]) {
            vector<int> comp;
            dfs2(u, comp);
            sccs.push_back(comp);
        }
    }
    return sccs;
}

Classic Problems -- Categorized

BFS Problems

1. Shortest Path in Binary Matrix (LC 1091)

Given an n x n binary grid, find the shortest path from (0,0) to (n-1,n-1) using 8-directional movement. Cells with 0 are passable, 1 are blocked.

int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
    int n = grid.size();
    if (grid[0][0] == 1 || grid[n-1][n-1] == 1) return -1;

    int dx[] = {-1,-1,-1,0,0,1,1,1};
    int dy[] = {-1,0,1,-1,1,-1,0,1};

    queue<pair<int,int>> q;
    q.push({0, 0});
    grid[0][0] = 1;  // Mark visited
    int pathLen = 1;

    while (!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            auto [x, y] = q.front(); q.pop();
            if (x == n-1 && y == n-1) return pathLen;

            for (int d = 0; d < 8; d++) {
                int nx = x + dx[d], ny = y + dy[d];
                if (nx >= 0 && nx < n && ny >= 0 && ny < n && grid[nx][ny] == 0) {
                    grid[nx][ny] = 1;
                    q.push({nx, ny});
                }
            }
        }
        pathLen++;
    }
    return -1;
}

2. Word Ladder (LC 127)

Transform beginWord to endWord by changing one letter at a time, each intermediate word must be in the dictionary. Return minimum number of transformations.

int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
    unordered_set<string> wordSet(wordList.begin(), wordList.end());
    if (wordSet.find(endWord) == wordSet.end()) return 0;

    queue<string> q;
    q.push(beginWord);
    int level = 1;

    while (!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            string word = q.front(); q.pop();

            for (int j = 0; j < (int)word.size(); j++) {
                char original = word[j];
                for (char c = 'a'; c <= 'z'; c++) {
                    if (c == original) continue;
                    word[j] = c;
                    if (word == endWord) return level + 1;
                    if (wordSet.count(word)) {
                        wordSet.erase(word);  // Mark visited by removing
                        q.push(word);
                    }
                }
                word[j] = original;
            }
        }
        level++;
    }
    return 0;
}

3. Rotting Oranges (LC 994) --- Multi-Source BFS

Already covered in the Multi-Source BFS section above.

4. 01 Matrix (LC 542) --- Multi-Source BFS

Given a matrix with 0s and 1s, find the distance of each cell to the nearest 0.

vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
    int m = mat.size(), n = mat[0].size();
    vector<vector<int>> dist(m, vector<int>(n, INT_MAX));
    queue<pair<int,int>> q;

    // Multi-source: all 0-cells are sources at distance 0
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (mat[i][j] == 0) {
                dist[i][j] = 0;
                q.push({i, j});
            }
        }
    }

    int dx[] = {0, 0, 1, -1};
    int dy[] = {1, -1, 0, 0};

    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d], ny = y + dy[d];
            if (nx >= 0 && nx < m && ny >= 0 && ny < n
                && dist[nx][ny] > dist[x][y] + 1) {
                dist[nx][ny] = dist[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }
    return dist;
}

5. Open the Lock (LC 752)

Start at "0000", reach target combination. Each move: turn one wheel one slot. Some combinations are deadends. Minimum moves?

int openLock(vector<string>& deadends, string target) {
    unordered_set<string> dead(deadends.begin(), deadends.end());
    if (dead.count("0000")) return -1;
    if (target == "0000") return 0;

    unordered_set<string> visited;
    queue<string> q;
    q.push("0000");
    visited.insert("0000");
    int moves = 0;

    while (!q.empty()) {
        int size = q.size();
        moves++;
        for (int i = 0; i < size; i++) {
            string curr = q.front(); q.pop();
            for (int j = 0; j < 4; j++) {
                for (int delta : {-1, 1}) {
                    string next = curr;
                    next[j] = ((next[j] - '0' + delta + 10) % 10) + '0';
                    if (next == target) return moves;
                    if (!dead.count(next) && !visited.count(next)) {
                        visited.insert(next);
                        q.push(next);
                    }
                }
            }
        }
    }
    return -1;
}

6. Minimum Knight Moves (LC 1197)

Minimum moves for a chess knight to go from (0,0) to (x,y) on infinite board.

int minKnightMoves(int x, int y) {
    x = abs(x); y = abs(y);  // Symmetry
    int dx[] = {2,2,1,1,-1,-1,-2,-2};
    int dy[] = {1,-1,2,-2,2,-2,1,-1};

    queue<pair<int,int>> q;
    set<pair<int,int>> visited;
    q.push({0, 0});
    visited.insert({0, 0});
    int moves = 0;

    while (!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            auto [cx, cy] = q.front(); q.pop();
            if (cx == x && cy == y) return moves;
            for (int d = 0; d < 8; d++) {
                int nx = cx + dx[d], ny = cy + dy[d];
                // Bound search space to avoid exploring too far
                if (nx >= -2 && ny >= -2 && nx <= x + 2 && ny <= y + 2
                    && !visited.count({nx, ny})) {
                    visited.insert({nx, ny});
                    q.push({nx, ny});
                }
            }
        }
        moves++;
    }
    return -1;
}

DFS Problems

1. Number of Islands (LC 200) --- Flood Fill

int numIslands(vector<vector<char>>& grid) {
    int m = grid.size(), n = grid[0].size();
    int count = 0;

    function<void(int, int)> dfs = [&](int x, int y) {
        if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] != '1') return;
        grid[x][y] = '0';  // Mark visited
        dfs(x+1, y); dfs(x-1, y); dfs(x, y+1); dfs(x, y-1);
    };

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == '1') {
                count++;
                dfs(i, j);
            }
        }
    }
    return count;
}

2. Course Schedule (LC 207) --- Cycle Detection in Directed Graph

bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
    vector<vector<int>> adj(numCourses);
    for (auto& p : prerequisites) {
        adj[p[1]].push_back(p[0]);
    }

    // 0 = unvisited, 1 = in current path, 2 = done
    vector<int> state(numCourses, 0);

    function<bool(int)> hasCycle = [&](int u) -> bool {
        state[u] = 1;
        for (int v : adj[u]) {
            if (state[v] == 1) return true;   // Cycle!
            if (state[v] == 0 && hasCycle(v)) return true;
        }
        state[u] = 2;
        return false;
    };

    for (int i = 0; i < numCourses; i++) {
        if (state[i] == 0 && hasCycle(i)) return false;
    }
    return true;
}

3. Clone Graph (LC 133)

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> neighbors;
    Node(int _val) : val(_val) {}
};
*/

class Solution {
    unordered_map<Node*, Node*> cloned;
public:
    Node* cloneGraph(Node* node) {
        if (!node) return nullptr;
        if (cloned.count(node)) return cloned[node];

        Node* copy = new Node(node->val);
        cloned[node] = copy;

        for (Node* neighbor : node->neighbors) {
            copy->neighbors.push_back(cloneGraph(neighbor));
        }
        return copy;
    }
};

4. Pacific Atlantic Water Flow (LC 417)

Water flows from higher to lower or equal cells. Find cells that can reach both oceans.

vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
    int m = heights.size(), n = heights[0].size();
    vector<vector<bool>> pacific(m, vector<bool>(n, false));
    vector<vector<bool>> atlantic(m, vector<bool>(n, false));

    int dx[] = {0, 0, 1, -1};
    int dy[] = {1, -1, 0, 0};

    function<void(int, int, vector<vector<bool>>&)> dfs =
        [&](int x, int y, vector<vector<bool>>& ocean) {
        ocean[x][y] = true;
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d], ny = y + dy[d];
            if (nx >= 0 && nx < m && ny >= 0 && ny < n
                && !ocean[nx][ny] && heights[nx][ny] >= heights[x][y]) {
                dfs(nx, ny, ocean);
            }
        }
    };

    // DFS from ocean borders (reverse flow: go uphill)
    for (int i = 0; i < m; i++) {
        dfs(i, 0, pacific);      // Left border (Pacific)
        dfs(i, n-1, atlantic);   // Right border (Atlantic)
    }
    for (int j = 0; j < n; j++) {
        dfs(0, j, pacific);      // Top border (Pacific)
        dfs(m-1, j, atlantic);   // Bottom border (Atlantic)
    }

    vector<vector<int>> result;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (pacific[i][j] && atlantic[i][j]) {
                result.push_back({i, j});
            }
        }
    }
    return result;
}

5. Surrounded Regions (LC 130)

Capture all 'O' regions that are NOT connected to the border.

void solve(vector<vector<char>>& board) {
    int m = board.size(), n = board[0].size();

    function<void(int, int)> dfs = [&](int x, int y) {
        if (x < 0 || x >= m || y < 0 || y >= n || board[x][y] != 'O') return;
        board[x][y] = 'S';  // Safe (connected to border)
        dfs(x+1, y); dfs(x-1, y); dfs(x, y+1); dfs(x, y-1);
    };

    // Mark all border-connected O's as safe
    for (int i = 0; i < m; i++) {
        dfs(i, 0); dfs(i, n-1);
    }
    for (int j = 0; j < n; j++) {
        dfs(0, j); dfs(m-1, j);
    }

    // Flip: O -> X (captured), S -> O (restored)
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (board[i][j] == 'O') board[i][j] = 'X';
            else if (board[i][j] == 'S') board[i][j] = 'O';
        }
    }
}

6. All Paths from Source to Target (LC 797)

Find all paths from node 0 to node n-1 in a DAG.

vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
    int n = graph.size();
    vector<vector<int>> result;
    vector<int> path;

    function<void(int)> dfs = [&](int node) {
        path.push_back(node);

        if (node == n - 1) {
            result.push_back(path);
        } else {
            for (int next : graph[node]) {
                dfs(next);
            }
        }

        path.pop_back();  // Backtrack
    };

    dfs(0);
    return result;
}

Summary: Quick Reference

Problem Type Use Shortest path (unweighted) BFS Shortest path (0-1 weights) 0-1 BFS Minimum steps / moves BFS Level-order traversal BFS Multi-source distance Multi-source BFS Cycle detection (undirected) DFS (back edge != parent) Cycle detection (directed) DFS (gray node revisit) Topological sort DFS post-order or Kahn's BFS Connected components DFS (simpler) or BFS Strongly connected components DFS (Tarjan / Kosaraju) Articulation points / bridges DFS (Tarjan) Flood fill / islands DFS (simple recursion) All paths / backtracking DFS Tree problems (height, diameter) DFS Bipartite check BFS or DFS (both work) Word transformation BFS (+ bidirectional for speed)