Đồ thị (Graph) cơ bản: BFS, DFS
Biểu diễn đồ thị, Breadth-First Search, Depth-First Search, và ứng dụng thực tế: dependency resolution, phát hiện chu trình.
Đồ thị mô hình hoá gần như mọi hệ thống có "quan hệ" giữa các thực thể: mạng xã hội (user-follow-user), dependency giữa các package/module, sơ đồ mạng máy tính, và chính Context Map đã học ở khoá Architecture (Module 4) — về bản chất cũng là 1 đồ thị. BFS/DFS là 2 thuật toán duyệt nền tảng cho mọi bài toán đồ thị phức tạp hơn.
🎯 Mục tiêu học tập
- Biểu diễn đồ thị bằng Adjacency List và Adjacency Matrix, chọn đúng cách theo tình huống
- Triển khai Breadth-First Search (BFS) và ứng dụng cho bài toán đường đi ngắn nhất (không trọng số)
- Triển khai Depth-First Search (DFS) và ứng dụng cho bài toán phát hiện chu trình
- Áp dụng Topological Sort để giải bài toán dependency resolution
Biểu diễn Đồ thị
| Cách biểu diễn | Không gian | Kiểm tra 2 node có cạnh nối | Phù hợp khi |
|---|---|---|---|
| Adjacency List | O(V + E) | O(degree) | Đồ thị thưa (sparse — ít cạnh so với số đỉnh) — trường hợp phổ biến nhất thực tế |
| Adjacency Matrix | O(V²) | O(1) | Đồ thị dày đặc (dense), hoặc cần kiểm tra cạnh cực nhanh |
# Adjacency List — cách phổ biến nhất trong thực tế
graph = {
"A": ["B", "C"],
"B": ["D"],
"C": ["D"],
"D": [],
}
Breadth-First Search (BFS) — duyệt theo từng "lớp"
from collections import deque
def bfs(graph: dict, start: str) -> list:
visited = {start}
queue = deque([start]) # dùng Queue (Module 2) — đúng bản chất FIFO của BFS
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return order
BFS duyệt theo từng "lớp khoảng cách" từ điểm xuất phát — đến node ở khoảng cách k trước khi đến bất kỳ node nào ở khoảng cách k+1. Tính chất này khiến BFS là thuật toán chuẩn cho đường đi ngắn nhất trên đồ thị không trọng số (số cạnh ít nhất) — node đầu tiên BFS chạm tới đích chính là đường đi ngắn nhất. Ứng dụng: tìm số bước kết nối ngắn nhất trong mạng xã hội ("6 độ kết nối"), giải mê cung, và là nền tảng khái niệm cho Dijkstra (Module 10, mở rộng cho đồ thị có trọng số).
Depth-First Search (DFS) — đi sâu nhất có thể trước
def dfs(graph: dict, start: str, visited: set = None) -> list:
if visited is None:
visited = set()
visited.add(start)
order = [start]
for neighbor in graph[start]:
if neighbor not in visited:
order.extend(dfs(graph, neighbor, visited))
return order
DFS đi sâu theo 1 nhánh đến cùng trước khi quay lại thử nhánh khác (dùng đệ quy — tận dụng Call Stack, hoặc Stack tường minh — Module 2). Ứng dụng: phát hiện chu trình (nếu gặp lại 1 node đang nằm trên đường đi hiện tại — không chỉ "đã thăm" mà "đang trong stack đệ quy" — có chu trình), duyệt cây thư mục/file system, và giải các bài toán cần khám phá triệt để 1 nhánh trước khi chuyển hướng (backtracking).
Topological Sort — giải bài toán Dependency Resolution
Với đồ thị có hướng, không chu trình (DAG — Directed Acyclic Graph), Topological Sort sắp xếp các node sao cho mọi cạnh đều đi từ node đứng trước đến node đứng sau trong thứ tự đó — chính xác là bài toán "task A phải hoàn thành trước task B" cần giải trong: thứ tự cài đặt package (package A phụ thuộc package B → cài B trước), thứ tự build các module trong dự án lớn, và thứ tự thực thi các bước trong pipeline CI/CD (liên hệ khoá DevOps Module 3) khi các bước có phụ thuộc lẫn nhau. Triển khai phổ biến nhất dùng DFS: chạy DFS, thêm node vào đầu kết quả sau khi đã xử lý xong toàn bộ node con của nó (post-order).
🏋️ Bài tập thực hành
Mô hình hoá 1 tập package giả định với quan hệ phụ thuộc (dùng Adjacency List). Triển khai Topological Sort để xác định đúng thứ tự cài đặt. Thêm 1 chu trình phụ thuộc giả định (A phụ thuộc B, B phụ thuộc A) và triển khai DFS để phát hiện và báo lỗi chu trình này, thay vì để chương trình chạy vào vòng lặp vô hạn.
📚 Tài nguyên học tập
-
VisuAlgo — Graph Traversal (BFS/DFS)Trực quan hoá tương tác BFS và DFSTool
✅ Tự đánh giá hoàn thành
- Chọn đúng Adjacency List hay Matrix theo mật độ đồ thị
- Triển khai đúng BFS và giải thích vì sao nó cho đường đi ngắn nhất không trọng số
- Triển khai đúng DFS và dùng nó để phát hiện chu trình
- Giải đúng 1 bài toán dependency resolution thực tế bằng Topological Sort