Tìm kiếm theo chiều sâu (DFS)
Đi vào một mê cung, cứ đi tiếp cho đến khi gặp ngõ cụt, rồi quay lại ngã rẽ gần nhất và thử lối tiếp theo. Tìm kiếm theo chiều sâu khám phá đồ thị theo cùng cách đó. Đây là một trong những thuật toán đồ thị đơn giản nhất, và ngăn xếp mà nó dùng cho bạn biết nhiều hơn bạn tưởng.
Ý tưởng
Đồ thị là một tập các đỉnh nối với nhau bằng cạnh: phòng và cửa, trang web và liên kết, công việc và những công việc mà nó phụ thuộc. Tìm kiếm theo chiều sâu thăm mọi đỉnh tới được từ điểm xuất phát, nhưng theo một thứ tự riêng: thuật toán luôn đi tiếp từ đỉnh vừa tới gần đây nhất. Nó giữ một ngăn xếp chứa các đỉnh mà nó đang ở bên trong. Đỉnh mới được đặt lên trên cùng, và một đỉnh chỉ được lấy ra khi mọi thứ quanh nó đã được khám phá.
Từng bước
Đưa điểm xuất phát vào ngăn xếp và gán số thứ tự thăm 1. Xét đỉnh kề tiếp theo của đỉnh trên cùng. Nếu nó chưa từng được thấy, gán cho nó số thứ tự thăm tiếp theo, ghi nhớ đỉnh đã dẫn tới nó, và đặt nó lên trên cùng ngăn xếp. Nếu đã thấy rồi, bỏ qua. Khi đỉnh trên cùng không còn đỉnh kề nào để xét, nó đã xong: lấy nó ra và đi tiếp với đỉnh bên dưới. Dừng khi ngăn xếp rỗng, hoặc khi tới đích.
Một ví dụ
Lấy một đồ thị có các cạnh A–B, A–C, B–D, C–D, C–E và D–F, bắt đầu tại A, và xét các đỉnh kề theo thứ tự bảng chữ cái. Từ A việc tìm kiếm đi đến B, từ B đến D, từ D đến C, và từ C đến E, nên ngăn xếp là A, B, D, C, E. Trên đường đi, C thấy A, vẫn còn trong ngăn xếp: cạnh C–A khép chu trình A, B, D, C. E không có gì mới, nên nó xong, rồi đến C, và việc tìm kiếm quay lui về D, đỉnh vẫn còn F. Thứ tự thăm là A, B, D, C, E, F. Nếu đích là E, DFS dừng với đường đi A → B → D → C → E, bốn cạnh, dù A → C → E chỉ cần hai.
Dùng để làm gì
Ngăn xếp luôn là một đường đi từ điểm xuất phát đến đỉnh hiện tại, nên DFS rất hợp với mê cung và câu đố: đó là ý tưởng đằng sau quay lui. Trong đồ thị vô hướng, một cạnh tới đỉnh vẫn còn trong ngăn xếp sẽ khép một chu trình. Trong đồ thị có hướng, liệt kê các đỉnh theo thứ tự ngược với thứ tự chúng xong sẽ cho một thứ tự tô pô, để mỗi công việc đứng sau những công việc mà nó phụ thuộc. Tìm kiếm theo chiều sâu cũng tìm được các thành phần liên thông, cầu và đỉnh khớp, và phiên bản ngẫu nhiên của nó là cách kinh điển để tạo mê cung.
Lịch sử
Vào thế kỷ 19, nhà toán học Pháp Charles Pierre Trémaux mô tả một cách thoát khỏi mọi mê cung bằng cách đánh dấu các lối đi, đó chính là tìm kiếm theo chiều sâu làm bằng phấn. Năm 1972 và 1973, Robert Tarjan và John Hopcroft chỉ ra rằng DFS giải được nhiều bài toán đồ thị trong thời gian tuyến tính, từ thành phần liên thông mạnh đến kiểm tra xem một đồ thị có vẽ được mà không có cạnh cắt nhau hay không. Họ nhận Giải Turing năm 1986 một phần nhờ công trình đó.
Khám phá
Mở ứng dụng và nhấn Bước. Đỉnh đang được xét các đỉnh kề sẽ được tô sáng, các đỉnh trong ngăn xếp có màu xanh dương, và các đỉnh đã xong có màu xanh lá, mỗi đỉnh kèm số thứ tự thăm. Ngăn xếp hiển thị dưới đồ thị, từ điểm xuất phát đến đỉnh trên cùng. Theo dõi dòng trạng thái để thấy các cạnh khép chu trình, và chọn một đích để xem đường đi tìm được có thể dài thế nào so với tìm kiếm theo chiều rộng.
Câu hỏi thường gặp
Độ phức tạp thời gian của DFS là bao nhiêu?
O(V + E) với V đỉnh và E cạnh: mỗi đỉnh vào và ra khỏi ngăn xếp một lần, và mỗi cạnh được xét từ cả hai đầu. Thuật toán cần thêm O(V) bộ nhớ cho ngăn xếp và các dấu đánh dấu.
Vì sao DFS dùng ngăn xếp?
Vì vào sau, ra trước khiến việc tìm kiếm đi tiếp từ đỉnh mới nhất và quay lui về đỉnh trước đó. Đệ quy làm điều tương tự bằng ngăn xếp lời gọi của chương trình. Nếu dùng hàng đợi thay vào đó, việc tìm kiếm sẽ lan ra từng vòng: đó là tìm kiếm theo chiều rộng.
DFS đệ quy có gặp vấn đề với đồ thị lớn không?
Có thể: một đường đi dài nghĩa là đệ quy sâu, và nhiều ngôn ngữ giới hạn độ sâu của lời gọi. Một ngăn xếp tường minh trong vòng lặp tránh được giới hạn đó mà vẫn thăm các đỉnh theo cùng thứ tự.
DFS được dùng ở đâu?
Giải mê cung và câu đố bằng quay lui, tìm chu trình, sắp xếp công việc theo quan hệ phụ thuộc (sắp xếp tô pô), tìm thành phần liên thông và liên thông mạnh, tạo mê cung, và trong trình biên dịch cũng như công cụ build duyệt đồ thị phụ thuộc.
Sẵn sàng thử chưa?
Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.
Thử tìm kiếm theo chiều sâu