Chuyển đến nội dung chính

DFS và BFS: Hai thuật toán duyệt đồ thị cơ bản

Khi một bài toán được mô hình hóa thành các đỉnh và các liên kết giữa chúng, câu hỏi đầu tiên thường là: làm thế nào đi qua các đỉnh một cách có hệ thống mà không bỏ sót hoặc lặp vô hạn? Từ nhu cầu đó hình thành hai chiến lược nền tảng của khoa học máy tính: duyệt theo chiều sâu (Depth-First Search - DFS) và duyệt theo chiều rộng (Breadth-First Search - BFS).

Hai thuật toán không chỉ dùng cho đồ thị. Chúng còn xuất hiện trong cây, mê cung, tìm đường, kiểm tra liên thông, phát hiện chu trình, phân tích phụ thuộc, trò chơi và nhiều bài toán tìm kiếm trạng thái.

Tóm tắt nội dung
DFS đi sâu trước: chọn một nhánh và tiếp tục cho đến khi không thể đi tiếp rồi mới quay lui.
BFS đi rộng trước: khám phá tất cả đỉnh gần nguồn trước rồi mới chuyển sang các mức xa hơn.
DFS thường gắn với stack, BFS gắn với queue; cả hai đều có độ phức tạp O(V + E) khi dùng danh sách kề.
DFS và BFS: hai chiến lược khám phá khác nhau Cùng một đồ thị, nhưng thứ tự duyệt phụ thuộc vào cấu trúc dữ liệu điều khiển. A B C D E F G DFS Đi sâu theo một nhánh A → B → D → E → C → F → G Cấu trúc: Stack BFS Đi theo từng mức A → B → C → D → E → F → G Cấu trúc: Queue DFS ưu tiên độ sâu; BFS ưu tiên khoảng cách theo số cạnh.
Trên cùng một đồ thị, DFS và BFS có thể thăm đủ các đỉnh nhưng tạo ra thứ tự duyệt khác nhau.

1. Bài toán ban đầu: làm thế nào khám phá một cấu trúc liên kết?

Trong nhiều bài toán, dữ liệu không nằm theo một dãy tuyến tính. Một thành phố nối với nhiều thành phố khác, một trang web liên kết tới nhiều trang, một người trong mạng xã hội có nhiều quan hệ, hoặc một trạng thái trò chơi có thể sinh ra nhiều trạng thái tiếp theo.

Cấu trúc tự nhiên để mô hình hóa những hệ thống này là đồ thị (graph). Một đồ thị gồm tập đỉnh V và tập cạnh E:

G = (V, E)

Khi đã có đồ thị, vấn đề cơ bản xuất hiện: bắt đầu từ một đỉnh, cần khám phá các đỉnh có thể đi tới như thế nào?

Một thuật toán duyệt tốt phải đáp ứng ba yêu cầu: biết đỉnh nào đã được thăm, quyết định đỉnh nào sẽ xử lý tiếp theo và không bị mắc kẹt trong chu trình.

Hai lựa chọn tự nhiên xuất hiện. Một là đi sâu nhất có thể rồi quay lại. Hai là khám phá mọi lựa chọn gần nhất trước rồi mới tiến xa hơn. Đây chính là hai tư tưởng của DFS và BFS.



2. DFS: đi sâu trước rồi quay lui

DFS bắt đầu tại một đỉnh, chọn một đỉnh kề chưa được thăm và tiếp tục đi sâu. Khi đến một đỉnh không còn đường mới, thuật toán quay về vị trí trước đó và thử nhánh khác.

Giả sử đồ thị có cấu trúc:

A → B, C
B → D, E
C → F, G

Nếu luôn chọn đỉnh bên trái trước, DFS có thể duyệt:

A → B → D → E → C → F → G

DFS phù hợp tự nhiên với ngăn xếp (stack). Đỉnh được đưa vào sau cùng sẽ được xử lý trước. Khi viết đệ quy, ngăn xếp lời gọi của chương trình tự đảm nhiệm vai trò này.

Python · DFS đệ quy 
graph = {
    "A": ["B", "C"],
    "B": ["D", "E"],
    "C": ["F", "G"],
    "D": [],
    "E": [],
    "F": [],
    "G": []
}

def dfs(graph, node, visited):
    # Đánh dấu đỉnh hiện tại đã được thăm
    visited.add(node)
    print(node, end=" ")

    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

visited = set()
dfs(graph, "A", visited)

Kết quả với thứ tự danh sách kề trên là:

A B D E C F G

Điểm quan trọng là thứ tự cụ thể có thể thay đổi nếu thứ tự các đỉnh kề thay đổi. Bản chất của DFS không phải một chuỗi cố định mà là chiến lược ưu tiên đi sâu.

