lthieu's notes

09-Graph-DFS-BFS

16 min read

Buổi 09 — Graph: DFS & BFS

Navigation

← 08-Tree-DFS-BFS | → 10-Heap Giai đoạn: Big Tech Foundation | Độ khó: ⭐⭐⭐

1. Analogy & Context

Graph = Bản đồ thành phố với các con đường

Hãy tưởng tượng bạn đang khám phá một thành phố lạ:

  • Nodes = các địa điểm (nhà hàng, trường học, công viên)
  • Edges = các con đường nối giữa chúng
  • Directed edge = đường một chiều
  • Undirected edge = đường hai chiều

DFS = Explorer tham vọng Chọn một con phố và đi thẳng, không quay đầu. Khi gặp ngõ cụt, mới backtrack và thử con đường khác. Có thể đi rất xa trước khi khám phá được khu vực lân cận.

BFS = Sóng nước lan ra từ điểm ném đá Từ điểm xuất phát, sóng lan ra theo vòng tròn đồng tâm — tất cả địa điểm cách 1 bước được thăm trước, rồi 2 bước, rồi 3 bước. Đây là lý do BFS đảm bảo tìm đường ngắn nhất trong unweighted graph.

Graph vs Tree

Tree là một trường hợp đặc biệt của graph: directed, acyclic, connected, có đúng 1 root. Graph tổng quát hơn: có thể có cycles, disconnected components, undirected edges.

Context thực tế:

  • Social network: Facebook friends graph, Twitter follower graph
  • Navigation: Google Maps tìm đường ngắn nhất (Dijkstra’s = BFS với weights)
  • Dependency resolution: npm packages, Docker build layers — cần topological sort
  • Web crawling: Google spider crawls URLs — BFS from seed URLs
  • Recommendation systems: “Friends of friends” suggestions

2. The FAANG Standard

Graph = Khả năng model hóa bài toán thực tế

FAANG interviewer không chỉ test algorithm — họ test khả năng nhận ra rằng bài toán là một graph problem và model nó đúng cách.

Những gì FAANG interviewer mong đợi:

Kỹ năngMức độ quan trọngGhi chú
DFS/BFS traversal⭐⭐⭐⭐⭐Cả iterative và recursive
Grid as implicit graph⭐⭐⭐⭐⭐Number of Islands pattern
Cycle detection⭐⭐⭐⭐⭐Directed graph — topological sort
Topological Sort⭐⭐⭐⭐⭐Course Schedule — classic L5
Shortest path unweighted⭐⭐⭐⭐BFS guarantees shortest
Connected components⭐⭐⭐⭐Union-Find hoặc DFS
Bipartite graph check⭐⭐⭐Graph coloring
Dijkstra’s (weighted)⭐⭐⭐L5/L6, dùng priority queue

L4 expectation: BFS/DFS, number of islands, cycle detection trong 25 phút.

L5 expectation: Topological sort, shortest path, nhận biết ẩn graph từ bài toán không rõ ràng là graph.

3. Visual Thinking (Mermaid)

3.1 Adjacency List vs Adjacency Matrix

graph LR
    subgraph List["Adjacency List — Recommended"]
        direction TB
        L0["0: [1, 2]"]
        L1["1: [0, 3]"]
        L2["2: [0, 4]"]
        L3["3: [1]"]
        L4["4: [2]"]
    end

    subgraph Graph["Actual Graph"]
        direction TB
        N0((0)) --- N1((1))
        N0((0)) --- N2((2))
        N1((1)) --- N3((3))
        N2((2)) --- N4((4))
    end

    subgraph Matrix["Adjacency Matrix — Dense graphs only"]
        direction TB
        M["  0 1 2 3 4<br/>0[0 1 1 0 0]<br/>1[1 0 0 1 0]<br/>2[1 0 0 0 1]<br/>3[0 1 0 0 0]<br/>4[0 0 1 0 0]"]
    end

3.2 BFS Shortest Path với khoảng cách

