Đồ thị (Graph) Phần 3: DFS – Thuật toán tìm kiếm theo chiều sâu

DFS – Depth-First Search hay còn được gọi là tìm kiếm theo chiều sâu – là một trong những thuật toán quan trọng nhất của lý thuyết đồ thị. Ý tưởng cốt lõi của thuật toán DFS có thể được trình bày như sau: Xuất phát từ một đỉnh \(S\) ban đầu rồi thăm đỉnh \(x\) kề \(S\); từ đỉnh \(x\), ta sẽ thăm đỉnh \(y\) kề \(x\)… và cứ tiếp tục như vậy đến khi hết chiều sâu của nhánh. Sau đó, ta sẽ quay lại các đỉnh láng giềng và xét tương tự như trên.

Mục lục

1. Bài toán 1

Cho đồ thị vô hướng \(n\) đỉnh, \(m\) cạnh, 2 đỉnh \(S\) và \(T\) lần lượt thể hiện đỉnh bắt đầu và kết thúc của 1 đường đi. Lưu ý: tất cả các cạnh trong đồ thị chỉ được thăm tối đa 1 lần.

Yêu cầu: Tìm đường đi từ \(S\) tới \(T\).

Input:

Dòng đầu tiên chứa 4 số \(n, m, S, T\) \((3 ≤ n, m, S, T ≤ 200)\) \(m\) dòng tiếp theo, mỗi dòng chứa 2 số nguyên dương \(u, v\) cho ta thông tin: giữa 2 đỉnh \(u, v\) tồn tại 1 cạnh 2 chiều nối giữa chúng.

Output:

Dòng đầu ghi từ \(YES\) hay \(NO\) tùy theo có tồn tại đường đi từ \(S\) tới \(T\) hay không.
Nếu dòng đầu ghi từ \(YES\), dòng 2 ghi hành trình tìm được: Bắt đầu là đỉnh \(S\), tiếp theo là danh sách các đỉnh trên đường đi tồn tại từ \(S\) tới \(T\), cuối cùng là đỉnh \(T\).

Sample Input

Sample Output

YES
1 2 3 4 5

Giải thích

Phân tích bài toán:

Nhận xét: Với mọi đỉnh \(x\) kề \(S\), đồng nghĩa với việc tồn tại đường đi tới \(x\) từ \(S\). Tương tự như vậy, với mọi đỉnh \(y\) kề \(x\), đồng nghĩa với việc tồn tại đường đi từ \(y\) tới \(x\). Để lưu trữ đỉnh kề, ta khai báo như sau:

vector<int> adj[N + 1];
int n, m, s, t;

signed main() {
	cin >> n >> m >> s >> t;
	for (int i = 1; i <= m; i++) {
		int u, v; cin >> u >> v;
		adj[u].push_back(v); // đỉnh v kề u
		adj[v].push_back(u); // đỉnh u kề v
        }
}

Qua nhận xét trên, ta có thể liên tưởng tới việc sử dụng đệ quy để DFS liệu có tồn tại đường đi từ đỉnh \(S\) tới một đỉnh bất kỳ khác \(S\) trong đồ thị hay không. Bên cạnh đó, để đảm bảo tất cả các đỉnh không được thăm quá 1 lần, ta có thể sử dụng mảng đánh dấu \(visited\).
Ta có mã giả DFS:

void dfs(u):
	đánh dấu u đã thăm
	for v kề u: 
		nếu v chưa thăm 
			dfs(v)

Thứ tự duyệt đỉnh DFS có thể được hình dung như sau:

Muốn truy vết, ta sử dụng mảng \(trace[v]\) để lưu lại đỉnh trước \(v\). Có nghĩa là, đường đi từ \(S\) tới \(T\) có thể được biểu diễn như sau:
- \(T ← x1 = trace[T] ← x2 = trace[x1] ← … ← S\)

Code full:

#include<bits/stdc++.h>
using namespace std;

const int N = 200;

vector<int> adj[N + 1], Path;
bool visited[N + 1];
int trace[N + 1];
int n, m, S, T;

void dfs(int u) {
    visited[u] = true; // đánh dấu u đã được thăm
    for (auto v : adj[u]) {
        if (visited[v] == false) {
            // nếu như v chưa được thăm
            trace[v] = u;
            // đỉnh trước v là u 
            dfs(v);
        }
    }
}

void find_path(int t) {
    int x = t;
    while (true) {
        Path.push_back(x);
        // thêm đỉnh x vào đường đi
        if (x == S) {
            break;
            // nếu đỉnh x là S --> kết thúc vòng lặp while
        }
        x = trace[x];
    }
    for (int i = Path.size() - 1; i >= 0; i--) {
        cout << Path[i] << " ";
    }
}


signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> m >> S >> T;
    memset(visited, false, sizeof (visited));
    // tất cả các đỉnh trong đồ thị chưa được thăm
    for (int i = 1; i <= m; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v); // đỉnh v kề u
        adj[v].push_back(u); // đỉnh u kề v
    }
    dfs(S);
    if (visited[T] == false) {
        cout << "NO";
        return 0;
        // nếu như T chưa được thăm --> không tồn tại đường đi từ S tới T
    }
    cout << "YES" << "\n";
    find_path(T);
    return 0;
}

Độ phức tạp thời gian: \(O(V + E)\) với \(V\) là số đỉnh của đồ thị, \(E\) là số cạnh.

2. Bài toán 2

Cho đồ thị vô hướng \(n\) đỉnh, \(m\) cạnh. Yêu cầu: Đếm số thành phần liên thông trong đồ thị và liệt kê các đỉnh của từng thành phần liên thông đó.

Input:

