Module 3 — Tổng kết & cheat sheet

TL;DR: Module 3 đi qua toàn bộ graph algorithms cốt lõi — từ representation đến BFS/DFS, topo sort, ba thuật toán shortest-path (Dijkstra, Bellman-Ford, Floyd-Warshall), MST (Kruskal + Prim), và Disjoint Set Union. Trang này là cheat sheet để bookmark: bảng chọn thuật toán theo bài toán, bảng so sánh shortest-path theo điều kiện trọng số và scale, glossary 15 thuật ngữ, 5 pitfall và self-assessment. Nếu bạn giải thích được khi nào dùng Dijkstra thay Bellman-Ford, hiểu tại sao DSU gần O(1), và biết design giải pháp graph cho bài toán thật — bạn đã sẵn sàng cho khoá tiếp theo.

Đã đi qua những gì

Bạn bắt đầu từ bài 00 — Tổng quan module: graph không phải cấu trúc xa lạ — Maven, Git, Google Maps đều chạy graph algorithm mỗi ngày.

Bài 01 — Graph representation đặt nền: adjacency list tốn O(V+E) space phù hợp sparse graph, adjacency matrix tốn O(V²) nhưng lookup O(1) phù hợp dense graph nhỏ. Choice sai ở đây có thể gây OOM trước khi algorithm chạy.

Bài 02 — BFS duyệt theo tầng: tìm shortest path không trọng số trong O(V+E), phát hiện connected component, là backbone của bidirectional search. Queue FIFO là điểm mấu chốt — thay queue bằng stack là thành DFS.

Bài 03 — DFS duyệt sâu trước: phát hiện cycle qua back edge, topological sort qua finish-time order, và strongly connected component (Kosaraju/Tarjan). Recursion stack hoặc explicit stack — hai cách implement tương đương.

Bài 04 — Topological sort là ứng dụng DFS/Kahn trên DAG: thứ tự build Maven, dependency resolution, detect circular import. Kahn BFS-based dễ detect cycle hơn (check order.size() != V).

Bài 05 — Dijkstra giải shortest path với trọng số không âm: relaxation + MinHeap cho O((V+E) log V). Greedy hoạt động vì một khi đỉnh settled, dist của nó đã tối ưu — điều này break khi có trọng số âm.

Bài 06 — Bellman-Ford tổng quát hơn: chạy được trọng số âm, detect negative cycle. Đánh đổi: O(VE) thay vì O((V+E) log V) — chậm hơn nhưng đúng hơn trong điều kiện khó.

Bài 07 — Floyd-Warshall giải all-pairs shortest path bằng DP 3 vòng lặp O(V³): đơn giản code, phù hợp V nhỏ (dưới vài trăm đỉnh), cho phép detect negative cycle qua diagonal âm.

Bài 08 — MST (Kruskal + Prim) tìm cây khung chi phí tối thiểu: Kruskal sort cạnh + DSU cho sparse graph, Prim MinHeap-based cho dense graph. Ứng dụng: cáp mạng datacenter, đường truyền tối ưu.

Bài 09 — Disjoint Set Union cấu trúc gom nhóm gần O(1): path compression rút phẳng cây về root, union by rank giữ cây thấp. Kết hợp hai kỹ thuật cho độ phức tạp O(α(n)) — hàm Ackermann nghịch đảo, tăng cực kỳ chậm.

Bài 10 — Mini Challenge: Maze BFS thực hành BFS trên grid 2D: mỗi ô là đỉnh, 4 hướng là cạnh, tìm đường ngắn nhất từ S đến E.

Bài 11 — Case Study: Maven + Google Maps dive sâu hai hệ thống production: Maven dùng Kahn topo sort để quyết định build order (cycle → CycleDetectedException), Google Maps dùng Dijkstra + Contraction Hierarchy + bidirectional search để routing dưới 10ms trên graph 100 triệu cạnh — nhanh hơn Dijkstra naive khoảng 40.000 lần.

🗺️ Cheat sheet

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

Bảng chọn thuật toán shortest-path

MST — Kruskal vs Prim

DSU — path compression + union by rank

function find(x):
    if parent[x] != x:
        parent[x] <- find(parent[x])   -- path compression: rút phẳng về root
    return parent[x]

function union(x, y):
    rx <- find(x)
    ry <- find(y)
    if rx = ry: return false           -- cùng nhóm, không union
    if rank[rx] < rank[ry]:            -- union by rank: gắn cây thấp vào cây cao
        swap(rx, ry)
    parent[ry] <- rx
    if rank[rx] = rank[ry]: rank[rx] <- rank[rx] + 1
    return true

// Time: O(α(n)) mỗi thao tác  Space: O(n)
// α(n) = hàm Ackermann nghịch đảo, thực tế ≤ 4 với mọi n hợp lý

Algorithm vs production use case

📖 Glossary module

⚠️ Pitfall tổng hợp

Pitfall 1 — Dùng Dijkstra khi có trọng số âm. Dijkstra greedy assume rằng một khi đỉnh settled, dist của nó đã tối ưu. Với trọng số âm, assumption này sai — một đường đi dài hơn có thể rẻ hơn nhờ cạnh âm sau đó. Kết quả: dist sai hoàn toàn mà không có thông báo lỗi. Fix: dùng Bellman-Ford hoặc Johnson's algorithm.