flowchart TD
    subgraph BFS_Levels["BFS từ Node 0 — khoảng cách"]
        A["Node 0 — dist: 0"]
        B["Node 1 — dist: 1"]
        C["Node 2 — dist: 1"]
        D["Node 3 — dist: 2"]
        E["Node 4 — dist: 2"]
        F["Node 5 — dist: 3"]

        A --> B
        A --> C
        B --> D
        C --> E
        D --> F
    end

    subgraph Queue_State["Queue states"]
        Q0["Init: [0]"]
        Q1["After 0: [1, 2]"]
        Q2["After 1,2: [3, 4]"]
        Q3["After 3,4: [5]"]
    end

3.3 Topological Sort — DAG với dependencies

graph LR
    A["Course A<br/>(no prereq)"]
    B["Course B<br/>(needs A)"]
    C["Course C<br/>(needs A)"]
    D["Course D<br/>(needs B, C)"]
    E["Course E<br/>(needs D)"]

    A --> B
    A --> C
    B --> D
    C --> D
    D --> E

    style A fill:#27ae60,color:#fff
    style E fill:#e74c3c,color:#fff

Topological order: A → B → C → D → E (hoặc A → C → B → D → E) Nếu có cycle trong graph → topological sort không tồn tại

4. TypeScript Template

4.1 Graph Representation — Adjacency List

// Undirected graph
function buildUndirectedGraph(n: number, edges: number[][]): Map<number, number[]> {
  const graph = new Map<number, number[]>();
 
  for (let i = 0; i < n; i++) {
    graph.set(i, []);
  }
 
  for (const [u, v] of edges) {
    graph.get(u)!.push(v);
    graph.get(v)!.push(u); // Undirected: cả hai chiều
  }
 
  return graph;
}
 
// Directed graph
function buildDirectedGraph(n: number, edges: number[][]): Map<number, number[]> {
  const graph = new Map<number, number[]>();
 
  for (let i = 0; i < n; i++) {
    graph.set(i, []);
  }
 
  for (const [u, v] of edges) {
    graph.get(u)!.push(v); // Chỉ một chiều
  }
 
  return graph;
}

4.2 DFS — Iterative (Explicit Stack) và Recursive

// DFS Recursive — Clean và dễ hiểu
function dfsRecursive(
  graph: Map<number, number[]>,
  start: number
): number[] {
  const visited = new Set<number>();
  const result: number[] = [];
 
  function dfs(node: number): void {
    visited.add(node);
    result.push(node);
 
    for (const neighbor of graph.get(node) || []) {
      if (!visited.has(neighbor)) {
        dfs(neighbor);
      }
    }
  }
 
  dfs(start);
  return result;
}
 
// DFS Iterative — Dùng khi graph quá sâu (stack overflow risk với recursive)
function dfsIterative(
  graph: Map<number, number[]>,
  start: number
): number[] {
  const visited = new Set<number>();
  const stack: number[] = [start];
  const result: number[] = [];
 
  while (stack.length > 0) {
    const node = stack.pop()!;
 
    if (visited.has(node)) continue; // Skip nếu đã visited
    visited.add(node);
    result.push(node);
 
    for (const neighbor of graph.get(node) || []) {
      if (!visited.has(neighbor)) {
        stack.push(neighbor);
      }
    }
  }
 
  return result;
}

Recursive vs Iterative DFS

  • Recursive: cleaner code, nhưng risk stack overflow với graph rất sâu (>10,000 nodes)
  • Iterative: dùng explicit stack trên heap → không bị stack overflow
  • Trong interview, recursive thường được chấp nhận trừ khi đề bài cảnh báo về input size lớn

4.3 BFS — Shortest Path trong Unweighted Graph