Dòng đầu tiên chứa 2 số \(n, m\) \((3 ≤ n, m ≤ 200)\)
\(m\) dòng tiếp theo, mỗi dòng chứa 2 số nguyên dương \(u, v\) cho ta thông tin: giữa 2 đỉnh \(u, v\) tồn tại 1 cạnh 2 chiều nối giữa chúng.

Output:

Dòng đầu tiên ghi số nguyên dương \(k\) với \(k\) là số thành phần liên thông của đồ thị.
\(k\) dòng tiếp theo, mỗi dòng là một số đỉnh thỏa mãn: tất cả các đỉnh trên cùng một dòng đều thuộc cùng một thành phần liên thông.

Sample Input:

Sample Output:

2
1 2 3 4
5 6

Giải thích:

Phân tích bài toán:

Nhận xét: Với mọi đỉnh khác \(x\), nếu tồn tại ít nhất một con đường từ \(x\) tới nó, sẽ thuộc cùng một thành phần liên thông chứa \(x\).
Qua nhận xét trên: số thành phần liên thông của đồ thị chính là số lần DFS đỉnh \(x\) với \(x ∊ {1, 2, … n}\) và \(x\) là đỉnh chưa được thăm. Từ đó, ta có thể quy về bài toán 1 để giải bài này.

Code full:

#include<bits/stdc++.h>
using namespace std;

const int N = 200;

vector<int> adj[N + 1];
vector<int> connected_component[N + 1];
bool visited[N + 1];
int n, m, tplt = 0;

void dfs(int u) {
    connected_component[tplt].push_back(u);
    // thành phần liên thông thứ tplt chứa đỉnh u
    visited[u] = true; 
    // đánh dấu đỉnh u đã được thăm
    for (auto v : adj[u]) {
        if (visited[v] == false) {
            // nếu như v chưa được thăm
            dfs(v);
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> m;
    memset(visited, false, sizeof (visited));
    // tất cả các đỉnh trong đồ thị chưa được thăm
    for (int i = 1; i <= m; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v); // đỉnh v kề u
        adj[v].push_back(u); // đỉnh u kề v
    }
    for (int u = 1; u <= n; u++) {
        if (visited[u] == false) {
            // nếu đỉnh u chưa được thăm
            ++tplt;
            dfs(u);
        }
    }
    cout << tplt << '\n';
    for (int i = 1; i <= tplt; i++) {
        for (auto x : connected_component[i]) {
            cout << x << " ";
        }
        cout << '\n';
    }
    return 0;
}

3. Khi nào sử dụng thuật toán DFS

Khác với thuật toán BFS, tư tưởng của thuật toán DFS là đi hết chiều sâu của đỉnh đang xét và quay lại rồi đi hết chiều sâu của các đỉnh láng giềng.

→ Qua đó, thuật toán DFS được dùng để:

- Giải một số bài toán liên quan đến thành phần liên thông mạnh, đường đi Euler, quy hoạch động trên cây, sắp xếp topo…
- Phần lớn các bài liên quan đến việc xác định sự tồn tại của con đường giữa 2 đỉnh bất kỳ trong đồ thị, hoặc cách chuyển đổi giữa 2 trạng thái bất kỳ với một số điều kiện cho trước. Những bài toán này có thể sử dụng BFS để thay thế, tuy nhiên DFS thường dễ cài đặt hơn nên được khuyến khích sử dụng hơn.

4. Luyện tập

Đây là một số bài tập luyện tập trong sách Competitive Programming Advanced của Code Dream, đăng ký mua ngay để được luyện tập nhiều dạng bài về thuật toán khác, chấm bài online tại http://oj.codedream.edu.vn

Lời giải bài OFFER:

Phân tích bài toán:

Nhận xét: Để chọn được số đỉnh ít nhất mà vẫn thỏa mãn đề bài đưa ra, ta nghĩ đến việc DFS từng đỉnh một để kiểm tra xem với mỗi đỉnh, tồn tại nhiều nhất bao nhiêu đỉnh có thể đi được từ đỉnh đang xét mà thỏa mãn dữ kiện đề bài

Code full:

#include<bits/stdc++.h>
using namespace std;

const int N = 200;

vector<int> adj[N + 1];
vector<int> res, tmp;
bool visited[N + 1];
int n;

void dfs(int u) {
    visited[u] = true; 
    // đánh dấu đỉnh u đã được thăm
    tmp.push_back(u);
    for (auto v : adj[u]) {
        if (visited[v] == false) {
            // nếu như v chưa được thăm
            dfs(v);
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n;
    int u, v;
    while (cin >> u >> v) {
        adj[u].push_back(v);
        // tức v kề u
    }
    res.assign(n + 1, 0);
    // resize mảng res có kích thước là n + 1
    for (int u = 1; u <= n; u++) {
        memset(visited, false, sizeof (visited));
        // chưa có đỉnh nào đã được thăm
        dfs(u);
        if (tmp.size() < res.size()) {
            swap(tmp, res);
            // nếu như phương án này có thể chọn nhiều nhất số đỉnh thỏa mãn đề bài nhỏ hơn các phương án đã xét trước đó thì minimize vector res bằng cách swap 2 vector với nhau.
        }
        tmp.clear();
        // xóa toàn bộ phần tử ở vector tmp để tiếp tục xét tới các phương án khác
    }
    cout << res.size() << '\n';
    // kích thước mảng res chính là số loại hoa chọn ra được ít nhất mà vẫn thỏa mãn dữ kiện đề bài
    sort(res.begin(), res.end());
    for (auto x : res) {
        cout << x << " ";
        // in ra toàn bộ phần tử ở mảng res
    }
    return 0;
}