Graph
BFS, DFS, Dijkstra, MST

11.1 Graph Terminology

• Vertex (V): đỉnh / node
• Edge (E): cạnh, kết nối 2 vertex
• Directed: cạnh có hướng (vd Twitter: A follow B ≠ B follow A)
• Undirected: cạnh 2 chiều (vd Facebook friend)
• Weighted: cạnh có trọng số (vd khoảng cách, thời gian, chi phí)
• Cycle: đường đi quay về điểm xuất phát
• DAG: Directed Acyclic Graph — đồ thị có hướng không cycle
• Connected component: tập vertex liên thông với nhau
• Tree: connected acyclic undirected graph với V vertex và V-1 edge

11.2 Biểu diễn Graph trong code

11.2.1 Adjacency List (phổ biến nhất)

// Mảng/Map: vertex → list các neighbor
const graph = {
  'A': ['B', 'C'],
  'B': ['A', 'D'],
  'C': ['A', 'D'],
  'D': ['B', 'C']
};

// Hoặc dùng Map
const g = new Map();
g.set('A', ['B', 'C']);
// ...

// Với weighted graph: list các [neighbor, weight]
const wg = {
  'A': [['B', 4], ['C', 2]],
  'B': [['D', 5]],
  // ...
};

11.2.2 Adjacency Matrix

// Ma trận n×n: matrix[i][j] = 1 nếu có edge i→j
//                              0 nếu không
//                              weight nếu weighted

const matrix = [
  [0, 1, 1, 0],  // A
  [1, 0, 0, 1],  // B
  [1, 0, 0, 1],  // C
  [0, 1, 1, 0],  // D
];

So sánh

Quy tắc: sparse graph (ít edge) → list. Dense graph (nhiều edge gần V²) → matrix.

11.3 BFS — Breadth-First Search

BFS thăm các vertex theo "lớp" — bắt đầu từ start, thăm tất cả neighbor (depth 1), rồi tất cả depth 2, ...

function bfs(graph, start) {
  const visited = new Set([start]);
  const queue = [start];
  const result = [];
  while (queue.length) {
    const node = queue.shift();
    result.push(node);
    for (const neighbor of graph[node] || []) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
  return result;
}

Ứng dụng kinh điển: Shortest path trên unweighted graph

// Tìm khoảng cách ngắn nhất (số cạnh) từ start đến target
function shortestPath(graph, start, target) {
  const visited = new Set([start]);
  const queue = [[start, 0]];  // [node, distance]
  while (queue.length) {
    const [node, dist] = queue.shift();
    if (node === target) return dist;
    for (const neighbor of graph[node] || []) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push([neighbor, dist + 1]);
      }
    }
  }
  return -1;
}

Bài: Number of Islands (LeetCode 200)

function numIslands(grid) {
  const m = grid.length, n = grid[0].length;
  let count = 0;

  function bfs(r, c) {
    const queue = [[r, c]];
    grid[r][c] = '0';  // mark visited
    while (queue.length) {
      const [x, y] = queue.shift();
      for (const [dx, dy] of [[1,0],[-1,0],[0,1],[0,-1]]) {
        const nx = x + dx, ny = y + dy;
        if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] === '1') {
          grid[nx][ny] = '0';
          queue.push([nx, ny]);
        }
      }
    }
  }

  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      if (grid[r][c] === '1') {
        count++;
        bfs(r, c);
      }
    }
  }
  return count;
}

Multi-source BFS

Khi có nhiều điểm xuất phát, push tất cả vào queue ngay từ đầu.

// Bài "Rotting Oranges": orange thối lan ra ô liền kề mỗi phút.
// Tìm phút cuối khi tất cả orange thối.
function orangesRotting(grid) {
  const m = grid.length, n = grid[0].length;
  const queue = [];
  let fresh = 0;
  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      if (grid[r][c] === 2) queue.push([r, c, 0]);
      else if (grid[r][c] === 1) fresh++;
    }
  }
  let minutes = 0;
  while (queue.length) {
    const [r, c, t] = queue.shift();
    minutes = Math.max(minutes, t);
    for (const [dx, dy] of [[1,0],[-1,0],[0,1],[0,-1]]) {
      const nr = r + dx, nc = c + dy;
      if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] === 1) {
        grid[nr][nc] = 2;
        fresh--;
        queue.push([nr, nc, t + 1]);
      }
    }
  }
  return fresh === 0 ? minutes : -1;
}

