Login

Đồ thị (graph) cơ bản: nút, cạnh và hai cách duyệt BFS, DFS

  • author-image

    Nguyễn Đình Cường

  • blog-tag
  • blog-comment 0 comment
  • created-date 09 Nov, 2026
blog-thumbnail

Mạng xã hội, bản đồ đường đi, hệ thống tàu điện: tất cả đều là các điểm được nối với nhau bằng đường. Trong khoa học máy tính, mô hình đó gọi là đồ thị, và nó giải quyết rất nhiều bài toán thực tế.

Đồ thị là gì?

Đồ thị (graph) gồm tập các đỉnh (vertex/node) và tập các cạnh (edge) nối các đỉnh với nhau. Một vài phân loại quan trọng:

  • Vô hướng: cạnh hai chiều, ví dụ quan hệ bạn bè.
  • Có hướng: cạnh một chiều, ví dụ A theo dõi B nhưng B không theo dõi A.
  • Có trọng số: cạnh mang giá trị như khoảng cách hay chi phí.

Cây thực ra là một trường hợp đặc biệt của đồ thị: liên thông và không có chu trình.

Cách lưu đồ thị

Hai cách phổ biến nhất:

  1. Ma trận kề: bảng hai chiều, ô [i][j] cho biết có cạnh từ i đến j. Kiểm tra cạnh nhanh nhưng tốn bộ nhớ với đồ thị thưa.
  2. Danh sách kề: với mỗi đỉnh, lưu danh sách các đỉnh kề nó. Tiết kiệm và hay dùng hơn.
do_thi = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "D"],
    "D": ["B", "C", "E"],
    "E": ["D"],
}

Duyệt theo chiều rộng (BFS)

BFS thăm các đỉnh theo từng "vòng": đầu tiên các đỉnh cách xuất phát 1 bước, rồi 2 bước... Nó dùng hàng đợi và tìm được đường đi ít cạnh nhất trong đồ thị không trọng số.

from collections import deque

def bfs(do_thi, bat_dau):
    da_tham = {bat_dau}
    hang = deque([bat_dau])
    thu_tu = []
    while hang:
        u = hang.popleft()
        thu_tu.append(u)
        for v in do_thi[u]:
            if v not in da_tham:
                da_tham.add(v)
                hang.append(v)
    return thu_tu

print(bfs(do_thi, "A"))   # ['A', 'B', 'C', 'D', 'E']

Duyệt theo chiều sâu (DFS)

DFS đi sâu hết mức theo một nhánh rồi mới quay lại. Có thể viết đệ quy (dùng ngăn xếp lời gọi) hoặc dùng stack tường minh.

def dfs(do_thi, u, da_tham=None):
    if da_tham is None:
        da_tham = set()
    da_tham.add(u)
    print(u, end=" ")
    for v in do_thi[u]:
        if v not in da_tham:
            dfs(do_thi, v, da_tham)

dfs(do_thi, "A")   # A B D C E

Tập da_tham rất quan trọng: nếu thiếu nó, chương trình sẽ đi vòng quanh chu trình mãi mãi.

Khi nào dùng BFS, khi nào dùng DFS?

Mục đíchGợi ý
Tìm đường ngắn nhất (ít bước)BFS
Kiểm tra hai đỉnh có liên thôngBFS hoặc DFS
Phát hiện chu trình, sắp xếp tô-pôDFS
Giải mê cung, thử mọi khả năng (quay lui)DFS

Ứng dụng đời thực

  • Gợi ý kết bạn: tìm "bạn của bạn".
  • Ứng dụng bản đồ: tìm đường, có thuật toán chuyên dụng cho đồ thị có trọng số như Dijkstra.
  • Quản lý phụ thuộc: thứ tự cài các gói phần mềm, thứ tự môn học tiên quyết.
  • Trò chơi: tìm đường cho nhân vật.

Ví dụ: tìm đường ngắn nhất trong mê cung

BFS cực kỳ hợp với bài toán lưới. Mê cung dưới đây dùng # cho tường, . cho đường đi:

from collections import deque

me_cung = ["..#.",
           ".##.",
           "....",
           "#..."]

def duong_ngan_nhat(luoi, bd, dich):
    h, w = len(luoi), len(luoi[0])
    hang = deque([(bd, 0)])
    da_tham = {bd}
    while hang:
        (r, c), d = hang.popleft()
        if (r, c) == dich:
            return d
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < h and 0 <= nc < w and luoi[nr][nc] == "." and (nr, nc) not in da_tham:
                da_tham.add((nr, nc))
                hang.append(((nr, nc), d + 1))
    return -1

print(duong_ngan_nhat(me_cung, (0, 0), (0, 3)))   # 7

Mỗi ô là một đỉnh, bốn ô kề là các cạnh. Vì BFS thăm theo từng lớp khoảng cách nên lần đầu chạm đích chính là đường ngắn nhất. Hãy thử thay đổi mê cung và xem kết quả.

Lỗi thường gặp khi làm việc với đồ thị

  1. Quên đánh dấu đã thăm nên chương trình lặp vô hạn trên đồ thị có chu trình.
  2. Đánh dấu muộn trong BFS. Nên đánh dấu ngay khi đưa vào hàng đợi, nếu không một đỉnh có thể bị thêm nhiều lần.
  3. Đồ thị vô hướng nhưng chỉ thêm một chiều của cạnh, khiến duyệt thiếu.
  4. Đồ thị không liên thông: chỉ duyệt từ một đỉnh sẽ bỏ sót các thành phần khác; cần lặp qua mọi đỉnh chưa thăm.

Bài tập: đếm số thành phần liên thông của một đồ thị, và đếm số "hòn đảo" trong lưới 0/1 (các ô 1 kề nhau tạo thành một đảo).

Kết luận

Đồ thị mô hình hóa mọi mối quan hệ, và chỉ cần hiểu danh sách kề cùng BFS, DFS là bạn đã giải được rất nhiều bài toán. Hãy thử mô hình hóa một bài toán quen thuộc như bản đồ lớp học hay mạng bạn bè thành đồ thị rồi tự duyệt nó.

Học xong lý thuyết, hãy thực hành thật nhiều; các bài giảng có bài tập trong khóa học codebem.com sẽ giúp bạn việc đó.

author_photo
Nguyễn Đình Cường

0 comment