Thuật toán Tìm kiếm theo chiều sâu (Depth First Search – DFS) là một trong những thuật toán phổ biến nhất để duyệt qua đồ thị. DFS hoạt động bằng cách bắt đầu từ một đỉnh nguồn, sau đó khám phá càng xa càng tốt dọc theo một nhánh trước khi quay lui để khám phá các nhánh khác. DFS có thể được áp dụng trên các cấu trúc dữ liệu như cây, đồ thị (cả có hướng và vô hướng), và các bài toán như mê cung.
DFS là nền tảng cho nhiều bài toán quan trọng:
Bây giờ chúng ta sẽ đi sâu vào chi tiết của DFS, bao gồm lý thuyết, các bước thuật toán, các trường hợp sử dụng và cách triển khai.
DFS là một phương pháp duyệt qua các đỉnh của đồ thị theo chiến lược tìm kiếm sâu nhất trước. Bắt đầu từ một đỉnh, DFS sẽ khám phá tất cả các đỉnh có thể từ đỉnh đó, di chuyển càng sâu càng tốt trước khi quay lại đỉnh trước đó để khám phá nhánh còn lại.
DFS có nhiều ứng dụng thực tiễn trong các bài toán đồ thị, cụ thể:
DFS được triển khai bằng cách gọi đệ quy qua các đỉnh chưa được thăm, theo các bước như sau:
def dfs(graph, node, visited):
# Đánh dấu đỉnh hiện tại là đã thăm
visited.add(node)
print(node) # Xử lý đỉnh hiện tại
# Duyệt qua các đỉnh kề
for neighbor in graph[node]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
Ví dụ về đồ thị:
A
/ \
B C
| |
D E
\
F
Danh sách kề:
graph = {
'A': ['B', 'C'],
'B': ['D'],
'C': ['E'],
'D': [],
'E': ['F'],
'F': []
}
Thực hiện DFS từ đỉnh ‘A’:
visited = set()
dfs(graph, 'A', visited)
Kết quả in ra:
A B D C E F
Phiên bản DFS lặp sử dụng ngăn xếp thay cho đệ quy. Các bước của DFS lặp như sau:
def dfs_iterative(graph, start):
stack = [start] # Ngăn xếp chứa đỉnh bắt đầu
visited = set() # Tập chứa các đỉnh đã thăm
while stack:
node = stack.pop() # Lấy đỉnh từ ngăn xếp
if node not in visited:
visited.add(node)
print(node) # Xử lý đỉnh
# Đưa các đỉnh kề chưa thăm vào ngăn xếp
for neighbor in reversed(graph[node]):
if neighbor not in visited:
stack.append(neighbor)
Thực hiện DFS lặp từ đỉnh ‘A’:
dfs_iterative(graph, 'A')
Kết quả in ra:
A C E F B D
DFS là một công cụ hữu ích để phát hiện chu trình trong đồ thị có hướng và vô hướng. Nếu có một đỉnh quay trở lại chính nó hoặc quay lại một đỉnh đã xuất hiện trong ngăn xếp hiện tại của DFS, thì tồn tại một chu trình.
Pseudocode phát hiện chu trình trong đồ thị có hướng:
def is_cyclic(graph, node, visited, rec_stack):
visited.add(node)
rec_stack.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
if is_cyclic(graph, neighbor, visited, rec_stack):
return True
elif neighbor in rec_stack:
return True
rec_stack.remove(node)
return False
DFS cũng được sử dụng để thực hiện sắp xếp topo trong đồ thị có hướng không chu trình (DAG). Trong sắp xếp topo, các đỉnh được sắp xếp sao cho nếu có cạnh từ đỉnh u đến đỉnh v, thì u sẽ xuất hiện trước v trong thứ tự sắp xếp.
Trong đồ thị vô hướng, DFS có thể tìm ra các thành phần liên thông, nghĩa là các nhóm đỉnh mà trong đó có thể đi từ bất kỳ đỉnh nào đến đỉnh khác. Mỗi lần DFS bắt đầu từ một đỉnh chưa thăm sẽ khám phá một thành phần liên thông mới.
DFS là một thuật toán cơ bản, nhưng vô cùng mạnh mẽ trong việc giải quyết các bài toán đồ thị. Nó có thể được triển khai dễ dàng cả theo cách đệ quy lẫn cách lặp. DFS là công cụ cần thiết cho các bài toán phát hiện chu trình, tìm thành phần liên thông, và các bài toán tìm đường trong nhiều ứng dụng thực tiễn khác.
