Algorithms & Applications
Trang chủ / Module 9
🕸️ Module 9 / 14 · 1 tuần

Đồ 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.

GraphBFSDFS
📌 Vì sao module này quan trọng

Đồ 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ễnKhông gianKiểm tra 2 node có cạnh nốiPhù hợp khi
Adjacency ListO(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 MatrixO(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

Giải bài toán Dependency Resolution

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

✅ 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