- Hiện tại
- Trong ngăn xếp
- Đã xong
- Đường đi
Tìm kiếm theo chiều sâu (DFS)
Tìm kiếm theo chiều sâu khám phá đồ thị giống như một người đi trong mê cung với một tay chạm tường: đi theo một lối xa nhất có thể, và chỉ quay lui khi không còn chỗ mới nào để đi. Thuật toán làm điều đó bằng một ngăn xếp. Nhấp vào một đỉnh để bắt đầu từ đó, chọn đích nếu muốn, rồi đi từng bước để xem ngăn xếp dài ra và ngắn lại, mỗi đỉnh nhận số thứ tự thăm của nó, và những cạnh khép một chu trình. Nhấn Phát để xem quá trình tìm kiếm, hoặc dùng Bước và Lùi để đi từng bước. Kéo thanh trượt bước để nhảy đến bất kỳ đâu. Nhấp vào một đỉnh để chọn làm điểm xuất phát; chuyển thao tác nhấp sang Đích rồi nhấp vào đỉnh khác để tìm đường đi đến đó. Số trên mỗi đỉnh là thứ tự đỉnh đó được thăm, còn hàng dưới đồ thị là ngăn xếp, từ điểm xuất phát lên đến đỉnh trên cùng. Đồ thị mới tạo một đồ thị khác; chọn số đỉnh và số cạnh. Khi bảng đang được chọn, phím mũi tên đi từng bước, phím cách phát và tạm dừng, còn Home và End nhảy về đầu và cuối.
Cách nó hoạt động
- Nhấp vào một đỉnh để chọn làm điểm xuất phát. Để tìm đường đi, chuyển thao tác nhấp sang Đích rồi nhấp vào đỉnh khác.
- Nhấn Phát, hoặc dùng Bước và Lùi để đi từng bước. Kéo thanh trượt bước để nhảy đến bất kỳ đâu trong quá trình tìm kiếm.
- Theo dõi ngăn xếp dưới đồ thị và số thứ tự thăm trên mỗi đỉnh. Đồ thị mới tạo một đồ thị khác để thử.
Cách tìm kiếm theo chiều sâu hoạt động
Đưa đỉnh xuất phát vào ngăn xếp. Rồi lặp lại: xét đỉnh kề tiếp theo của đỉnh trên cùng ngăn xếp. Một đỉnh kề chưa từng thấy sẽ nhận số thứ tự thăm tiếp theo, ghi nhớ đỉnh đã dẫn tới nó, và được đặt lên trên cùng ngăn xếp, nên việc tìm kiếm đi tiếp từ đó. Khi đỉnh trên cùng không còn đỉnh kề nào để xét, nó đã xong và được lấy ra khỏi ngăn xếp, và việc tìm kiếm quay lui về đỉnh bên dưới. Khi ngăn xếp rỗng, mọi đỉnh tới được đều đã được thăm.
Ngăn xếp cho bạn biết gì
Vì việc tìm kiếm luôn đi tiếp từ đỉnh mới nhất, ngăn xếp luôn là một đường đi từ điểm xuất phát đến đỉnh đang xét. Khi tới đích, ngăn xếp là một đường đi đến đó, dù thường không phải đường ngắn nhất: tìm kiếm theo chiều rộng mới tìm được đường đó. Trong đồ thị vô hướng, một cạnh tới đỉnh vẫn còn trong ngăn xếp, trừ đỉnh vừa đi từ đó tới, sẽ khép một chu trình. Các đỉnh được ghi nhớ tạo thành một cây, gọi là cây tìm kiếm theo chiều sâu, và thứ tự các đỉnh xong là chìa khóa của sắp xếp tô pô.
Câu hỏi thường gặp
Tìm kiếm theo chiều sâu là gì?
Một cách khám phá đồ thị từ một đỉnh xuất phát bằng cách đi theo một lối sâu nhất có thể, và chỉ quay lui để thử nhánh khác khi không còn chỗ mới nào để đi. Thuật toán dùng ngăn xếp, hoặc đệ quy, để nhớ đường quay về.
Tìm kiếm theo chiều sâu có tìm được đường đi ngắn nhất không?
Không. Thuật toán tìm được một đường đi đến đích nếu có, nhưng đường đó có thể dài hơn cần thiết rất nhiều, vì DFS bám theo nhánh đầu tiên nó thử. Hãy dùng tìm kiếm theo chiều rộng để có ít cạnh nhất, hoặc thuật toán Dijkstra khi các cạnh có độ dài.
DFS và BFS khác nhau thế nào?
Tìm kiếm theo chiều sâu dùng ngăn xếp và đi sâu theo một lối trước khi quay lui. Tìm kiếm theo chiều rộng dùng hàng đợi và lan ra đều, từng vòng một. Cả hai đều thăm mọi đỉnh tới được trong thời gian tăng theo số đỉnh cộng số cạnh; BFS tìm đường đi ngắn nhất, còn DFS là lựa chọn tự nhiên cho chu trình, mê cung và sắp xếp tô pô.
DFS tìm chu trình như thế nào?
Trong đồ thị vô hướng, nếu việc tìm kiếm gặp một cạnh tới đỉnh vẫn còn trong ngăn xếp, và đỉnh đó không phải đỉnh vừa đi từ đó tới, thì cạnh đó khép một vòng. Trong ứng dụng, dòng trạng thái sẽ báo khi điều đó xảy ra.
Đồ thị của tôi có bị gửi đi đâu không?
Không. Đồ thị được tạo và tìm kiếm ngay trong trình duyệt của bạn, và cài đặt gần nhất được lưu trong bộ nhớ cục bộ của trình duyệt này.
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.
Tới trình chỉnh sửa