Bỏ qua đến nội dung chính
Mục lục

Thuật toán BFS và DFS trong Python: duyệt đồ thị

AIDev Team · duyệt: Nguyễn Việt Chung

Bài 10/20 · Chương 23

Cấu trúc dữ liệu và giải thuật

  • 10 phút
  • Trung cấp
  • Python 3.14
  • Cập nhật

BFS và DFS là hai cách đi qua mọi đỉnh của một đồ thị. BFS (tìm theo chiều rộng) đi hết các đỉnh gần trước, còn DFS (tìm theo chiều sâu) đi một nhánh tới tận cùng rồi mới quay lại. BFS còn cho bạn đường đi ít chặng nhất, ví dụ từ Ga Huế tới chùa Thiên Mụ trên bản đồ xe buýt.

Cần biết trước: hàng đợi, ngăn xếp và đệ quy.

Đồ thị và danh sách kề

Đồ thị gồm các đỉnh và các cạnh nối hai đỉnh. Ở bản đồ xe buýt, mỗi trạm là một đỉnh, mỗi chặng xe chạy thẳng giữa hai trạm là một cạnh. Cây nhị phân là một đồ thị đặc biệt: không có vòng, và mỗi nút có tối đa hai con. Đồ thị thường thì có vòng, như Ga Huế đi Đại Nội, sang Chợ Đông Ba, qua Vĩ Dạ rồi về lại Ga Huế.

Cách lưu đồ thị gọn nhất trong Python là danh sách kề: một dict mà mỗi khóa là một đỉnh, giá trị là list các đỉnh nối thẳng với nó, giống một dict lồng nhau chứa list.

python
ban_do = {"Ga Huế": ["Đại Nội", "Vĩ Dạ"], "Thiên Mụ": ["Đại Nội"],
    "Đại Nội": ["Ga Huế", "Chợ Đông Ba", "Thiên Mụ"],
    "Vĩ Dạ": ["Ga Huế", "Chợ Đông Ba"],
    "Chợ Đông Ba": ["Đại Nội", "Vĩ Dạ"]}
print(ban_do["Đại Nội"])
print(len(ban_do), "trạm")
so_chang = 0
for tram in ban_do:
    so_chang += len(ban_do[tram])
