Triển khai tìm kiếm theo chiều sâu trong Python

 Depth-first search (DFS), là một thuật toán để duyệt cây trên đồ thị hoặc cấu trúc dữ liệu cây. Nó có thể được thực hiện dễ dàng bằng cách sử dụng đệ quy và cấu trúc dữ liệu như từ điển và bộ.

Thuật toán

1. Chọn bất kỳ nút nào. Nếu nó không được truy cập, hãy đánh dấu nó là đã thăm và lặp lại trên tất cả các nút lân cận của nó.
2. Lặp lại cho đến khi tất cả các nút được truy cập hoặc nút được tìm kiếm được tìm thấy.

Triển khai

Hãy xem xét biểu đồ này, được triển khai trong đoạn mã dưới đây:

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

visited = set() # Set to keep track of visited nodes.

def dfs(visited, graph, node):
    if node not in visited:
        print (node)
        visited.add(node)
        for neighbour in graph[node]:
            dfs(visited, graph, neighbour)

# Driver Code
dfs(visited, graph, 'A')

Giải thích

• Biểu đồ minh họa được biểu diễn bằng cách sử dụng adjacency list - một cách dễ dàng để làm điều đó trong Python là sử dụng dictionary data structure. Mỗi đỉnh có một danh sách các nút liền kề của nó được lưu trữ
• Line 11: visited là một tập hợp được sử dụng để theo dõi các nút đã truy cập hay đã xét.
• Line 21: The dfs hàm được gọi và được chuyển vào visited set, the graph in the form of a dictionary, and A, là nút bắt đầu.
• Lines 13-18: dfs theo thuật toán được mô tả ở trên:
  1. It first checks if the current node is unvisited - if yes, it is appended in the visited set.
  2. Then for each neighbor of the current node, the dfs function is invoked again.
  3. The base case is invoked when all the nodes are visited. The function then returns.

Độ phức tạp

Vì tất cả các nút và đỉnh được truy cập, độ phức tạp thời gian trung bình cho DFS trên đồ thị là O (V + E) O (V + E), trong đó VV là số đỉnh và EE là số cạnh. Trong trường hợp DFS trên cây, độ phức tạp thời gian là O (V) O (V), trong đó VV là số nút.