Module Đồ thị — Tổng kết & cheat sheet

TL;DR: Module Đồ thị đi qua các thuật toán đồ thị cốt lõi: cách lưu graph, BFS/DFS, topo sort, ba thuật toán đường ngắn nhất (Dijkstra, Bellman-Ford, Floyd-Warshall), MST (Kruskal + Prim) và Disjoint Set Union. Trang này là cheat sheet để bạn lưu lại tra cứu: bảng chọn thuật toán theo bài toán, bảng so sánh các thuật toán đường ngắn nhất theo trọng số và quy mô, glossary 15 thuật ngữ, 5 bẫy thường gặp và phần tự đánh giá. Nếu bạn giải thích được khi nào dùng Dijkstra thay Bellman-Ford, hiểu vì sao DSU gần O(1), và biết thiết kế giải pháp đồ thị 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ạ, vì Maven, Git, Google Maps đều chạy thuật toán đồ thị mỗi ngày.

Bài 01 — Graph representation đặt nền: adjacency list tốn O(V+E) bộ nhớ, hợp với sparse graph (graph thưa); adjacency matrix tốn O(V²) nhưng tra cạnh O(1), hợp với dense graph (graph dày) nhỏ. Chọn sai ở đây có thể làm hết bộ nhớ (OOM) trước cả khi thuật toán 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 thứ tự lúc rời đỉnh (finish time), và strongly connected component (Kosaraju/Tarjan). Dùng đệ quy hay tự dựng stack đều được, hai cách cho cùng kết quả.

Bài 04 — Topological sort là ứng dụng DFS/Kahn trên DAG: thứ tự build Maven, dependency resolution, detect circular import. Kahn (dựa trên BFS) phát hiện cycle dễ hơn: chỉ cần kiểm tra 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 chạy đúng vì một khi đỉnh đã được chốt (settled), dist của nó là tối ưu, và điều này không còn đúng khi có trọng số âm.

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

Bài 07 — Floyd-Warshall giải all-pairs shortest path bằng DP 3 vòng lặp O(V³): code đơn giản, hợp khi V nhỏ (dưới vài trăm đỉnh), và phát hiện được negative cycle qua đường chéo âm của ma trận.

Bài 08 — MST (Kruskal + Prim) tìm cây khung có tổng chi phí nhỏ nhất: Kruskal sort cạnh rồi dùng DSU, hợp với sparse graph; Prim dùng MinHeap, hợp với dense graph. Ứng dụng: kéo cáp mạng datacenter, đường truyền tối ưu.

Bài 09 — Disjoint Set Union là cấu trúc gom nhóm gần O(1): path compression kéo cây dẹt 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)), với α là hàm ngược Ackermann, 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 + routing bản đồ đi sâu vào hai hệ thống chạy thật: Maven sắp xếp topo các module bằng DFS để quyết định thứ tự build (có cycle thì dừng với CycleDetectedException), còn routing quy mô bản đồ dùng Contraction Hierarchy + bidirectional search, nhanh hơn Dijkstra thường hàng chục nghìn lần theo các bài báo học thuật (Google không công bố chi tiết routing của Google Maps).

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: kéo dẹt 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 ngược Ackermann, thực tế ≤ 4 với mọi n hợp lý

Algorithm vs production use case

Glossary module

Bẫy tổng hợp

Bẫy 1: Dùng Dijkstra khi có trọng số âm. Dijkstra (greedy) giả định rằng một khi đỉnh đã được chốt thì dist của nó là tối ưu. Với trọng số âm, giả định này sai: một đường dài hơn có thể rẻ hơn nhờ cạnh âm đi sau. Kết quả là dist sai hoàn toàn mà không có thông báo lỗi nào. Cách sửa: dùng Bellman-Ford (single-source), hoặc thuật toán Johnson cho all-pairs.

Bẫy 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 graph có chu trình mà không đánh dấu visited trước khi đưa đỉnh vào queue/stack sẽ thêm cùng một đỉnh nhiều lần: queue phình ra, hết bộ nhớ, hoặc lặp vô hạn. Cách sửa: đánh dấu visited ngay lúc enqueue (BFS) hoặc ngay lúc gọi DFS, không đợi đến lúc xử lý.

Bẫy 3: Tưởng DSU là chỗ chậm nhất của Kruskal. DSU O(α(n)) gần như O(1); chỗ chậm nhất là sort E cạnh, O(E log E). Vì E ≤ V², nên log E ≤ 2 log V, nên O(E log E) = O(E log V): hai cách viết này bằng nhau. Với sparse graph (E ~ V), Kruskal và Prim cùng bậc.

Bẫy 4: Floyd-Warshall khởi tạo sai dist[i][i]. dist[i][i] phải là 0 (đứng yên thì không tốn chi phí), không phải vô cực. Khởi tạo sai thì mọi đường đi qua i đều tính sai. Ngoài ra, phát hiện negative cycle bằng cách kiểm tra dist[i][i] < 0 sau khi chạy xong: nếu âm thì có negative cycle đi qua i.

Bẫy 5: DSU quên 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 cho kết quả đúng, nhưng find() phải đi lên từng bước: còn union by rank thì O(log n), mất cả hai thì có thể tới O(n). Hãy cài cả path compression lẫn union by rank.

Tự kiểm tra

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 mà 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 thuật toán và giải thích được đánh đổi.
  • 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.

Bài tiếp theo

Module Đồ thị là module 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 đã đi qua data structure nâng cao, tìm kiếm nhanh, sắp xếp và graph algorithm.

Khoá tiếp theo là Thuật toán Ứng dụng (tier 3), dạy cách giải bài toán phức tạp hơn. Bốn module đầu đã có: quyết định tối ưu (Dynamic Programming, greedy, backtracking), string matching (KMP, Rabin-Karp), big data và streaming (Bloom Filter, Count-Min Sketch, HyperLogLog), thuật toán phân tán. Các module hình học, search engine và crypto sắp ra mắt.

Tài liệu mở rộng

• Sách: Introduction to Algorithms (CLRS) — Cormen, Leiserson, Rivest, Stein. Chapters 21-25 (ấn bản 3) bao trọn các thuật toán 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 — BFS/DFS, đường ngắn nhất, MST — animation 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 nền của nhiều engine routing (như OSRM) — đọc phần node contraction sau khi hiểu Dijkstra vững.

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