11.4 DFS — Depth-First Search

DFS đi sâu vào một nhánh đến tận cùng trước khi quay lại thử nhánh khác.

// Recursive
function dfs(graph, start, visited = new Set()) {
  if (visited.has(start)) return;
  visited.add(start);
  console.log(start);  // hoặc collect
  for (const neighbor of graph[start] || []) {
    dfs(graph, neighbor, visited);
  }
}

// Iterative với stack
function dfsIter(graph, start) {
  const visited = new Set();
  const stack = [start];
  const result = [];
  while (stack.length) {
    const node = stack.pop();
    if (visited.has(node)) continue;
    visited.add(node);
    result.push(node);
    for (const neighbor of graph[node] || []) {
      if (!visited.has(neighbor)) stack.push(neighbor);
    }
  }
  return result;
}

BFS vs DFS — Khi nào dùng cái nào?

11.5 Cycle Detection

Undirected graph — DFS với parent

function hasCycleUndirected(graph) {
  const visited = new Set();

  function dfs(node, parent) {
    visited.add(node);
    for (const neighbor of graph[node] || []) {
      if (!visited.has(neighbor)) {
        if (dfs(neighbor, node)) return true;
      } else if (neighbor !== parent) {
        // Đã thăm + không phải parent → cycle
        return true;
      }
    }
    return false;
  }

  for (const node in graph) {
    if (!visited.has(node)) {
      if (dfs(node, null)) return true;
    }
  }
  return false;
}

Directed graph — DFS với 3 màu

// 0 = white (chưa thăm), 1 = gray (đang thăm), 2 = black (đã xong)
function hasCycleDirected(graph) {
  const color = {};
  for (const node in graph) color[node] = 0;

  function dfs(node) {
    color[node] = 1;  // gray
    for (const neighbor of graph[node] || []) {
      if (color[neighbor] === 1) return true;  // gặp gray → cycle
      if (color[neighbor] === 0 && dfs(neighbor)) return true;
    }
    color[node] = 2;  // black
    return false;
  }

  for (const node in graph) {
    if (color[node] === 0 && dfs(node)) return true;
  }
  return false;
}

Tại sao 3 màu? Trong undirected, gặp lại visited node mà không phải parent → cycle. Trong directed, không có "parent" rõ ràng → ta cần phân biệt "đang trên đường thăm hiện tại (gray)" và "đã thăm xong (black)". Gặp gray = cycle vì có đường quay lại trên cùng path DFS.

11.6 Topological Sort — sắp xếp theo dependency

Bài toán: cho DAG (directed acyclic graph), sắp xếp vertex sao cho với mọi edge u→v, u đứng trước v. Ứng dụng: build dependency, course schedule, task ordering.

Cách 1: Kahn's Algorithm (BFS-based)

function topoSortKahn(graph, n) {
  // Tính indegree
  const indegree = new Array(n).fill(0);
  for (const u in graph) {
    for (const v of graph[u]) indegree[v]++;
  }

  // Queue chứa node có indegree = 0
  const queue = [];
  for (let i = 0; i < n; i++) if (indegree[i] === 0) queue.push(i);

  const result = [];
  while (queue.length) {
    const node = queue.shift();
    result.push(node);
    for (const neighbor of graph[node] || []) {
      indegree[neighbor]--;
      if (indegree[neighbor] === 0) queue.push(neighbor);
    }
  }

  // Nếu không lấy hết = có cycle
  return result.length === n ? result : null;
}

Cách 2: DFS-based