3. BFS: khám phá đồ thị theo từng lớp

BFS bắt đầu tại đỉnh nguồn, trước hết thăm tất cả các đỉnh cách nguồn một cạnh. Sau đó thuật toán thăm các đỉnh cách nguồn hai cạnh, rồi ba cạnh và tiếp tục như vậy.

Với cùng đồ thị ở trên, BFS từ A cho thứ tự:

A → B → C → D → E → F → G

BFS cần một hàng đợi (queue). Đỉnh được thêm vào trước sẽ được xử lý trước. Đây là cơ chế bảo đảm các đỉnh ở mức gần nguồn được duyệt trước các đỉnh xa hơn.

Python · BFS bằng queue 
from collections import deque

def bfs(graph, start):
    visited = {start}
    queue = deque([start])

    while queue:
        node = queue.popleft()
        print(node, end=" ")

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

bfs(graph, "A")

Ở BFS, nên đánh dấu một đỉnh là đã thăm ngay khi đưa nó vào queue. Nếu chờ đến lúc lấy đỉnh ra mới đánh dấu, cùng một đỉnh có thể bị thêm vào queue nhiều lần khi có nhiều đường cùng dẫn tới nó.

4. Vì sao BFS tìm được đường đi ngắn nhất còn DFS thì không?

Đây là khác biệt quan trọng nhất khi lựa chọn thuật toán. Trên đồ thị không trọng số, BFS khám phá các đỉnh theo khoảng cách tăng dần tính bằng số cạnh.

Nếu một đỉnh t được BFS gặp lần đầu ở mức 3, điều đó có nghĩa tồn tại đường từ nguồn đến t gồm 3 cạnh và không có đường nào chỉ gồm 1 hoặc 2 cạnh. Nếu tồn tại, BFS đã phải phát hiện t ở một mức trước đó.

Vì vậy BFS có thể tính khoảng cách ngắn nhất:

distance[v] = distance[u] + 1

DFS không có tính chất này. Nó có thể đi rất sâu vào một nhánh dài trước khi phát hiện một đường ngắn hơn nằm ở nhánh khác.

Giới hạn cần nhớ: BFS chỉ bảo đảm đường đi ngắn nhất theo số cạnh khi các cạnh không có trọng số hoặc có cùng chi phí. Với đồ thị có trọng số tổng quát, cần các thuật toán như Dijkstra thay vì BFS thông thường.

5. Độ phức tạp và sự khác biệt thực tế

Nếu đồ thị được lưu bằng danh sách kề, cả DFS và BFS đều có thể thăm mỗi đỉnh một lần và kiểm tra mỗi cạnh một số lần hữu hạn. Vì vậy:

Thời gian = O(V + E)

Trong đó V là số đỉnh và E là số cạnh.

Khác biệt lớn thường nằm ở bộ nhớ. DFS cần lưu đường đi hiện tại và các nhánh chờ xử lý. BFS có thể phải giữ toàn bộ một lớp lớn của đồ thị trong queue.

Tiêu chí DFS BFS
Chiến lược Đi sâu trước Đi theo từng mức
Cấu trúc dữ liệu Stack hoặc đệ quy Queue
Đường ngắn nhất không trọng số Không bảo đảm Bảo đảm
Tìm kiếm theo nhánh sâu Phù hợp Không phải ưu thế chính
Rủi ro bộ nhớ Độ sâu quá lớn Một mức có quá nhiều đỉnh
Độ phức tạp O(V + E) O(V + E)

6. Từ duyệt đồ thị đến giải quyết bài toán thực tế

DFS đặc biệt phù hợp khi cần khám phá cấu trúc sâu hoặc cần quay lui. Một số ứng dụng điển hình gồm tìm các thành phần liên thông, kiểm tra chu trình, duyệt cây thư mục, sắp xếp topo trong đồ thị có hướng không chu trình và giải các bài toán backtracking.

Trong mê cung, DFS có thể chọn một hướng và tiếp tục cho đến ngõ cụt rồi quay lại. Nếu mục tiêu chỉ là tìm một đường đi, chiến lược này thường đơn giản và hiệu quả.

BFS lại phù hợp khi khoảng cách là yếu tố quan trọng. Nó được dùng để tìm đường ngắn nhất trong mê cung không trọng số, xác định số bước tối thiểu để chuyển từ trạng thái này sang trạng thái khác, tìm người cách một người dùng k bậc trong mạng xã hội hoặc lan truyền tín hiệu theo từng lớp.

Một cách nhìn rộng hơn là coi mỗi trạng thái như một đỉnh và mỗi hành động hợp lệ như một cạnh. Khi đó DFS và BFS trở thành công cụ tìm kiếm trên không gian trạng thái.

