Stage 2: Recursive Thinking·Graphs: BFS & DFS

Medium#2076 min readGraphsTopological SortBFSDFS Cycle DetectionLeetCode

Course Schedule

Kahn's algorithm (BFS topological sort)

Cycle detection in directed graph. Both DFS (3-color) and Kahn’s BFS work.

Published Apr 16, 2026

Problem

There are numCourses courses labeled 0 .. numCourses - 1. Some courses have prerequisites given as pairs [a, b] meaning "to take a, you must first take b". Return true if you can finish all courses, false otherwise.

Input

numCourses = 2, prerequisites = [[1, 0]]

Output

true

Input

numCourses = 2, prerequisites = [[1, 0], [0, 1]]

Output

false

Explanation

0 and 1 require each other — a cycle.

Intuition

Each prerequisite [a, b] is an edge b → a ("b before a"). The question "can I finish all courses?" is the same as "does this directed graph have a valid topological order?", which is the same as "is this graph a DAG?".

Two standard answers:

Kahn's algorithm (BFS topo): Count each node's in-degree, start a queue with all in-degree-0 nodes, repeatedly pop and decrement neighbors. If every node gets popped, no cycle.
DFS with coloring: Each node is either WHITE (unvisited), GRAY (in current DFS path), or BLACK (fully processed). If DFS ever steps to a GRAY node, that's a back-edge — a cycle.

Both are O(V + E). Kahn's is slightly simpler to reason about and is what #210 (below) will extend directly.

Approach

Kahn's algorithm (BFS topo)

TimeO(V+E)

SpaceO(V+E)

Recommended

Build the adjacency list and the in-degree array. Queue everything with in-degree 0. Pop, count, decrement neighbors' in-degree, push the ones that hit 0. Return popped == numCourses.

use std::collections::VecDeque;

impl Solution {
    pub fn can_finish(num_courses: i32, prerequisites: Vec<Vec<i32>>) -> bool {
        let n = num_courses as usize;
        let mut adj: Vec<Vec<usize>> = vec![Vec::new(); n];
        let mut indeg: Vec<usize> = vec![0; n];
        for e in &prerequisites {
            let (a, b) = (e[0] as usize, e[1] as usize);
            adj[b].push(a);
            indeg[a] += 1;
        }
        let mut q: VecDeque<usize> = VecDeque::new();
        for i in 0..n {
            if indeg[i] == 0 {
                q.push_back(i);
            }
        }
        let mut popped = 0;
        while let Some(u) = q.pop_front() {
            popped += 1;
            for &v in &adj[u] {
                indeg[v] -= 1;
                if indeg[v] == 0 {
                    q.push_back(v);
                }
            }
        }
        popped == n
    }
}

Rust · runnable

function canFinish(numCourses: number, prerequisites: number[][]): boolean {
  const adj: number[][] = Array.from({ length: numCourses }, () => []);
  const indeg = new Array(numCourses).fill(0);
  for (const [a, b] of prerequisites) {
    adj[b].push(a);
    indeg[a]++;
  }
  const q: number[] = [];
  for (let i = 0; i < numCourses; i++) {
    if (indeg[i] === 0) q.push(i);
  }
  let popped = 0;
  let head = 0;
  while (head < q.length) {
    const u = q[head++];
    popped++;
    for (const v of adj[u]) {
      if (--indeg[v] === 0) q.push(v);
    }
  }
  return popped === numCourses;
}

TypeScript · runnable

DFS with three-color cycle detection

TimeO(V+E)

SpaceO(V+E)

Tri-state per node: 0 = unvisited, 1 = on current DFS stack, 2 = fully processed. DFS from each unvisited node. If we step into a node whose state is 1, there's a back-edge and the graph has a cycle.

Useful when you don't want a queue around, or when you want to reuse the DFS for something else in the same traversal.

impl Solution {
    pub fn can_finish(num_courses: i32, prerequisites: Vec<Vec<i32>>) -> bool {
        let n = num_courses as usize;
        let mut adj: Vec<Vec<usize>> = vec![Vec::new(); n];
        for e in &prerequisites {
            adj[e[1] as usize].push(e[0] as usize);
        }
        let mut color = vec![0u8; n];
        fn dfs(u: usize, adj: &[Vec<usize>], color: &mut [u8]) -> bool {
            if color[u] == 1 {
                return false; // back-edge = cycle
            }
            if color[u] == 2 {
                return true;
            }
            color[u] = 1;
            for &v in &adj[u] {
                if !dfs(v, adj, color) {
                    return false;
                }
            }
            color[u] = 2;
            true
        }
        for u in 0..n {
            if color[u] == 0 && !dfs(u, &adj, &mut color) {
                return false;
            }
        }
        true
    }
}

Rust · runnable

function canFinish(numCourses: number, prerequisites: number[][]): boolean {
  const adj: number[][] = Array.from({ length: numCourses }, () => []);
  for (const [a, b] of prerequisites) adj[b].push(a);
  const color = new Array(numCourses).fill(0);
  const dfs = (u: number): boolean => {
    if (color[u] === 1) return false;
    if (color[u] === 2) return true;
    color[u] = 1;
    for (const v of adj[u]) {
      if (!dfs(v)) return false;
    }
    color[u] = 2;
    return true;
  };
  for (let u = 0; u < numCourses; u++) {
    if (color[u] === 0 && !dfs(u)) return false;
  }
  return true;
}

TypeScript · runnable

Trace

Kahn's on numCourses = 4, prerequisites = [[1,0], [2,0], [3,1], [3,2]]:

Graph (edges b → a):

0 → 1 → 3
0 → 2 → 3

step	queue	in-degrees	popped	action
init	[0]	[0,1,1,2]	0	start
1	[1,2]	[0,0,0,2]	1	pop 0, decrement 1 and 2
2	[2,3]	[0,0,0,1]	2	pop 1, decrement 3
3	[3]	[0,0,0,0]	3	pop 2, decrement 3
4	[]	[0,0,0,0]	4	pop 3, no outgoing

All 4 popped — no cycle — return true.

Edge cases

No prerequisites — every node has in-degree 0; all are popped trivially.
Self-loop — [a, a] gives a in-degree 1 with no way to decrement it. Correctly detected as a cycle.
Multiple components — Kahn's starts the queue with all in-degree-0 nodes, so disconnected DAGs work naturally.
Duplicate edges — increment in-degree per occurrence; matches what adj[b].push(a) does, so it's consistent.

Takeaway

Any "does a valid order exist?" question on constraints is a DAG question. Kahn's algorithm is the cleanest cycle detector because the same machinery also produces a topological order (#210). When you're asked just "is it possible?", Kahn's counts popped nodes; when you're asked "give me one valid order", Kahn's records the pop sequence. Same algorithm, different output.

Medium#210

Course Schedule II

Topological sort — output the ordering, not just detect cycles.

Medium#133

Clone Graph

BFS/DFS with a visited HashMap that maps old → new nodes.

Hard#127

Word Ladder

BFS on an implicit graph. Each word is a node, edges connect words differing by one letter.