DFS
Bài học 11 trên 14 trong khóa học Đồ thị, chuỗi cấu trúc dữ liệu #9 của Coddy.
Tìm kiếm theo chiều sâu đi sâu trước rồi mới mở rộng. Bắt đầu từ một đỉnh, thuật toán đi theo một cạnh xa nhất có thể, sau đó quay lui và thử cạnh tiếp theo. Phiên bản lặp sử dụng ngăn xếp: lấy một đỉnh ra, ghi lại đỉnh đó, rồi đưa các đỉnh kề chưa được thăm trở lại ngăn xếp.
Để DFS tạo ra thứ tự duyệt xác định trong thử thách này, hãy đưa các đỉnh kề vào ngăn xếp theo thứ tự giảm dần. Nhờ vậy, đỉnh kề nhỏ nhất nằm trên cùng ngăn xếp và được xử lý trước, khớp với thứ tự mà DFS đệ quy trên các đỉnh kề tăng dần sẽ tạo ra.
Lưu ý một đỉnh có thể được đưa vào ngăn xếp hai lần, vì các đỉnh kề khác nhau có thể cùng kề với nó. Hãy kiểm tra tập hợp các đỉnh đã thăm ở đầu vòng lặp và bỏ qua nếu đỉnh đó đã được thăm.
Thử thách
DễViết một hàm (function) dfs nhận mảng số nguyên 2D adjacency (mỗi hàng là một cạnh [u, v]) và số nguyên start, rồi trả về thứ tự duyệt DFS bắt đầu từ start dưới dạng danh sách số nguyên.
Dựng đồ thị bằng cách thêm từng cạnh. Duyệt DFS lặp bằng ngăn xếp: lấy một đỉnh ra khỏi ngăn xếp, nếu chưa được thăm thì ghi lại đỉnh đó và thêm các đỉnh kề theo thứ tự giảm dần để đỉnh nhỏ nhất được xử lý trước.
Bạn phải dùng lớp Graph (được cung cấp trong graph), không dùng các kiểu dựng sẵn của ngôn ngữ (map, set) để biểu diễn danh sách kề. Dữ liệu phụ trợ cho thuật toán (tập hợp các đỉnh đã thăm, ngăn xếp) có thể dùng các kiểu trong thư viện chuẩn.
Tự làm thử
#include <stdio.h>
#include "solution.h"
int main() {
int n, m, start;
if (scanf("%d %d %d", &n, &m, &start) != 3) return 0;
int adjacency[1024][2];
for (int i = 0; i < m; i++) scanf("%d %d", &adjacency[i][0], &adjacency[i][1]);
int out[MAX_VERTICES];
int outn = dfs(adjacency, m, start, out);
for (int i = 0; i < outn; i++) {
if (i > 0) printf(" ");
printf("%d", out[i]);
}
printf("\n");
return 0;
}
Tất cả bài học trong Đồ thị, chuỗi cấu trúc dữ liệu #9
Tự luyện tập: Trình biên dịch C online