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

The Depth First Search (DFS) là một thuật toán để duyệt qua hoặc tìm kiếm cấu trúc dữ liệu dạng cây hoặc đồ thị sử dụng ý tưởng về backtracking. Nó khám phá tất cả các nút bằng cách chuyển tiếp nếu có thể hoặc sử dụng backtracking.

Note: Nó có thể được thực hiện bằng cách sử dụng một ngăn xếp.

Thuật toán

Đây là các bước cho thuật toán DFS:

• Chọn một nút và đẩy tất cả các nút liền kề của nó vào một ngăn xếp.

• Bật một nút từ ngăn xếp và đẩy tất cả các nút liền kề của nó vào một ngăn xếp.

• Lặp lại quá trình này cho đến khi ngăn xếp trống hoặc bạn đạt được mục tiêu.

Chương trình có thể bị mắc kẹt trong một vòng lặp vô hạn nếu một nút được truy cập lại và không được đánh dấu là đã truy cập (visited) trước đó. Do đó, ngăn việc khám phá các nút được truy cập bằng cách đánh dấu chúng là đã truy cập.

Ví dụ

Chúng ta có một đồ thị có hướng gồm năm nút với G là nút cần tìm. Các nút sẽ được đánh dấu là đã truy cập bằng cách sử dụng mảng đã truy cập (visited) trong khi các nút liền kề sẽ được thêm vào ngăn xếp(stack.)

1 of 8

Giải trình

Bắt đầu từ nút nguồn A, chúng ta tiếp tục di chuyển đến các nút lân cận A đến B đến D nơi chúng ta đạt đến mức xa nhất. Sau đó, chúng tôi quay lại nút B trước đó và chọn một nút liền kề. Một lần nữa, chúng tôi thăm dò cho đến mức xa nhất mà chúng tôi đạt được nút G mong muốn.

Độ phức tạp

Độ phức tạp của DFS nếu toàn bộ cây được duyệt qua là O (V) trong đó V là số nút. Trong trường hợp của một đồ thị, độ phức tạp thời gian là O (V + E) O (V + E) trong đó V là số đỉnh và E là số cạnh.