Module 3 — Thuật toán đồ thị: BFS, DFS, Dijkstra, MST

TL;DR: Module 3 dạy graph algorithms — nền tảng của hàng loạt bài toán thực tế: tìm đường ngắn nhất (GPS routing), phát hiện chu trình (Maven dependency), sắp xếp thứ tự build (topo sort), kết nối tối ưu (MST cáp mạng), và gom nhóm quan hệ (Union-Find). Bạn sẽ đi từ cách lưu đồ thị trong bộ nhớ, qua BFS/DFS, đến Dijkstra/Bellman-Ford/Floyd-Warshall, Kruskal/Prim, Disjoint Set Union, và kết thúc bằng hai case study production: Maven reactor build và Google Maps routing dưới 10ms.

Vì sao module này tồn tại

Graph không phải thứ xa lạ chỉ có trong đề thi. Mỗi khi bạn chạy mvn package, Maven đang tính topological sort trên DAG dependency để quyết định thứ tự compile. Mỗi khi Google Maps tìm đường, nó chạy Dijkstra kết hợp Contraction Hierarchy trên graph 100 triệu cạnh. Mỗi khi bạn dùng Git, DAG commit đang được traverse để merge branch.

Vấn đề là graph algorithms dễ bị học theo kiểu "thuộc công thức" mà không hiểu cơ chế — dẫn đến không biết chọn BFS hay DFS, không biết Dijkstra tại sao không dùng được khi có trọng số âm, không biết Union-Find làm gì mà nhanh đến vậy. Module này giải thích từng cơ chế từ gốc, kèm bài toán thực tế chứng minh khi nào dùng cái nào.

Sau module này bạn sẽ

• Implement BFS / DFS và áp dụng cho shortest-path không trọng số, cycle detection, topo sort
• Compare Dijkstra, Bellman-Ford, Floyd-Warshall theo trọng số âm, số đỉnh/cạnh và bài toán
• Explain Union-Find với path compression / union by rank và độ phức tạp α(n)
• Design giải pháp đồ thị cho hệ thống thật (routing Google Maps, dependency Maven, MST)

Bản đồ module

flowchart LR
    A["00\nTổng quan"] --> B["01\nRepresentation"]
    B --> C["02\nBFS"]
    C --> D["03\nDFS"]
    D --> E["04\nTopo Sort"]
    E --> F["05\nDijkstra"]
    F --> G["06\nBellman-Ford"]
    G --> H["07\nFloyd-Warshall"]
    H --> I["08\nMST\nKruskal+Prim"]
    I --> J["09\nUnion-Find\nDSU"]
    J --> K["10\nMini Challenge\nMaze BFS"]
    K --> L["11\nCase Study\nMaven+Maps"]
    L --> M["12\nTổng kết"]

Lộ trình học

Thứ tự bài được xây theo nguyên tắc "nền trước, ứng dụng sau":

Bài 01 — Graph representation là điểm xuất phát bắt buộc: adjacency list vs adjacency matrix. Mọi algorithm sau đều dùng một trong hai cấu trúc này — không hiểu representation là không debug được complexity.

Bài 02 — BFS là traversal cơ bản nhất: duyệt theo tầng (level-order), tìm shortest path không trọng số, phát hiện connected component. BFS cũng là backbone của bidirectional search ở bài case study.

Bài 03 — DFS bổ sung hướng khác: duyệt sâu trước, phát hiện cycle (back edge), topo sort qua DFS, và strongly connected component. DFS ít hiển nhiên hơn BFS nhưng mạnh hơn cho các bài toán có cấu trúc đệ quy.

Bài 04 — Topological sort là ứng dụng trực tiếp của DFS và BFS (Kahn) trên DAG — thứ tự build Maven, thứ tự thực thi task, detect circular import trong compiler.

Bài 05 — Dijkstra mở ra bài toán shortest path có trọng số không âm: relaxation, MinHeap priority queue, và tại sao greedy hoạt động đúng. Nền tảng để hiểu Contraction Hierarchy ở bài 11.

Bài 06 — Bellman-Ford là bổ sung cho Dijkstra: chạy được khi có trọng số âm, detect negative cycle (currency arbitrage). Chậm hơn nhưng tổng quát hơn.

Bài 07 — Floyd-Warshall giải quyết all-pairs shortest path bằng DP 3 vòng lặp: đơn giản hơn chạy Dijkstra N lần, phù hợp khi V nhỏ và cần khoảng cách giữa mọi cặp đỉnh.

Bài 08 — MST (Kruskal + Prim) tìm cây khung nhỏ nhất: tối ưu cáp mạng, đường truyền datacenter. Kruskal dùng DSU (bài 09); Prim dùng MinHeap giống Dijkstra.

Bài 09 — Disjoint Set Union (Union-Find) là cấu trúc dữ liệu phụ trợ xuất hiện trong Kruskal, network connectivity, và gom nhóm: path compression + union by rank cho độ phức tạp gần O(1) mỗi thao tác.

Bài 10 — Mini Challenge: Maze BFS là bài thực hành tổng hợp BFS trên grid — pattern phổ biến trong phỏng vấn và game pathfinding.

Bài 11 — Case Study: Maven + Google Maps dive vào hai hệ thống production: topo sort trong Maven reactor và CH + bidirectional Dijkstra trong Google Maps routing dưới 10ms.

Bài 12 — Tổng kết gom cheat sheet, bảng chọn thuật toán, glossary và self-assessment.

Yêu cầu trước khi bắt đầu

• Đã hoàn thành Module 1 (Tìm kiếm nhanh) và Module 2 (Sắp xếp) trong khoá này — đặc biệt hiểu Binary Heap (dùng trong Dijkstra) và khái niệm complexity O(n log n).
• Nắm vững đệ quy — DFS dùng đệ quy hoặc stack tường minh; không thoải mái với đệ quy thì đọc lại khoá Cơ bản trước.
• Không cần biết graph trước — bài 01 dạy từ đầu.

Time budget

Cách học module này hiệu quả

• Vẽ tay trước khi code. Với mọi algorithm, cầm bút vẽ đồ thị nhỏ 5-6 đỉnh và trace tay từng bước trước khi đọc pseudocode. Graph algorithm rất trực quan khi nhìn — không rõ khi chỉ đọc chữ.
• Bám bảng dist/parent. Dijkstra và Bellman-Ford đều xoay quanh bảng dist[] và parent[]. Mỗi lần relaxation, cập nhật bảng tay — bạn sẽ thấy tại sao greedy hoạt động.
• Phân biệt WHEN, không chỉ HOW. Có 4 thuật toán shortest path (BFS không trọng số, Dijkstra, Bellman-Ford, Floyd-Warshall) — hiểu khi nào dùng cái nào còn quan trọng hơn biết code cái nào. Bảng chọn ở bài 12.
• Liên hệ bài toán thật. Mỗi lần học một algorithm, tự hỏi "cái này giải quyết bài toán nào trong công việc?" — câu trả lời ở bài 11 case study, nhưng tự suy trước sẽ nhớ lâu hơn.

Bài tiếp theo: Graph representation — Adjacency list vs matrix