Thuật toán tìm kiếm theo chiều sâu (DFS)

7.1 Nguyên tắc hoạt động của thuật toán DFS

Tìm kiếm theo chiều sâu (Depth-First Search, DFS) — là thuật toán duyệt hoặc tìm kiếm trong đồ thị. Nó bắt đầu từ đỉnh đầu tiên và đi sâu vào đồ thị cho đến khi đạt đến đỉnh không còn đỉnh liền kề chưa thăm, sau đó quay ngược lại và tiếp tục quá trình với các đỉnh khác.

Các bước của thuật toán:

1. Bắt đầu với đỉnh đầu tiên đã chọn và đánh dấu nó là đã thăm.
2. Khám phá đỉnh liền kề chưa thăm đầu tiên.
3. Lặp lại các bước 1 và 2 cho đỉnh liền kề này.
4. Nếu tất cả các đỉnh liền kề của đỉnh hiện tại đã thăm, quay lại (backtrack) đỉnh trước đó và tiếp tục quá trình.
5. Quá trình lặp lại cho đến khi tất cả các đỉnh có thể tiếp cận từ đỉnh đầu tiên đã thăm.

Hình ảnh minh họa:

Độ phức tạp thời gian và không gian của DFS:

Độ phức tạp thời gian:

O(V + E), trong đó V là số lượng đỉnh, E là số lượng cạnh.

Mỗi nút và mỗi cạnh của đồ thị được thăm một lần.

Độ phức tạp không gian:

O(V), vì sử dụng ngăn xếp gọi đệ quy hoặc ngăn xếp rõ ràng để lưu trữ các đỉnh, cũng như mảng để lưu trữ trạng thái (các đỉnh đã thăm).

7.2 Thực hiện DFS sử dụng đệ quy

Hãy bắt đầu thực hiện DFS sử dụng đệ quy — mã sẽ ngắn gọn và dễ hiểu.

Thực hiện DFS sử dụng đệ quy:

def dfs_recursive(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start)  # Xử lý nút
    
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)
    
# Ví dụ sử dụng:
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B'],
    'F': ['C']
}
dfs_recursive(graph, 'A')

7.3 Thực hiện DFS sử dụng ngăn xếp

Không sử dụng đệ quy mã sẽ hơi dài hơn một chút, vì chúng ta cần lưu trữ thêm danh sách các đỉnh đã thăm.

Thực hiện DFS Sử dụng ngăn xếp (iterative):

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
        
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            print(vertex)  # Xử lý nút
        
            for neighbor in reversed(graph[vertex]):  # Thứ tự ngược để duyệt đúng thứ tự
                if neighbor not in visited:
                    stack.append(neighbor)
        
# Ví dụ sử dụng:
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B'],
    'F': ['C']
}
dfs_iterative(graph, 'A')

7.4 Ví dụ về các bài toán giải quyết bằng DFS

Các ví dụ kinh điển về các bài toán giải quyết bằng DFS:

1. Tìm đường đi trong mê cung:

Sử dụng để tìm đường đi trong mê cung từ điểm bắt đầu đến điểm kết thúc.

Ứng dụng:

Trong trò chơi điện tử và robot để điều hướng qua các mê cung và không gian phức tạp.

2. Kiểm tra tính liên thông của đồ thị:

Kiểm tra xem đồ thị có liên thông không (có đường đi giữa hai đỉnh bất kỳ hay không).

Ứng dụng:

Trong phân tích mạng để kiểm tra tính liên thông của mạng.

3. Sắp xếp topo:

Sử dụng để sắp xếp các đỉnh của đồ thị có hướng không chu trình (DAG) sao cho với mỗi cạnh (u, v) đỉnh u đứng trước đỉnh v.

Ứng dụng:

Trong trình biên dịch để sắp xếp thứ tự phụ thuộc và công việc.

4. Phát hiện chu trình trong đồ thị:

Kiểm tra xem đồ thị có chứa chu trình hay không.

Ứng dụng:

Trong phân tích phụ thuộc để phát hiện phụ thuộc vòng.

5. Tạo mê cung:

Sử dụng DFS để tạo mê cung ngẫu nhiên.

Ứng dụng:

Trong các ứng dụng trò chơi và giải trí để tạo mê cung.