Ví dụ: tìm đường trong mê cung
Ô hiện tại → Sinh ô lân cận → Bỏ ô đã thăm → DFS hoặc BFS → Tìm đích

Nếu yêu cầu là “có đường tới đích hay không?”, cả DFS và BFS đều có thể trả lời. Nếu yêu cầu là “đường nào có ít bước nhất?”, BFS là lựa chọn tự nhiên hơn trên mê cung mà mỗi bước có cùng chi phí.

7. Chọn DFS hay BFS?

Không có thuật toán nào luôn tốt hơn. Việc lựa chọn phụ thuộc vào mục tiêu của bài toán và hình dạng của không gian tìm kiếm.

Nên ưu tiên DFS khi cần duyệt toàn bộ cấu trúc, phát hiện chu trình, thực hiện quay lui, phân tích quan hệ phụ thuộc hoặc khi lời giải có khả năng nằm sâu và không cần bảo đảm đường ngắn nhất.

Nên ưu tiên BFS khi cần khoảng cách tối thiểu theo số cạnh, tìm trạng thái gần nhất, duyệt dữ liệu theo từng mức hoặc cần biết một đỉnh cách nguồn bao nhiêu bước.

Trong cả hai trường hợp, tập visited là thành phần bắt buộc với đồ thị có chu trình. Nếu không đánh dấu đỉnh đã thăm, thuật toán có thể quay lại các đỉnh cũ vô hạn.

Kết luận

DFS và BFS xuất phát từ cùng một vấn đề cơ bản: làm thế nào khám phá có hệ thống một cấu trúc gồm nhiều trạng thái liên kết với nhau. Sự khác biệt chủ yếu nằm ở quyết định đỉnh nào được xử lý tiếp theo: DFS ưu tiên đỉnh sâu nhất đang chờ, còn BFS ưu tiên đỉnh được phát hiện sớm nhất.

Hiểu rõ stack, queue, tập visited và cách hai thuật toán mở rộng không gian tìm kiếm quan trọng hơn việc ghi nhớ code. Khi nắm được tư tưởng này, DFS và BFS trở thành nền tảng để tiếp cận các bài toán phức tạp hơn như tìm đường ngắn nhất, sắp xếp topo, phân tích liên thông, tìm kiếm trạng thái và nhiều thuật toán đồ thị nâng cao.

© The CS Note · THE CS NOTE

Nội dung gốc thuộc tác giả. Vui lòng không đăng lại toàn văn khi chưa được phép, trừ trường hợp pháp luật hoặc giấy phép áp dụng cho phép. Nội dung của bên thứ ba tuân theo quyền và giấy phép tương ứng.

Nguồn gốc: DFS và BFS: Hai thuật toán duyệt đồ thị cơ bản

Về trang chủ Về đầu bài
Labels:

Bài Đăng Phổ Biến

Bài toán tháp Hà nội

Trải nghiệm Tháp Hà Nội Kéo thả đĩa hoặc chạm vào các nút bên dưới để di chuyển. Bạn phải chuyển toàn bộ đĩa sang cột ngoài cùng bên phải (Cột 3) mà không đặt đĩa to lên đĩa nhỏ. Cột 1 Cột 2 Cột 3 Điều khiển & Chế độ Số lượng đĩa 4 Tốc độ máy giải ↪ Undo ↻ Chơi lại 🤖 Máy tự giải Thống kê ván chơi Nước đã đi 0 Thời gian 00:00 Tối thiểu cần 15 Kỷ lục của bạn - Lịch sử và Nguồn gốc Truyền thuyết Bài toán Tháp Hà Nội (hay Tháp Brahma) là một trò chơi xếp hình toán học kinh điển được giới thiệu lần đầu vào năm 1883 bởi nhà toán học người Pháp Édouard L...

Bài toán phân tích cảm xúc trong văn bản

Bài toán phân tích cảm xúc (sentiment analysis) là một bài toán NLP nhằm xác định thái độ hoặc cảm xúc được thể hiện trong văn bản. Ví dụ, từ một đánh giá như “Điện thoại đẹp, chạy nhanh nhưng pin hơi yếu”, hệ thống có thể nhận biết rằng người dùng có cả nhận xét tích cực và tiêu cực. Điểm thú vị của bài toán nằm ở khoảng cách giữa cách con người hiểu ngôn ngữ và cách máy tính xử lý dữ liệu. Một hệ thống phân tích cảm xúc cần biến văn bản tự nhiên thành dữ liệu có cấu trúc, học được các mẫu ngôn ngữ từ dữ liệu huấn luyện và đưa ra dự đoán hợp lý trên những câu chưa từng gặp. 1. Bài toán phân tích cảm xúc bắt đầu từ đâu? Hãy tưởng tượng một cửa hàng trực tuyến có hàng nghìn đánh giá mỗi ngày. Con người có thể đọc từng đánh giá để biết khách hàng hài lòng hay không, nhưng việc này nhanh chóng trở nên tốn thời gian khi dữ liệu tăng lên. NLP có thể biến bài toán đó thành một bài toán phân loại. Với mỗi văn bản, hệ thống nhận vào một chuỗi ký...

