DFS ghé thăm các đỉnh con trước đỉnh anh em; tức là nó duyệt sâu theo một đường đi cụ thể trước khi khám phá độ rộng. Một stack (thường là call stack của chương trình qua đệ quy) thường được dùng khi triển khai thuật toán.
Cách DFS hoạt động:
- Ghé thăm đỉnh kề chưa thăm. Đánh dấu đã thăm. Hiển thị nó. Đẩy vào stack.
- Nếu không tìm thấy đỉnh kề, lấy một đỉnh từ stack. (Sẽ lấy tất cả đỉnh từ stack, những đỉnh không có đỉnh kề.)
- Lặp lại Quy tắc 1 và 2 cho đến khi stack rỗng.
Hãy xem minh họa cách DFS traversal hoạt động.
| Bước | Duyệt | Mô tả |
|---|---|---|
| 1 |  | Khởi tạo stack. |
| 2 |  | Đánh dấu S đã thăm và đẩy vào stack. Khám phá nút kề chưa thăm từ S. Có 3 nút và có thể chọn bất kỳ. Ví dụ này chọn theo thứ tự bảng chữ cái. |
| 3 |  | Đánh dấu A đã thăm và đẩy vào stack. Khám phá nút kề chưa thăm từ A. Cả S và D kề với A nhưng chỉ quan tâm nút chưa thăm. |
| 4 |  | Ghé thăm D, đánh dấu đã thăm và đẩy vào stack. Ở đây có B và C kề với D và cả hai chưa thăm. Tuy nhiên, lại chọn theo thứ tự bảng chữ cái. |
| 5 |  | Chọn B, đánh dấu đã thăm và đẩy vào stack. B không có nút kề chưa thăm. Vậy lấy B ra khỏi stack. |
| 6 |  | Kiểm tra đỉnh đỉnh stack để quay lại nút trước và xem có nút kề chưa thăm không. Ở đây, tìm thấy D ở đỉnh stack. |
| 7 |  | Chỉ nút kề chưa thăm từ D là C bây giờ. Vậy ghé thăm C, đánh dấu đã thăm và đẩy vào stack. |
Vì C không có nút kề chưa thăm, ta tiếp tục lấy stack cho đến khi tìm thấy nút có nút kề chưa thăm. Trong trường hợp này, không có và ta lấy cho đến khi stack rỗng. Hãy xem cách triển khai trong JavaScript.
Ví dụ
DFS(node) {
// Tạo Stack và thêm nút khởi tạo vào
let s = new Stack(this.nodes.length);
let explored = new Set();
s.push(node);
// Đánh dấu nút đầu tiên đã khám phá
explored.add(node);
// Tiếp tục cho đến khi Stack rỗng
while (!s.isEmpty()) {
let t = s.pop();
// Log mọi phần tử ra khỏi Stack
console.log(t);
// 1. Trong object edges, tìm nút mà nút này kết nối trực tiếp.
// 2. Lọc bỏ nút đã được khám phá.
// 3. Đánh dấu mỗi nút chưa khám phá là đã khám phá và đẩy vào Stack.
this.edges[t]
.filter(n => !explored.has(n))
.forEach(n => {
explored.add(n);
s.push(n);
});
}
}
Thật dễ dàng. Chúng ta chỉ đổi queue thành stack và đã có DFS. Đó chính là sự khác biệt duy nhất giữa hai thuật toán. DFS cũng có thể triển khai bằng đệ quy. Nhưng tốt nhất tránh trong trường hợp này vì đồ thị lớn nghĩa là cần bộ nhớ thêm để theo dõi call stack.
Bạn có thể kiểm tra bằng cách sau:
let g = new Graph();
g.addNode("A");
g.addNode("B");
g.addNode("C");
g.addNode("D");
g.addNode("E");
g.addNode("F");
g.addNode("G");
g.addEdge("A", "C");
g.addEdge("A", "B");
g.addEdge("A", "D");
g.addEdge("D", "E");
g.addEdge("E", "F");
g.addEdge("B", "G");
g.DFS("A");
Kết quả
Điều này sẽ cho ra kết quả.
A D E F B G C