function bfsShortestPath(
  graph: Map<number, number[]>,
  start: number,
  end: number
): number {
  if (start === end) return 0;
 
  const visited = new Set<number>([start]);
  const queue: number[] = [start];
  let head = 0; // Index pointer — O(1) dequeue (xem 03-Stack-and-Queue § Pitfall 2)
  let distance = 0;
 
  while (head < queue.length) {
    const levelSize = queue.length - head;
    distance++;
 
    for (let i = 0; i < levelSize; i++) {
      const node = queue[head++];
 
      for (const neighbor of graph.get(node) || []) {
        if (neighbor === end) return distance;
 
        if (!visited.has(neighbor)) {
          visited.add(neighbor);
          queue.push(neighbor);
        }
      }
    }
  }
 
  return -1; // Không tìm thấy đường
}

Tại sao BFS đảm bảo shortest path?

BFS khám phá theo vòng tròn đồng tâm từ source. Node nào được thăm đầu tiên, đó là đường ngắn nhất. Với unweighted graph, mỗi edge có weight = 1, nên “số bước” = “tổng weight”.

4.4 numIslands — Grid as Implicit Graph

// Grid = implicit graph: mỗi cell là 1 node, 4 neighbors là các edge
function numIslands(grid: string[][]): number {
  if (!grid || grid.length === 0) return 0;
 
  const rows = grid.length;
  const cols = grid[0].length;
  let count = 0;
 
  // DFS để "sink" một island (mark visited bằng cách đổi '1' → '0')
  function dfs(r: number, c: number): void {
    // Boundary checks và water/visited check
    if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] !== '1') {
      return;
    }
 
    grid[r][c] = '0'; // Mark as visited (sink the island)
 
    dfs(r + 1, c); // Down
    dfs(r - 1, c); // Up
    dfs(r, c + 1); // Right
    dfs(r, c - 1); // Left
  }
 
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === '1') {
        count++;
        dfs(r, c); // Sink entire island
      }
    }
  }
 
  return count;
}
 
// ===== COMPLEXITY =====
// Time: O(M * N) — visit each cell at most once
// Space: O(M * N) — recursion stack in worst case (all land)

Grid Pattern — Rất phổ biến trong FAANG

Nhiều bài “không rõ ràng là graph” thực ra là grid problems: Flood Fill, Walls and Gates, Rotten Oranges, Pacific Atlantic Water Flow. Pattern chung: 4-directional DFS/BFS, check bounds trước khi access.

4.5 canFinish — Cycle Detection cho Topological Sort

// LeetCode #207: Course Schedule
// Có thể hoàn thành tất cả n courses không? (có prerequisite)
// Tương đương: graph có cycle không?
 
function canFinish(numCourses: number, prerequisites: number[][]): boolean {
  // Build adjacency list
  const graph = new Map<number, number[]>();
  for (let i = 0; i < numCourses; i++) graph.set(i, []);
  for (const [course, prereq] of prerequisites) {
    graph.get(prereq)!.push(course);
  }
 
  // 0 = unvisited, 1 = visiting (in current DFS path), 2 = visited (done)
  const state = new Array(numCourses).fill(0);
 
  function hasCycle(node: number): boolean {
    if (state[node] === 1) return true;  // Cycle detected!
    if (state[node] === 2) return false; // Already fully processed
 
    state[node] = 1; // Mark as "being visited"
 
    for (const neighbor of graph.get(node) || []) {
      if (hasCycle(neighbor)) return true;
    }
 
    state[node] = 2; // Mark as "fully visited"
    return false;
  }
 
  // Check all nodes (graph có thể disconnected)
  for (let i = 0; i < numCourses; i++) {
    if (hasCycle(i)) return false;
  }
 
  return true;
}

3 states trong cycle detection — không được dùng boolean visited

  • 0 = chưa thăm
  • 1 = đang thăm (trong DFS call stack hiện tại) — nếu gặp lại node này → cycle!
  • 2 = đã thăm xong (toàn bộ subtree đã được explore)

Nếu chỉ dùng boolean visited, sẽ không phân biệt được “đang trong DFS path” vs “đã xử lý xong” → false positive cycles.

4.6 Topological Sort — Kahn’s Algorithm (BFS-based)

// Kahn's Algorithm: BFS, dùng in-degree
// Thích hợp hơn DFS-based vì dễ detect cycle và code cleaner
 
