NỘI DUNG
Giới thiệu Thuật toán DFS (Depth-first search)
– DFS (Depth-first search) là một thuật toán tìm kiếm sâu trong đồ thị.
– Thuật toán DFS bắt đầu tại một đỉnh (node) bất kỳ của đồ thị và đi thẳng tới cùng một nhánh của đỉnh đó cho đến khi không thể đi được nữa. Sau đó, thuật toán quay lại đi tiếp theo trên đường đi mới nhất.
Các bước thực hiện thuật toán DFS
– Bước 1: Chọn một đỉnh bất kỳ trong đồ thị làm đỉnh bắt đầu.
– Bước 2: Đánh dấu đỉnh đó là đã được thăm.
– Bước 3: Đưa ra các nhánh của đỉnh đã chọn (nếu có) và chọn một nhánh để đi tiếp theo.
– Bước 4: Thực hiện đệ quy từ bước 2 cho đến khi tìm thấy đỉnh kết thúc hoặc không có nhánh để đi tiếp.
Ví dụ về thuật toán DFS
Xét đồ thị G = (V, E) sau:
Bắt đầu từ đỉnh B, thuật toán DFS sẽ đi theo thứ tự B-C-D-A-E-F-G.
V = {A, B, C, D, E, F, G}
E = {(A, B), (A, E), (B, C), (B, D), (E, F), (E, G)}
Cài đặt thuật toán DFS với Python
graph = {
'A': ['B', 'E'],
'B': ['A', 'C', 'D'],
'C': ['B'],
'D': ['B'],
'E': ['A', 'F', 'G'],
'F': ['E'],
'G': ['E']
}
visited = []
def dfs(graph, node):
visited.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
dfs(graph, neighbor)
dfs(graph, 'B')
print(visited)
Đánh giá độ phức tạp của thuật toán DFS
Độ phức tạp của thuật toán DFS là O(V + E), trong đó V là số đỉnh trong đồ thị và E là số cạnh trong đồ thị. Vì với mỗi đỉnh trong đồ thị, thuật toán chỉ duyệt một lần và với mỗi cạnh trong đồ thị, thuật toán chỉ duyệt một lần. Do đó, độ phức tạp của thuật toán là tuyến tính theo số đỉnh và số cạnh trong đồ thị.