KAN cho phân đoạn khối u não với bộ BraTS 2020

Kolmogorov-Arnold Network (KAN) mở ra một hướng khác với MLP truyền thống: thay vì chỉ học các trọng số vô hướng trên mỗi kết nối, KAN có thể học những hàm phi tuyến một biến trên các cạnh . Khi đưa ý tưởng này vào kiến trúc encoder-decoder như U-Net, ta có thể sử dụng convolution để giữ cấu trúc không gian của ảnh MRI và dùng KAN để thực hiện các phép biến đổi phi tuyến mạnh hơn trên representation trung gian. Một bài toán phù hợp để nghiên cứu hướng này là phân đoạn u thần kinh đệm trên BraTS 2020 . Dataset cung cấp MRI đa mô thức và yêu cầu xác định các vùng Whole Tumor (WT), Tumor Core (TC) và Enhancing Tumor (ET). Đây là bài toán 3D có sự mất cân bằng voxel lớn, hình dạng khối u rất đa dạng và ranh giới giữa các mô bệnh lý không đơn giản. Lưu ý học thuật quan trọng: U-KAN gốc được công bố cho nhiều benchmark phân đoạn ảnh y tế nhưng không báo cáo kết quả BraTS 2020. Một công trình sau đó đã mở rộng U-KAN sang 3D MRI brain tumor segmentation , nhưng đánh giá trên BraTS 2...

Tách từ trong tiếng Việt Word Segmentation

Tách từ tiếng Việt là bài toán xác định ranh giới giữa các từ trong một chuỗi văn bản. Khó khăn nằm ở chỗ khoảng trắng trong tiếng Việt thường phân cách các âm tiết , nhưng một từ hoàn chỉnh có thể gồm nhiều âm tiết như “sinh viên” , “đại học” , “công nghệ” hay “tự nhiên” . Tách từ đúng giúp các hệ thống NLP dựa trên từ biểu diễn văn bản hợp lý hơn, đặc biệt trong tìm kiếm, TF-IDF, phân loại văn bản, gán nhãn từ loại và một số mô hình ngôn ngữ tiếng Việt. Tuy nhiên, với các Transformer sử dụng tokenizer dưới mức từ như subword hoặc SentencePiece, tách từ thủ công không phải lúc nào cũng là bước bắt buộc . Việc có cần tách từ trước hay không phụ thuộc vào mô hình và pipeline cụ thể. Tóm tắt nội dung Khoảng trắng trong tiếng Việt không phải lúc nào cũng là ranh giới từ ; nhiều từ gồm hai hoặc nhiều âm tiết. Word segmentation và tokenization có liên quan nhưng không hoàn toàn đồng nghĩa. Ba hướng chính gồm dựa trên từ điển, mô hình thống kê và mô hình học sâu . Tron...

KAN là gì? Mạng Kolmogorov-Arnold khác MLP thế nào?

Kolmogorov-Arnold Network (KAN) là một kiến trúc mạng nơ-ron trong đó mỗi cạnh không chỉ chứa một trọng số vô hướng mà mang một hàm một biến có thể học được . Đây là khác biệt cốt lõi so với Multi-Layer Perceptron (MLP), nơi các cạnh chủ yếu thực hiện phép nhân với trọng số còn hàm kích hoạt thường được áp dụng tại các node. KAN được lấy cảm hứng từ định lý biểu diễn Kolmogorov-Arnold và đặc biệt đáng chú ý trong các bài toán xấp xỉ hàm, mô hình hóa khoa học và symbolic regression. Tuy nhiên, KAN không nên được hiểu là kiến trúc đã thay thế MLP trong mọi bài toán Deep Learning; khả năng biểu diễn, chi phí tính toán và mức độ phù hợp của hai kiến trúc khác nhau theo từng nhiệm vụ. Tóm tắt nội dung MLP học chủ yếu trọng số trên các cạnh , còn KAN đặt hàm một biến học được trên từng cạnh . Một KAN layer cộng kết quả của nhiều hàm cạnh để tạo activation của node tiếp theo. KAN gốc sử dụng B-spline để tham số hóa các hàm phi tuyến trên cạnh. KAN có lợi thế đáng chú ý về trực...