function topologicalSort(numCourses: number, prerequisites: number[][]): number[] {
  const graph = new Map<number, number[]>();
  const inDegree = new Array(numCourses).fill(0);
 
  for (let i = 0; i < numCourses; i++) graph.set(i, []);
 
  for (const [course, prereq] of prerequisites) {
    graph.get(prereq)!.push(course);
    inDegree[course]++;
  }
 
  // Start with nodes that have no prerequisites (in-degree = 0)
  const queue: number[] = [];
  for (let i = 0; i < numCourses; i++) {
    if (inDegree[i] === 0) queue.push(i);
  }
 
  const order: number[] = [];
  let head = 0; // Index pointer (O(1) dequeue)
 
  while (head < queue.length) {
    const node = queue[head++];
    order.push(node);
 
    for (const neighbor of graph.get(node) || []) {
      inDegree[neighbor]--;
      if (inDegree[neighbor] === 0) {
        queue.push(neighbor); // Tất cả prerequisites đã được hoàn thành
      }
    }
  }
 
  // Nếu order.length < numCourses → có cycle → không thể sort
  return order.length === numCourses ? order : [];
}
 
// ===== COMPLEXITY =====
// Time: O(V + E) — process each node and edge once
// Space: O(V + E) — graph + queue + inDegree array

4.7 cloneGraph

class GraphNode {
  val: number;
  neighbors: GraphNode[];
  constructor(val: number = 0, neighbors: GraphNode[] = []) {
    this.val = val;
    this.neighbors = neighbors;
  }
}
 
function cloneGraph(node: GraphNode | null): GraphNode | null {
  if (!node) return null;
 
  // Map từ original node → cloned node
  const cloned = new Map<GraphNode, GraphNode>();
 
  function dfs(original: GraphNode): GraphNode {
    if (cloned.has(original)) return cloned.get(original)!;
 
    const clone = new GraphNode(original.val);
    cloned.set(original, clone); // Phải set TRƯỚC khi recurse để handle cycles
 
    for (const neighbor of original.neighbors) {
      clone.neighbors.push(dfs(neighbor));
    }
 
    return clone;
  }
 
  return dfs(node);
}

cloneGraph — Xử lý Cycle

Phải thêm node vào map trước khi recurse vào neighbors. Nếu không, cycle trong graph sẽ gây infinite recursion.

5. Complexity Deep-dive

DFS và BFS

OperationTimeSpaceGhi chú
DFSV = nodes, E = edges
BFSQueue chứa tối đa V nodes
Topological SortPhải build adjacency list
Cycle Detection3-state DFS
Shortest Path (unweighted)BFS

Adjacency List vs Adjacency Matrix

Adjacency ListAdjacency Matrix
Space
Add edge
Check edge (u, v)
Iterate neighbors
Khi dùngSparse graphs (hầu hết)Dense graphs ()

Hầu hết FAANG interview problems dùng sparse graphs

(ví dụ: social networks — mỗi người có vài trăm friends, không phải N million friends). Adjacency list là lựa chọn mặc định.

6. Edge Cases & Pitfalls

Quên đánh dấu visited → Infinite Loop 

// WRONG: gây infinite loop nếu graph có cycle
function dfs(node: number): void {
  for (const neighbor of graph.get(node) || []) {
    dfs(neighbor); // Không check visited!
  }
}
 
// CORRECT: check visited trước khi recurse
function dfs(node: number): void {
  visited.add(node); // Mark BEFORE processing neighbors
  for (const neighbor of graph.get(node) || []) {
    if (!visited.has(neighbor)) dfs(neighbor);
  }
}

Disconnected Graph — Outer Loop bắt buộc 

// WRONG: chỉ start DFS từ node 0 → bỏ sót các connected components khác
dfs(0);
 
// CORRECT: loop qua tất cả nodes
for (let i = 0; i < n; i++) {
  if (!visited.has(i)) dfs(i); // Start new DFS from each unvisited node
}

Grid: Check Bounds TRƯỚC khi Access 