function topoSortDFS(graph, n) {
  const visited = new Set();
  const stack = [];

  function dfs(node) {
    visited.add(node);
    for (const neighbor of graph[node] || []) {
      if (!visited.has(neighbor)) dfs(neighbor);
    }
    stack.push(node);  // post-order: thêm sau khi xong children
  }

  for (let i = 0; i < n; i++) {
    if (!visited.has(i)) dfs(i);
  }
  return stack.reverse();
}

Bài: Course Schedule (LeetCode 207)

// numCourses = n, prerequisites = [[a, b], ...] nghĩa là phải học b trước a
// Trả về true nếu có thể hoàn thành tất cả → DAG có topo sort hợp lệ → KHÔNG cycle
function canFinish(numCourses, prereq) {
  const graph = Array.from({length: numCourses}, () => []);
  const indegree = new Array(numCourses).fill(0);
  for (const [a, b] of prereq) {
    graph[b].push(a);
    indegree[a]++;
  }
  const queue = [];
  for (let i = 0; i < numCourses; i++) if (indegree[i] === 0) queue.push(i);

  let taken = 0;
  while (queue.length) {
    const c = queue.shift();
    taken++;
    for (const next of graph[c]) {
      if (--indegree[next] === 0) queue.push(next);
    }
  }
  return taken === numCourses;
}

11.7 Dijkstra — Shortest Path với non-negative weights

Tìm đường đi ngắn nhất từ source đến mọi vertex khác trên weighted graph với edge weight ≥ 0. Dùng Priority Queue (min-heap) — đây là tại sao chương 10 trước chương 11.

function dijkstra(graph, start) {
  const dist = {};
  for (const node in graph) dist[node] = Infinity;
  dist[start] = 0;

  // Priority Queue: min-heap theo distance
  const pq = new MinHeap((a, b) => a[1] - b[1]);
  pq.push([start, 0]);

  while (pq.size) {
    const [node, d] = pq.pop();
    if (d > dist[node]) continue;  // outdated entry

    for (const [neighbor, weight] of graph[node] || []) {
      const newDist = d + weight;
      if (newDist < dist[neighbor]) {
        dist[neighbor] = newDist;
        pq.push([neighbor, newDist]);
      }
    }
  }
  return dist;
}

// Big-O: O((V + E) log V) với heap
// O(V²) nếu không dùng heap

Tại sao Dijkstra KHÔNG chạy với negative weight?

Dijkstra giả định: một khi đã chốt distance cho 1 node (pop từ heap), không có cách nào ngắn hơn. Với negative weight, có thể "đi xa hơn rồi quay về với negative edge" cho ra distance ngắn hơn → giả định sai.

11.8 Bellman-Ford — chạy được với negative weight

Phát hiện negative cycle (edge weights tổng cộng ngược về < 0).

function bellmanFord(edges, n, source) {
  const dist = new Array(n).fill(Infinity);
  dist[source] = 0;

  // Relax tất cả edges V-1 lần
  for (let i = 0; i < n - 1; i++) {
    for (const [u, v, w] of edges) {
      if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
      }
    }
  }

  // Lần thứ V-th: nếu còn relax được → có negative cycle
  for (const [u, v, w] of edges) {
    if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
      return null;  // negative cycle
    }
  }
  return dist;
}
// Big-O: O(V × E)

11.9 Floyd-Warshall — All Pairs Shortest Path

Tính shortest path giữa mọi cặp vertex bằng DP. O(V³).

function floydWarshall(graph, n) {
  // Init: dist[i][j] = weight nếu có edge, 0 nếu i==j, Infinity nếu không
  const dist = Array.from({length: n}, () => new Array(n).fill(Infinity));
  for (let i = 0; i < n; i++) dist[i][i] = 0;
  for (const u in graph) {
    for (const [v, w] of graph[u]) dist[+u][v] = w;
  }

  // 3 vòng for: k = "intermediate"
  for (let k = 0; k < n; k++) {
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        if (dist[i][k] + dist[k][j] < dist[i][j]) {
          dist[i][j] = dist[i][k] + dist[k][j];
        }
      }
    }
  }
  return dist;
}