print(so_chang // 2, "chặng")
print("Thiên Mụ" in ban_do["Ga Huế"])

KẾT QUẢ

['Ga Huế', 'Chợ Đông Ba', 'Thiên Mụ']
5 trạm
5 chặng
False

Chặng nào cũng đi được cả hai chiều, nên mỗi chặng xuất hiện hai lần, một lần trong list của mỗi đầu. Vì vậy tổng độ dài các list là 10, chia đôi mới ra 5 chặng. Dòng cuối in False vì từ Ga Huế không có chặng chạy thẳng tới Thiên Mụ. Đổi ban_do["Ga Huế"] thành ban_do["Đại Nội"] rồi chạy lại: dòng cuối in True.

Thuật toán BFS: duyệt theo chiều rộng

BFS bắt đầu từ một đỉnh, cho nó vào một hàng đợi và một tập các đỉnh đã thăm, lưu bằng một set. Mỗi lượt, hàm lấy đỉnh ở đầu hàng ra, rồi xếp vào cuối hàng những đỉnh kề chưa thăm. Hàng đợi đi trước ra trước nên đỉnh gần luôn được lấy ra trước đỉnh xa. Tập đã thăm giúp mỗi đỉnh chỉ vào hàng một lần, kể cả khi đồ thị có vòng.

python
from collections import deque
ban_do = {"Ga Huế": ["Đại Nội", "Vĩ Dạ"], "Thiên Mụ": ["Đại Nội"],
    "Đại Nội": ["Ga Huế", "Chợ Đông Ba", "Thiên Mụ"],
    "Vĩ Dạ": ["Ga Huế", "Chợ Đông Ba"],
    "Chợ Đông Ba": ["Đại Nội", "Vĩ Dạ"]}
def bfs(ban_do, dau):
    da_tham, hang = {dau}, deque([dau])
    while hang:
        tram = hang.popleft()
        print(tram)
        for ke in ban_do[tram]:
            if ke not in da_tham:
                da_tham.add(ke)
                hang.append(ke)
bfs(ban_do, "Ga Huế")

KẾT QUẢ

Ga Huế
Đại Nội
Vĩ Dạ
Chợ Đông Ba
Thiên Mụ

Thứ tự in ra đi theo từng lớp: Ga Huế, rồi hai trạm cách nó một chặng là Đại Nội và Vĩ Dạ, rồi hai trạm cách hai chặng. Mỗi đỉnh vào hàng một lần, mỗi cạnh được xem hai lần, nên BFS tốn O(V + E) với V đỉnh, E cạnh. Đổi bfs(ban_do, "Ga Huế") thành bfs(ban_do, "Thiên Mụ") rồi chạy lại: dòng cuối in Vĩ Dạ.

Tìm đường đi ít chặng nhất bằng BFS

Lần đầu BFS gặp một đỉnh, nó đi tới đó bằng đường ít cạnh nhất, vì mọi đỉnh gần hơn đã được lấy ra trước. Muốn biết đường đi cụ thể, bạn cất kèm mỗi trạm list các trạm đã đi qua để tới nó.

python
from collections import deque
ban_do = {"Ga Huế": ["Đại Nội", "Vĩ Dạ"], "Thiên Mụ": ["Đại Nội"],
    "Đại Nội": ["Ga Huế", "Chợ Đông Ba", "Thiên Mụ"],
    "Vĩ Dạ": ["Ga Huế", "Chợ Đông Ba"],
    "Chợ Đông Ba": ["Đại Nội", "Vĩ Dạ"]}
duong, hang = {"Ga Huế": ["Ga Huế"]}, deque(["Ga Huế"])
while hang:
    tram = hang.popleft()
    for ke in ban_do[tram]:
        if ke not in duong:
            duong[ke] = duong[tram] + [ke]
            hang.append(ke)
print(duong["Thiên Mụ"])
print(len(duong["Thiên Mụ"]) - 1, "chặng")

KẾT QUẢ

['Ga Huế', 'Đại Nội', 'Thiên Mụ']
2 chặng

Đường của mỗi trạm mới là đường của trạm đang xét nối thêm chính nó. Số chặng bằng số trạm trên đường trừ một. Cách cất này dễ đọc nhưng chép lại cả list cho từng trạm. Đồ thị lớn thường chỉ cất trạm đứng ngay trước mỗi trạm, rồi lần ngược từ đích về gốc. Bản đồ có chặng dài ngắn khác nhau thì "ít chặng nhất" không còn là "ngắn nhất", và bạn cần hàng đợi ưu tiên của heapq.

Thuật toán DFS: duyệt theo chiều sâu

DFS đi từ một đỉnh sang đỉnh kề đầu tiên chưa thăm, rồi lại từ đó đi tiếp, chỉ quay lại khi hết đường. Cách viết ngắn nhất là đệ quy: thăm đỉnh, rồi gọi lại chính hàm cho từng đỉnh kề chưa thăm.

python
ban_do = {"Ga Huế": ["Đại Nội", "Vĩ Dạ"], "Thiên Mụ": ["Đại Nội"],
    "Đại Nội": ["Ga Huế", "Chợ Đông Ba", "Thiên Mụ"],
    "Vĩ Dạ": ["Ga Huế", "Chợ Đông Ba"],
    "Chợ Đông Ba": ["Đại Nội", "Vĩ Dạ"]}
def dfs(tram, da_tham):
    da_tham.add(tram)
    print(tram)
    for ke in ban_do[tram]:
        if ke not in da_tham:
            dfs(ke, da_tham)

dfs("Ga Huế", set())

KẾT QUẢ

Ga Huế
Đại Nội
Chợ Đông Ba
Vĩ Dạ
Thiên Mụ

Từ Đại Nội, DFS đi tiếp sang Chợ Đông Ba rồi Vĩ Dạ trước khi quay về thăm Thiên Mụ. Mỗi tầng đệ quy giữ một trạm trên đường đang đi. Python mặc định chỉ cho khoảng 1000 tầng, và trang này cũng vậy, nên một chuỗi vài nghìn trạm làm bản đệ quy báo RecursionError.

Bản dùng ngăn xếp không có giới hạn đó. Ngăn xếp vào sau ra trước, nên trạm vừa đẩy vào được thăm ngay, đúng kiểu đi sâu. List kề được đẩy theo thứ tự ngược để trạm đứng đầu list ra trước, cho cùng thứ tự với bản đệ quy.

python
ban_do = {"Ga Huế": ["Đại Nội", "Vĩ Dạ"], "Thiên Mụ": ["Đại Nội"],
    "Đại Nội": ["Ga Huế", "Chợ Đông Ba", "Thiên Mụ"],
    "Vĩ Dạ": ["Ga Huế", "Chợ Đông Ba"],
    "Chợ Đông Ba": ["Đại Nội", "Vĩ Dạ"]}
da_tham, ngan_xep = set(), ["Ga Huế"]
while ngan_xep:
    tram = ngan_xep.pop()
    if tram in da_tham:
        continue
    da_tham.add(tram)
    print(tram)
    ngan_xep.extend(ban_do[tram][::-1])

KẾT QUẢ

Ga Huế
Đại Nội
Chợ Đông Ba
Vĩ Dạ
Thiên Mụ

DFS cũng tốn O(V + E) và đi qua mọi trạm đi tới được, nhưng đường nó tìm thấy đầu tiên chưa chắc ít chặng nhất. Nó hợp khi bạn chỉ cần biết hai trạm có nối với nhau không, hay cần đi hết một nhánh, như dò lối thoát trong mê cung.

Kiểm tra nhanh

  1. Trong hàm bfs() của bài, nếu đổi hang.popleft() thành hang.pop() và gọi bfs(ban_do, "Ga Huế") thì trạm thứ hai được in ra là trạm nào?

    • Đại Nội
    • Vĩ Dạ
    • Chợ Đông Ba
  2. Những cách nào tạo được một tập đã thăm có lệnh add()?

    • set()
    • {}
    • {"Ga Huế"}
    • dict()
  3. Với ban_do = {"Ga Huế": ["Đại Nội"]}, lệnh nào báo KeyError?

    • print(ban_do["Ga Huế"])
    • print("Đại Nội" in ban_do["Ga Huế"])
    • print(ban_do["Đại Nội"])
  4. Trên bản đồ năm trạm của bài, đi từ Thiên Mụ tới Vĩ Dạ ít nhất mất bao nhiêu chặng?

    • 2
    • 3
    • 4
Đúng hết lần đầu +15 XP

Bài tập

Số chặng xe buýt ít nhất

Viết hàm so_chang_it_nhat(ban_do, di, den). ban_do là danh sách kề, mọi trạm đều là khóa. Hàm trả về số chặng ít nhất để đi từ trạm di tới trạm den:

  • di và den là cùng một trạm thì trả về 0.

  • Không có đường đi thì trả về -1.

Dùng BFS (hàng đợi deque như bài) và đừng sửa ban_do. Trình chấm có một bản đồ lưới 144 trạm, và dừng hàm nếu nó tra danh sách kề quá nhiều lần, như khi quên tập đã thăm.

Ví dụ: trên bản đồ năm trạm của bài, so_chang_it_nhat(ban_do, "Ga Huế", "Thiên Mụ") trả về 2.

Trả về: số chặng, một int.

python
from collections import deque

def so_chang_it_nhat(ban_do, di, den):
    pass  # Viết thân hàm thay cho dòng này

Tóm tắt

  • Đồ thị gồm đỉnh và cạnh, và danh sách kề lưu nó bằng một dict từ mỗi đỉnh tới list các đỉnh nối thẳng.

  • BFS dùng hàng đợi lấy ra bằng popleft() và một set đã thăm, đi qua đồ thị theo từng lớp.

  • Lần đầu BFS gặp một đỉnh là lúc nó đi bằng đường ít cạnh nhất.

  • DFS đi một nhánh tới tận cùng, viết bằng đệ quy hoặc bằng ngăn xếp, và bản đệ quy chịu giới hạn khoảng 1000 tầng.

  • Cả hai tốn O(V + E), và set rỗng tạo bằng set(), không bằng {}.

Câu hỏi thường gặp

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

Cần đường đi ít chặng nhất, hay các đỉnh xếp theo khoảng cách, thì dùng BFS. Chỉ cần biết hai đỉnh có nối nhau không, hay cần đi hết từng nhánh, thì DFS thường gọn hơn và tốn ít bộ nhớ hơn trên đồ thị rộng.

Đồ thị một chiều lưu thế nào?

Đồ thị một chiều thường được gọi là đồ thị có hướng. Nó vẫn dùng danh sách kề, nhưng chỉ ghi cạnh ở đỉnh xuất phát. Ví dụ tuyến xe chỉ chạy từ Ga Huế tới Đại Nội thì "Đại Nội" nằm trong list của "Ga Huế", còn list của "Đại Nội" không có "Ga Huế". Hai hàm BFS và DFS của bài chạy được không cần sửa.

Python có sẵn thư viện đồ thị không?

Thư viện chuẩn có module graphlib, chỉ để sắp thứ tự các việc phụ thuộc nhau (xem các kiểu dữ liệu của thư viện chuẩn). Các thư viện cài thêm như NetworkX có sẵn BFS, DFS và đường đi ngắn nhất. Tự viết vài dòng với dict và deque như bài này là đủ cho đồ thị vừa và nhỏ.

Chủ đề

thuật toán bfs

Bài này có hữu ích?

Hỏi đáp

Đang tải câu hỏi…

Tham vấn chuyên môn

Nguyễn Việt Chung

Nhà sáng lập AIDev và VietPlatform · Thạc sĩ AI MSE

  • Tốt nghiệp thủ khoa xuất sắc Thạc sĩ AI MSE.
  • Đồng sáng lập, CTO E-University, SVOnline: số hóa 10+ đại học, 40.000+ sinh viên.
  • Xây hệ thống AI cho doanh nghiệp tại VietPlatform.
Biên soạn: AIDev Team · Rà soát · Quy trình biên tập