// WRONG: crash nếu r hoặc c out of bounds
if (grid[r][c] !== '1') return;
 
// CORRECT: bounds check trước
if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] !== '1') return;

Directed vs Undirected — Build Adjacency List khác nhau

  • Undirected: thêm edge cả hai chiều u → v VÀ v → u
  • Directed: chỉ thêm một chiều u → v
  • Đây là lỗi phổ biến khi code vội — luôn đọc kỹ đề

Visited: Set vs boolean[]

  • boolean[]: nhanh hơn, nhưng chỉ dùng được khi nodes là integers từ 0 đến n-1
  • Set<number>: linh hoạt hơn, dùng được với bất kỳ node type nào
  • Set<string>: dùng khi nodes là strings (word ladder, grid coordinates)

7. Pattern Recognition

Khi thấy những từ khóa này → nghĩ đến Graph DFS/BFS:

Từ khóa trong đềPattern
”number of islands / components”DFS/BFS, outer loop for disconnected
”shortest path” (unweighted)BFS — guarantees shortest
”cycle detection”3-state DFS hoặc Union-Find
”topological order” / “dependencies”Kahn’s algorithm (BFS) hoặc DFS postorder
”course schedule” / “prerequisites”Topological sort + cycle detection
”word ladder” / “transform one word”BFS, từng node là 1 word
”clone graph”DFS + HashMap (original → clone)
“flood fill” / “pacific atlantic”Multi-source BFS/DFS
”bipartite graph”Graph coloring, 2-state DFS
”rotten oranges”Multi-source BFS

"Grid" problems = Implicit Graph

Khi thấy grid với directions (up/down/left/right), đó là graph problem với implicit adjacency list. Pattern chuẩn:

const directions = [[0,1],[0,-1],[1,0],[-1,0]]; // 4-directional
for (const [dr, dc] of directions) {
  const nr = r + dr, nc = c + dc;
  if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) {
    // Process neighbor
  }
}

8. Top LeetCode Problems

Danh sách theo thứ tự học

#ProblemDifficultyKỹ năng cầnGhi chú
LC-200 #200Number of IslandsMediumDFS/BFS on gridClassic, must-solve
LC-695 #695Max Area of IslandMediumDFS, return valueVariation of Islands
LC-207 #207Course ScheduleMediumCycle detectionMust-know
LC-210 #210Course Schedule IIMediumTopological sortReturn actual order
LC-417 #417Pacific Atlantic Water FlowMediumMulti-source BFSClever reverse thinking
LC-133 #133Clone GraphMediumDFS + HashMapHandle cycles
LC-994 #994Rotting OrangesMediumMulti-source BFSClassic BFS
LC-127 #127Word LadderHardBFS, word transformsHard — need optimization
LC-269 #269Alien DictionaryHardTopological sortBuild graph from words

Complete Solution: #127 Word Ladder

Problem Statement

Cho beginWord, endWord, và một wordList. Tìm shortest transformation sequence từ beginWord đến endWord, mỗi bước chỉ thay đổi một chữ cái, và mỗi từ trung gian phải nằm trong wordList. Trả về độ dài của sequence ngắn nhất (0 nếu không tồn tại).

Tại sao đây là BFS?

  • Cần shortest path → BFS
  • Mỗi “edge” là một single-character transformation
  • Graph: nodes = words, edges = words differ by 1 character

Naive approach: — compare every pair of words Optimized approach: Pattern matching — *ot, h*t, ho* để group words

