Depth-First Search
Published:
DFS (Depth-first search) là thuật toán tìm kiếm trên đồ thị với tư tưởng:
- Ưu tiên “chiều sâu” hơn “chiều rộng”
- Đi sâu nhất có thể trước khi quay lại Xuất phát từ 1 node, duyệt đến tận cùng của từng nhánh tỏa ra từ nút đó rồi mới chuyển sang nhánh tiếp theo, rồi nút tiếp theo, v.v..
Nguyên lý hoạt động
- Bắt đầu từ một đỉnh xuất phát
- Đánh dấu đỉnh hiện tại là đã thăm
- Duyệt tất cả các đỉnh kề chưa được thăm của đỉnh hiện tại
- Quay lui để thử các nhánh khác
Cài đặt
- Biểu diễn đồ thị: Thường thường, input của đề bài là nhập hết tất cả các cạnh nên ta ưu tiên dùng phương pháp biểu diễn là adjacency list (danh sách kề) là hợp lí nhất. Ngoài ra khi sử dụng danh sách kề với DFS, độ phức tạp chỉ còn O(max(V, E)) so với O(V2) khi sử dụng adjacency matrix (ma trận kề).
- Cài đặt thuật toán DFS: Thường có 2 cách cài đặt chính: sử dụng đệ quy quay lui và sử dụng cấu trúc dữ liệu stack (khử đệ quy).
Sử dụng đệ quy (recursion)
Dùng danh sách kề:
void input(){
cin >> n >> m;
while (m--){
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
memset(unused, true, sizeof unused);
}
void DFS(int u){
unused[u] = false;
for(int i = 0; i < adj[u].size(); i++){
int v = adj[u][i];
if(unused[v]){
DFS(v);
}
}
}
Dùng ma trận kề:
void input(){
cin >> n;
for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) cin >> adj[i][j];
memset(unused, true, sizeof unused);
}
void DFS(int u){
unused[u] = false;
for(int i = 1; i <= n; i++){
int v = adj[u][i];
if(unused[v] && adj[u][i]){
DFS(v);
}
}
}
Sử dụng stack
Dùng danh sách kề:
void input(){
cin >> n >> m;
while (m--){
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
}
void DFS(int u){
memset(unused, true, sizeof unused);
unused[u] = false;
stack S;
S.push(u);
while (!S.empty()){
int x = S.top(); S.pop();
for(int i = 0; i < adj[x].size(), i++){
int y = adj[x][i];
if(unused[y]){
unused[y] = false;
S.push(x); S.push(y); break;
}
}
}
}
Dùng ma trận kề:
void input(){
cin >> n;
for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) cin >> adj[i][j];
}
void DFS(int u){
memset(unused, true, sizeof unused);
unused[u] = false;
stack S;
S.push(u);
while (!S.empty()){
int x = S.top(); S.pop();
for(int i = 1; i <= n; i++){
if(adj[x][i] == 1 && unused[i]){
unused[i] = false;
S.push(x); S.push(i); break;
}
}
}
}
Có thể tải code và chạy tại đây: https://ideone.com/9NSjls
Ứng dụng
- Kiểm tra tính liên thông của đồ thị
- Tìm chu trình trong đồ thị
- Sắp xếp tô-pô (Topological Sort)
- Tìm thành phần liên thông mạnh
- Giải các bài toán mê cung
Độ phức tạp
- Thời gian: O(V + E) với V là số đỉnh và E là số cạnh
- Không gian: O(V) cho việc lưu trữ mảng visited và stack/đệ quy