Đường đi & quan hệ — Graph algorithms

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

BFS, DFS, Dijkstra, Bellman-Ford, Floyd-Warshall, MST, DSU — tất cả đồ thị trong một module. Từ representation đến case study Maven DAG và Google Maps routing.

Graph representation — Adjacency list vs matrix, trade-off bộ nhớ

Adjacency list hay matrix ảnh hưởng RAM và time complexity mỗi op. So sánh 3 representation, pseudocode, rule of thumb cho social network, road map, dependency graph.

BFS — Breadth-First Search và unweighted shortest path

BFS duyệt theo lớp, đảm bảo shortest path unweighted O(V+E). Queue mechanics, level tracking, parent reconstruction, multi-source BFS, pattern system design hay gặp.

DFS — Depth-First Search, preorder/postorder, cycle detection

DFS đi sâu từng nhánh — recursive và iterative, white/gray/black coloring phát hiện cycle, preorder vs postorder, connected components, pattern hay gặp trong production.

Topological sort — Kahn (BFS-based) vs DFS-based, build order DAG

Kahn BFS-based và DFS reverse postorder — hai algorithm topo sort, cycle detection, multiple valid order, và pattern Maven/Gradle/npm/Excel/job scheduler dùng hàng ngày.

Dijkstra — Shortest path trên weighted graph với min-heap

Dijkstra tìm shortest path weighted graph: relaxation, min-heap lazy deletion O((V+E) log V), fail với edge âm — pattern Google Maps và OSPF routing áp dụng.

Bellman-Ford — Negative weight, detect negative cycle

Bellman-Ford xử lý edge âm — V-1 iteration relax mọi edge, detect negative cycle bằng V-th iteration. RIP routing và forex arbitrage detector đều dùng thuật toán này.

Floyd-Warshall — All-pairs shortest path qua DP-on-graph

All-pairs shortest path — Floyd-Warshall: 3 nested loop O(V³), 5 dòng code, hỗ trợ negative edge, detect negative cycle. Dùng cho transitive closure và flight cost.

Minimum Spanning Tree — Kruskal vs Prim, cut property

MST: kết nối nhiều node chi phí tối thiểu không vòng lặp. Kruskal (sort edges + DSU) và Prim (MinHeap), cut property chứng minh correctness, khi nào chọn từng thuật toán.

Disjoint Set Union — Near-O(1) với path compression + union by rank

DSU dùng mảng parent[] đạt amortized O(α(n)) nhờ path compression + union by rank. Từ naive O(n²) lên gần hằng số, ứng dụng Kruskal MST, image segmentation, connectivity.

Mini-challenge — Maze solver: BFS shortest path + path reconstruction

Implement MazeSolver: BFS trên 2D grid tìm shortest path từ S đến E, dùng parent map reconstruct đường đi — pattern game pathfinding, robot navigation, LeetCode 1091.

Case Study: Maven DAG build order + Google Maps shortest path

Maven reactor build dùng DAG topo sort; Google Maps dùng Dijkstra, Contraction Hierarchy, bidirectional search. Dive source thật, lý do mỗi quyết định đúng cho scale.

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

Recap graph algorithms: bảng chọn thuật toán shortest-path, cheat sheet BFS/DFS/MST/DSU, glossary, 5 pitfall và self-assessment 4 câu.