function ladderLength(beginWord: string, endWord: string, wordList: string[]): number {
  const wordSet = new Set(wordList);
 
  if (!wordSet.has(endWord)) return 0;
 
  const L = beginWord.length;
 
  // Build adjacency list using pattern matching
  // "hot" → ["*ot", "h*t", "ho*"] (L patterns per word)
  // Nhóm các words có cùng pattern lại → họ là neighbors của nhau
  const patternMap = new Map<string, string[]>();
 
  function addToPattern(word: string): void {
    for (let i = 0; i < L; i++) {
      const pattern = word.slice(0, i) + '*' + word.slice(i + 1);
      if (!patternMap.has(pattern)) patternMap.set(pattern, []);
      patternMap.get(pattern)!.push(word);
    }
  }
 
  addToPattern(beginWord);
  for (const word of wordSet) {
    addToPattern(word);
  }
 
  // BFS from beginWord
  const visited = new Set<string>([beginWord]);
  const queue: string[] = [beginWord];
  let head = 0; // Index pointer (O(1) dequeue)
  let steps = 1; // beginWord itself counts as step 1
 
  while (head < queue.length) {
    const levelSize = queue.length - head;
    steps++;
 
    for (let i = 0; i < levelSize; i++) {
      const word = queue[head++];
 
      // Generate all L patterns for current word
      for (let j = 0; j < L; j++) {
        const pattern = word.slice(0, j) + '*' + word.slice(j + 1);
 
        for (const neighbor of patternMap.get(pattern) || []) {
          if (neighbor === endWord) return steps;
 
          if (!visited.has(neighbor)) {
            visited.add(neighbor);
            queue.push(neighbor);
          }
        }
      }
    }
  }
 
  return 0; // No path found
}
 
// ===== TEST CASES =====
// beginWord = "hit", endWord = "cog"
// wordList = ["hot","dot","dog","lot","log","cog"]
// hit → hot → dot → dog → cog = 5 steps
 
// beginWord = "hit", endWord = "cog"
// wordList = ["hot","dot","dog","lot","log"] (no "cog")
// → return 0
 
// ===== COMPLEXITY =====
// N = số words trong wordList, L = độ dài mỗi word
// Time: O(N * L²) — N words, L patterns per word, L chars per pattern
// Space: O(N * L²) — patternMap stores all patterns
 
// ===== FOLLOW-UP: Bidirectional BFS =====
// Có thể optimize thêm bằng bidirectional BFS:
// BFS từ cả beginWord VÀ endWord đồng thời, dừng khi hai fronts gặp nhau
// Giảm từ O(b^d) → O(b^(d/2)) trong practice, b = branching factor, d = depth

Bidirectional BFS — Optimization nâng cao

Khi interviewer hỏi “làm sao optimize hơn nữa?”, đề xuất bidirectional BFS: mở rộng từ cả hai đầu (beginWord và endWord) đồng thời, luôn expand phía có frontier nhỏ hơn. Giảm complexity đáng kể trong practice.

9. Self-Assessment Checklist

Kiểm tra kiến thức của bạn

Graph Fundamentals:

  • Giải thích sự khác biệt giữa directed và undirected graph
  • Viết code build adjacency list từ edge list trong 3 phút
  • Biết khi nào dùng adjacency list vs adjacency matrix

DFS:

  • Viết DFS recursive với visited set
  • Viết DFS iterative với explicit stack
  • Handle disconnected graph với outer loop
  • Giải thích tại sao cần 3 states trong cycle detection (không phải boolean)

BFS:

  • Viết BFS trả về shortest path
  • Giải thích tại sao BFS đảm bảo shortest path trong unweighted graph
  • Implement multi-source BFS (Rotten Oranges pattern)

Topological Sort:

  • Viết được Kahn’s algorithm từ đầu
  • Giải thích mối liên hệ giữa cycle và impossibility của topological sort
  • Áp dụng được vào Course Schedule problem

Grid as Graph:

  • Nhận ra grid problems là implicit graph problems
  • Viết 4-directional BFS/DFS với proper bounds checking
  • Tránh được lỗi bounds access trước khi check

Pattern Recognition:

  • Nhìn đề “shortest path” → nghĩ BFS ngay
  • Nhìn đề “dependencies / prerequisites” → nghĩ topological sort
  • Nhìn đề “number of components” → nghĩ DFS + outer loop

Tags: dsa graph dfs bfs topological-sort cycle-detection faang algorithm Liên quan: 08-Tree-DFS-BFS | 10-Heap | MOC-DSA-Mastery

Graph View

Backlinks