11.10 Union-Find (Disjoint Set Union)

Cấu trúc quản lý các tập hợp rời nhau, hỗ trợ 2 thao tác:

• find(x): tìm "đại diện" (root) của tập chứa x
• union(x, y): gộp tập chứa x với tập chứa y

Với 2 optimization (path compression + union by rank), cả hai gần như O(1) (chính xác là α(n) — hàm Ackerman ngược, gần như hằng số).

class UnionFind {
  constructor(n) {
    this.parent = Array.from({length: n}, (_, i) => i);
    this.rank = new Array(n).fill(0);
    this.count = n;  // số connected component
  }

  find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]);  // path compression
    }
    return this.parent[x];
  }

  union(x, y) {
    const rx = this.find(x), ry = this.find(y);
    if (rx === ry) return false;  // đã cùng tập
    // Union by rank: tập nhỏ gắn vào tập lớn
    if (this.rank[rx] < this.rank[ry]) {
      this.parent[rx] = ry;
    } else if (this.rank[rx] > this.rank[ry]) {
      this.parent[ry] = rx;
    } else {
      this.parent[ry] = rx;
      this.rank[rx]++;
    }
    this.count--;
    return true;
  }

  connected(x, y) { return this.find(x) === this.find(y); }
}

Ứng dụng

• Đếm connected components
• Phát hiện cycle trong undirected graph (khi union 2 vertex đã connected)
• Kruskal's MST
• Dynamic connectivity
• Account merging

11.11 Minimum Spanning Tree (MST)

Cho weighted undirected connected graph. MST = subset của edges tạo thành tree (V-1 edges, không cycle, connected) với tổng weight nhỏ nhất.

11.11.1 Kruskal's Algorithm — O(E log E) với Union-Find

function kruskal(n, edges) {
  // edges = [[u, v, w], ...]
  edges.sort((a, b) => a[2] - b[2]);  // sort theo weight tăng

  const uf = new UnionFind(n);
  const mst = [];
  let total = 0;
  for (const [u, v, w] of edges) {
    if (uf.union(u, v)) {  // chỉ thêm nếu không tạo cycle
      mst.push([u, v, w]);
      total += w;
      if (mst.length === n - 1) break;
    }
  }
  return {mst, total};
}

11.11.2 Prim's Algorithm — O(E log V) với heap

function prim(graph, start) {
  // graph: adjacency list {u: [[v, w], ...]}
  const visited = new Set([start]);
  const pq = new MinHeap((a, b) => a[2] - b[2]);  // [u, v, w]
  for (const [v, w] of graph[start] || []) pq.push([start, v, w]);

  const mst = [];
  let total = 0;
  while (pq.size && mst.length < Object.keys(graph).length - 1) {
    const [u, v, w] = pq.pop();
    if (visited.has(v)) continue;
    visited.add(v);
    mst.push([u, v, w]);
    total += w;
    for (const [next, weight] of graph[v] || []) {
      if (!visited.has(next)) pq.push([v, next, weight]);
    }
  }
  return {mst, total};
}

So sánh Kruskal vs Prim

Bài tập

Tổng kết chương 11

• ✅ Biểu diễn: Adjacency List (sparse) vs Matrix (dense)
• ✅ BFS = Queue: shortest path unweighted, level-order
• ✅ DFS = Stack/recursive: cycle detection, topo sort, backtracking
• ✅ Cycle: undirected (DFS + parent), directed (DFS + 3 màu)
• ✅ Topological sort: Kahn (BFS + indegree) hoặc DFS post-order reverse
• ✅ Dijkstra: shortest path non-negative — O((V+E) log V)
• ✅ Bellman-Ford: chạy được với weight âm + phát hiện negative cycle — O(VE)
• ✅ Floyd-Warshall: all-pairs shortest path — O(V³)
• ✅ Union-Find với path compression + union by rank ≈ O(1)
• ✅ MST: Kruskal (sort + UF) hoặc Prim (heap)