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

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

Adjacency list hay adjacency matrix — choice ảnh hưởng RAM và time complexity từng operation. Bài này so sánh 3 representation chính, code Java cho từng cái, và rule of thumb cho social network, road map, dependency graph.

BFS — Breadth-First Search và unweighted shortest path

BFS duyệt graph theo từng lớp và đảm bảo tìm shortest path trên unweighted graph trong O(V+E). Bài này giải thích queue mechanics, level tracking, distance + parent reconstruction, multi-source BFS, và pattern hay gặp trong system design.

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

BFS đi rộng từng level, DFS đi sâu từng nhánh. Bài này giải thích DFS recursive và iterative, white/gray/black coloring cho cycle detection, preorder vs postorder traversal, connected components, và 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 PriorityQueue

BFS tìm shortest path trên unweighted graph, nhưng Google Maps cần đường ngắn nhất theo thời gian di chuyển — weighted graph. Bài này dạy Dijkstra: relaxation principle, PriorityQueue lazy deletion O((V+E) log V), vì sao FAIL với edge âm, và pattern Google Maps / OSPF routing dùng.

Bellman-Ford — Negative weight, detect negative cycle

Dijkstra fail với edge âm — currency arbitrage, forex graph cần algorithm khác. Bài này dạy Bellman-Ford: V-1 iteration relax mọi edge, detect negative cycle bằng V-th iteration, và tại sao RIP routing protocol cùng forex arbitrage detector đều dùng nó.

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

Dijkstra/Bellman-Ford tìm shortest path từ 1 source. Nếu cần shortest path giữa mọi cặp vertex — transitive closure, social network, flight all-pairs cost — Floyd-Warshall giải bằng 3 nested loop O(V³), 5 dòng code, hỗ trợ negative edge, và detect negative cycle.

Minimum Spanning Tree — Kruskal vs Prim, cut property

Kết nối 100 datacenter với chi phí tối thiểu, không vòng lặp — đó là bài toán MST. Bài này dạy Kruskal (sort edges + Disjoint Set Union) và Prim (grow tree với PriorityQueue), cut property chứng minh correctness, và khi nào chọn thuật toán nào.

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

DSU là cấu trúc chỉ dùng một mảng parent[] nhưng đạt amortized O(α(n)) — gần như hằng số — nhờ hai optimization: path compression và union by rank. Bài này dạy từ naive O(n²) lên optimized α(n), code Java đầy đủ, và ứng dụng trong Kruskal MST, image segmentation, network 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, kết hợp parent map để reconstruct đường đi — pattern dùng trong game pathfinding, robot navigation, và LeetCode 1091.

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

Module 5 đã đi qua 10 graph algorithm. Bài này dive 2 system production thực tế: Maven 3.x reactor build với DAG topo sort và Google Maps routing pipeline — Dijkstra, Contraction Hierarchy, bidirectional search. Đọc source thật, hiểu vì sao mỗi quyết định đúng cho scale.