Pitfall 2 — Quên khởi tạo visited dẫn đến BFS/DFS vô hạn trên đồ thị có chu trình. BFS/DFS trên undirected graph nếu không đánh dấu visited trước khi thêm vào queue/stack sẽ thêm cùng một đỉnh nhiều lần — queue phình ra, memory hết, hoặc vòng lặp vô hạn. Fix: mark visited ngay khi enqueue (BFS) hoặc ngay khi gọi DFS, không phải khi xử lý.

Pitfall 3 — Nhầm Kruskal O(E log E) với O(E log V) — thực ra giống nhau nhưng sort cạnh mới là bottleneck. Nhiều người nghĩ DSU là bottleneck của Kruskal. Thực ra DSU O(α(n)) gần như O(1) — bottleneck là sort E cạnh, O(E log E). Vì E ≤ V², nên log E ≤ 2 log V, do đó O(E log E) = O(E log V). Với sparse graph (E ~ V), Kruskal nhanh hơn Prim.

Pitfall 4 — Floyd-Warshall khởi tạo sai dist[i][i]. dist[i][i] phải là 0 (đứng yên không tốn chi phí), không phải vô cực. Nếu khởi tạo sai, mọi path đi qua i sẽ tính sai. Ngoài ra, detect negative cycle bằng cách check dist[i][i] < 0 sau khi chạy xong — nếu âm, có negative cycle đi qua i.

Pitfall 5 — DSU forget path compression làm thao tác chậm từ O(α(n)) xuống O(log n) hoặc O(n). DSU không có path compression vẫn đúng kết quả nhưng chậm hơn đáng kể — cây có thể bị unbalanced, find() phải đi lên từng bước. Với Kruskal trên graph triệu cạnh, difference giữa O(α(n)) và O(log n) rất rõ. Luôn implement cả path compression lẫn union by rank.

✅ Self-assessment

Bạn đã đạt module này nếu trả lời được:

• Implement được BFS và DFS, áp dụng cho shortest-path không trọng số, cycle detection và topological sort — viết pseudocode từ đầu không cần nhìn tài liệu.
  • Nếu chưa: đọc lại bài 02 (BFS, mục queue walkthrough), bài 03 (DFS, mục back edge), bài 04 (topo sort).
• Compare được Dijkstra, Bellman-Ford, Floyd-Warshall — giải thích khi nào dùng cái nào dựa trên trọng số âm, scale (V/E), và single-source vs all-pairs.
  • Nếu chưa: đọc lại bài 05 (Dijkstra, mục tại sao greedy đúng), bài 06 (Bellman-Ford, mục negative weight), bài 07 (Floyd-Warshall, mục so sánh).
• Explain được Union-Find với path compression và union by rank — tại sao kết hợp hai kỹ thuật cho O(α(n)), và α(n) có nghĩa gì thực tế.
  • Nếu chưa: đọc lại bài 09 (DSU, mục cơ chế bên dưới và amortized analysis).
• Design được giải pháp đồ thị cho bài toán thật — cho một hệ thống (routing, dependency, MST), chọn đúng algorithm và lý giải được tradeoff.
  • Nếu chưa: đọc lại bài 11 (case study Maven + Google Maps) và bảng "Algorithm vs production use case" ở trên.

🚀 What's next

Module 3 là bài cuối của khoá Thuật toán Cốt lõi (tier 2 trong lộ trình thuật toán). Bạn đã hoàn thành nền tảng: data structure nâng cao, tìm kiếm nhanh, sắp xếp, và graph algorithms.

Khoá tiếp theo là Thuật toán Ứng dụng (tier 3) — đào sâu các kỹ thuật giải bài toán phức tạp hơn: Dynamic Programming (overlapping subproblems, optimal substructure), String algorithms (KMP, Rabin-Karp, Suffix Array), và Big Data algorithms (Bloom Filter, Count-Min Sketch, HyperLogLog). Khoá này đang trong quá trình phát triển.

📚 Tài liệu mở rộng

• Sách: Introduction to Algorithms (CLRS) — Cormen, Leiserson, Rivest, Stein. Chapters 22-25 bao trọn mọi graph algorithm trong module này với proof đầy đủ. Chapter 22 (BFS/DFS) và 24 (Dijkstra/Bellman-Ford) là tham khảo chuẩn.
• Sách: Algorithm Design — Jon Kleinberg, Éva Tardos. Chapter 3 (Graph traversal) và 4 (Greedy — Dijkstra, MST) trình bày theo hướng "tại sao đúng" thay vì chỉ "cách làm".
• Visualizer: VisuAlgo — Graph — animation BFS, DFS, Dijkstra, Bellman-Ford, Floyd-Warshall, MST tương tác. Dùng khi cần xem từng bước algorithm chạy.
• Paper: "Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks" — Geisberger et al. (2008). Kỹ thuật core của Google Maps routing — đọc section 3 (node contraction) sau khi hiểu Dijkstra vững.
• Paper: "Shortest Paths in Digraphs of Small Treewidth" — Chaudhuri & Zaroliagis (ICALP 1995, Algorithmica) — đào sâu hơn về routing optimization nếu muốn hiểu tại sao CH hiệu quả trên road network.

Bài tiếp theo: Thuật toán Ứng dụng — DP, String, Big Data