Duyệt Đồ Thị (Graph Traversal)

Trong phần II của bài viết này, chúng ta sẽ cùng nhau khám phá hai thuật toán cơ bản trong duyệt đồ thị: Tìm Kiếm Theo Chiều Sâu (Depth-First Search - DFS) và Tìm Kiếm Theo Chiều Rộng (Breadth-First Search - BFS). Cả hai thuật toán này đều bắt đầu từ một nút nguồn và truy cập tất cả các nút có thể truy cập được từ nút nguồn đó. Sự khác biệt duy nhất giữa hai thuật toán này là thứ tự mà chúng truy cập các nút.

1. Tìm Kiếm Theo Chiều Sâu (DFS)

DFS là một thuật toán duyệt đồ thị đơn giản nhưng mạnh mẽ. Khi bắt đầu từ một nút nguồn, thuật toán sẽ tiếp tục di chuyển đến các nút kề cho đến khi không còn nút nào chưa được thăm. Khi gặp nút không còn kề nào chưa thăm, DFS sẽ quay lại các nút trước đó để khám phá những nhánh khác của đồ thị.

Khi thực hiện DFS, các nút đã thăm sẽ được đánh dấu để tránh việc thăm lại, đảm bảo rằng mỗi nút chỉ được truy cập một lần. Độ phức tạp thời gian của thuật toán này là O(n + m), trong đó n là số lượng nút và m là số lượng cạnh trong đồ thị.

Ví dụ, giả sử chúng ta có một đồ thị và chọn nút 1 làm nút nguồn. Quy trình DFS sẽ di chuyển như sau:

1. Từ nút 1, chúng ta di chuyển đến nút 2.
2. Tiếp theo, di chuyển đến nút 3 và sau đó đến nút 5.
3. Tiếp tục quay lại các nút trước khi hoàn thành việc thăm tất cả các nút của đồ thị.

Cài Đặt DFS bằng C++

DFS có thể được triển khai bằng cách sử dụng đệ quy hoặc ngăn xếp (stack). Ở đây, chúng ta sẽ cùng xem cách triển khai cả hai phương thức.

Sử dụng danh sách kề:

vector<int> graph(n);

Sử dụng vector<bool> visited để đánh dấu các nút đã thăm:

vector<bool> visited(n, false);

Phương pháp đệ quy:

void dfs(int s) {
    if(visited[s]) return;
    visited[s] = true;
    // xử lý nút s
    for(auto u : graph[s]) {
        dfs(u);
    }
}

Phương pháp sử dụng Stack:

void dfs(int s) {
    stack<int> st;
    st.push(s);
    visited[s] = true;
    while(!st.empty()) {
        auto cur = st.top();
        st.pop();
        for(auto u : graph[cur]) {
            if(!visited[u]) {
                st.push(u);
                visited[u] = true;
            }
        }
    }
}

Sử dụng ma trận:
Cách này sử dụng vector 2 chiều để lưu trữ đồ thị:

vector<vector<int>> grid(r, vector<int>(c));

Cách sử dụng đệ quy:

void dfs(pair<int, int> s, vector<vector<int>>& grid, vector<vector<bool>>& visited) {
    int x = s.first;
    int y = s.second;
    if (x < 0 || x >= grid.size() || y < 0 || y >= grid[0].size() || visited[x][y] || grid[x][y] != 1) {
        return;
    }
    visited[x][y] = true;
    vector<pair<int, int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    for (const auto& dir : directions) {
        int newX = x + dir.first;
        int newY = y + dir.second;
        dfs(make_pair(newX, newY), grid, visited);
    }
}

Cách sử dụng stack:

void dfs(pair<int, int> start, vector<vector<int>>& grid, vector<vector<bool>>& visited) {
    vector<pair<int, int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    stack<pair<int, int>> s;
    s.push(start);
    while (!s.empty()) {
        pair<int, int> current = s.top();
        s.pop();
        int x = current.first;
        int y = current.second;
        if (x < 0 || x >= grid.size() || y < 0 || y >= grid[0].size() || visited[x][y] || grid[x][y] != 1) {
            continue;
        }
        visited[x][y] = true;
        for (const auto& dir : directions) {
            int newX = x + dir.first;
            int newY = y + dir.second;
            s.push(make_pair(newX, newY));
        }
    }
}

Chúng ta đã tìm hiểu xong về DFS. Trong phần tiếp theo, tôi sẽ giới thiệu về Tìm Kiếm Theo Chiều Rộng (BFS). Hãy cùng chờ xem nhé!
source: viblo