Khóa học Python từ Cơ bản đến Nâng cao

Bài 12.2 - Thuật toán DFS với Python trong Python

DFS (Depth-First Search - Duyệt theo chiều sâu) là một trong những thuật toán cơ bản và cực kỳ quan trọng trong lĩnh vực xử lý đồ thị. Trong bài học này, chúng ta sẽ cùng nhau:

• Hiểu cách hoạt động của DFS
• Cài đặt DFS đệ quy và không đệ quy
• Áp dụng DFS trên đồ thị sử dụng adjacency list
• Có nhiều ví dụ minh hoạ cụ thể

DFS hoạt động như thế nào?

DFS bắt đầu từ một đỉnh gốc, và đi sâu vào từng nhánh đến khi không thể đi tiếp thì mới quay lui lại.

DFS giống như bạn đi khám phá mê cung, luôn chọn đi vào ngõ sâu nhất trước.

Mô hình đồ thị

Chúng ta sẽ sử dụng đồ thị vô hướng dưới dạng danh sách kề như sau:

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

Cài đặt DFS bằng đệ quy

def dfs_recursive(graph, node, visited=None):
    if visited is None:
        visited = set()

    print(node)
    visited.add(node)

    for neighbor in graph.get(node, []):
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)

Giải thích:

• visited: dùng để theo dõi các đỉnh đã đi qua.
• Đệ quy gọi lại chính nó cho từng đỉnh chưa thăm.

Ví dụ minh hoạ 1

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

dfs_recursive(graph, 'A')

Output:

A
B
D
E
F
C

DFS có thể đi theo nhiều thứ tự khác nhau tùy vào cách sắp xếp danh sách kề.

Cài đặt DFS bằng stack (không đệ quy)

def dfs_stack(graph, start):
    visited = set()
    stack = [start]

    while stack:
        node = stack.pop()
        if node not in visited:
            print(node)
            visited.add(node)
            # Thêm các đỉnh kề vào stack (đảo ngược thứ tự để đúng logic DFS)
            for neighbor in reversed(graph.get(node, [])):
                if neighbor not in visited:
                    stack.append(neighbor)

DFS dùng stack hoạt động tương tự đệ quy nhưng bạn kiểm soát rõ ràng thứ tự duyệt.

Ví dụ minh hoạ 2

dfs_stack(graph, 'A')

Kết quả:

A
B
D
E
F
C

So sánh DFS đệ quy và stack

Ứng dụng thực tế của DFS

• Kiểm tra tính liên thông của đồ thị
• Phát hiện chu trình
• Tìm đường đi trong mê cung
• Thuật toán topo sort
• Bài toán thành phần liên thông mạnh

Bài tập gợi ý

1. Cài đặt DFS trên đồ thị có hướng
2. Tìm tất cả các đỉnh có thể đi đến từ một đỉnh gốc
3. Viết DFS để tìm đường đi từ A đến F

Kết luận

DFS là thuật toán cực kỳ nền tảng, giúp bạn hiểu rõ cách duyệt cấu trúc đồ thị, cây và các bài toán liên quan đến đệ quy, tìm kiếm, và phân tích dữ liệu có quan hệ.