Khóa học CTDL và GT

Bài 18.5. Bài tập tổng hợp về duyệt đồ thị

Chào mừng trở lại với series bài viết chuyên sâu về Cấu trúc dữ liệu và Giải thuật của FullhouseDev!

Chúng ta đã cùng nhau khám phá sức mạnh của đồ thị và hai trong số những thuật toán cơ bản nhưng cực kỳ mạnh mẽ để "đi qua" các đỉnh và cạnh của nó: Tìm kiếm theo chiều rộng (BFS) và Tìm kiếm theo chiều sâu (DFS). Hiểu rõ lý thuyết là một chuyện, nhưng để thực sự làm chủ chúng, việc áp dụng vào giải quyết các bài toán thực tế là không thể thiếu.

Bài viết hôm nay sẽ là sân chơi để chúng ta cùng nhau "vật lộn" với một số dạng bài tập kinh điển liên quan đến duyệt đồ thị. Thông qua các ví dụ cụ thể và minh họa bằng C++, chúng ta sẽ thấy cách BFS và DFS được sử dụng linh hoạt như thế nào để giải quyết các vấn đề khác nhau, từ tìm đường đi ngắn nhất đến xác định các thành phần liên thông hay phát hiện chu trình.

Hãy cùng "lăn xả" vào các bài tập để mài sắc kỹ năng duyệt đồ thị của bạn nhé!

1. Nhắc lại nhanh: BFS và DFS trong "combat"

Trước khi bắt tay vào code, hãy cùng nhau điểm lại một chút tinh thần cốt lõi của BFS và DFS khi đối mặt với một bài toán trên đồ thị:

• BFS (Breadth-First Search): Duyệt "theo lớp". Từ một đỉnh xuất phát, BFS sẽ thăm tất cả các đỉnh kề với nó, sau đó mới đến các đỉnh kề với các đỉnh vừa thăm (chưa được thăm trước đó), và cứ thế tiếp tục. Nó sử dụng hàng đợi (queue) để quản lý thứ tự thăm các đỉnh. BFS thường được dùng để tìm đường đi ngắn nhất (theo số cạnh) trong đồ thị không có trọng số.
• DFS (Depth-First Search): Duyệt "theo chiều sâu". Từ một đỉnh xuất phát, DFS sẽ đi sâu nhất có thể theo một nhánh trước khi quay lui (backtrack) để thăm các nhánh khác. Nó sử dụng ngăn xếp (stack) (hoặc đệ quy, về bản chất cũng dùng stack của hệ thống) để quản lý thứ tự thăm các đỉnh. DFS rất hữu ích trong việc kiểm tra tính liên thông, phát hiện chu trình, sắp xếp tô-pô (trong đồ thị có hướng không chu trình), v.v.

Với hai công cụ sắc bén này trong tay, chúng ta hoàn toàn có thể giải quyết một loạt các vấn đề trên đồ thị. Giờ là lúc áp dụng chúng vào thực tế!

2. Bài tập 1: Tìm đường đi ngắn nhất trong đồ thị không trọng số (Sử dụng BFS)

Đây là một ứng dụng kinh điển và trực quan nhất của BFS.

Bài toán: Cho một đồ thị vô hướng, không trọng số với $N$ đỉnh và $M$ cạnh. Tìm độ dài đường đi ngắn nhất (theo số cạnh) từ đỉnh $S$ đến đỉnh $T$.

Phân tích: Vì đồ thị không có trọng số, đường đi ngắn nhất theo số cạnh chính là đường đi mà BFS tìm thấy đầu tiên khi nó thăm đến đỉnh $T$.

Giải thuật:

1. Sử dụng một hàng đợi q để lưu các đỉnh cần thăm. Ban đầu, thêm đỉnh xuất phát $S$ vào hàng đợi.
2. Sử dụng một mảng dist để lưu khoảng cách từ $S$ đến mỗi đỉnh. Khởi tạo dist[S] = 0, còn các đỉnh khác là vô cực (hoặc -1 để đánh dấu chưa thăm).
3. Sử dụng một mảng visited (hoặc dựa vào giá trị của dist) để đánh dấu các đỉnh đã được thêm vào hàng đợi. Ban đầu, chỉ đỉnh $S$ được đánh dấu là đã thăm (hoặc dist[S] = 0).
4. Trong khi hàng đợi chưa rỗng:
   • Lấy một đỉnh u từ đầu hàng đợi.
   • Nếu u là đỉnh $T$, ta đã tìm thấy đường đi ngắn nhất. Độ dài chính là dist[u]. Kết thúc.
   • Duyệt qua tất cả các đỉnh v kề với u:
     • Nếu v chưa được thăm (ví dụ: dist[v] == -1):
       • Cập nhật khoảng cách: dist[v] = dist[u] + 1.
       • Đánh dấu v đã thăm.
       • Thêm v vào cuối hàng đợi.
5. Nếu hàng đợi rỗng mà chưa gặp đỉnh $T$, nghĩa là $T$ không thể đạt được từ $S$.

Ví dụ minh họa (C++):

Giả sử đồ thị có 6 đỉnh (0 đến 5) và các cạnh sau: (0, 1), (0, 2), (1, 3), (2, 3), (2, 4), (3, 5), (4, 5). Tìm đường đi ngắn nhất từ đỉnh 0 đến đỉnh 5.

#include <iostream>
#include <vector>
#include <queue>
#include <limits> // For numeric_limits

using namespace std;

const int INF = numeric_limits<int>::max(); // Sử dụng giá trị vô cực cho khoảng cách

int bfs_shortest_path(const vector<vector<int>>& adj, int start_node, int end_node, int num_nodes) {
    // Vector lưu khoảng cách từ start_node đến mỗi đỉnh
    vector<int> dist(num_nodes, -1); // Khởi tạo -1 để đánh dấu chưa thăm

    // Hàng đợi cho BFS
    queue<int> q;

    // Khởi tạo cho đỉnh bắt đầu
    dist[start_node] = 0;
    q.push(start_node);

    // Bắt đầu BFS
    while (!q.empty()) {
        int u = q.front();
        q.pop();

        // Nếu đã đến đỉnh đích
        if (u == end_node) {
            return dist[u]; // Trả về khoảng cách tìm được
        }

        // Duyệt qua các đỉnh kề với u
        for (int v : adj[u]) {
            // Nếu v chưa được thăm (-1)
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1; // Cập nhật khoảng cách
                q.push(v);             // Thêm v vào hàng đợi
            }
        }
    }

    // Nếu không tìm thấy đường đi đến end_node
    return -1;
}

int main() {
    int num_nodes = 6;
    // Sử dụng adjacency list để biểu diễn đồ thị
    vector<vector<int>> adj(num_nodes);

    // Thêm các cạnh (đồ thị vô hướng)
    adj[0].push_back(1); adj[1].push_back(0);
    adj[0].push_back(2); adj[2].push_back(0);
    adj[1].push_back(3); adj[3].push_back(1);
    adj[2].push_back(3); adj[3].push_back(2);
    adj[2].push_back(4); adj[4].push_back(2);
    adj[3].push_back(5); adj[5].push_back(3);
    adj[4].push_back(5); adj[5].push_back(4);

    int start_node = 0;
    int end_node = 5;

    int shortest_dist = bfs_shortest_path(adj, start_node, end_node, num_nodes);

    if (shortest_dist != -1) {
        cout << "Do dai duong di ngan nhat tu " << start_node << " den " << end_node << " la: " << shortest_dist << endl;
    } else {
        cout << "Khong co duong di tu " << start_node << " den " << end_node << endl;
    }

    // Output mong đợi: Do dai duong di ngan nhat tu 0 den 5 la: 2 (0 -> 2 -> 5 hoac 0 -> 1 -> 3 -> 5)
    // Chú ý: BFS tìm khoảng cách 2 thông qua cả đường 0-2-5 và 0-1-3-5. Khoảng cách là 2 vì 0-2-5 có 2 cạnh.

    return 0;
}

Giải thích Code:

1. Chúng ta sử dụng vector<vector<int>> adj để biểu diễn đồ thị bằng danh sách kề. adj[i] chứa danh sách các đỉnh kề với đỉnh i.
2. Mảng dist được khởi tạo với giá trị -1 cho tất cả các đỉnh, biểu thị rằng chưa có đỉnh nào được thăm và khoảng cách chưa được biết. dist[start_node] được đặt bằng 0.
3. queue<int> q lưu trữ các đỉnh sẽ được thăm tiếp theo.
4. Vòng lặp while (!q.empty()) là trái tim của BFS. Chúng ta lần lượt lấy đỉnh u từ đầu hàng đợi.
5. Nếu u là đỉnh đích end_node, chúng ta đã tìm thấy đường đi ngắn nhất và trả về dist[u].
6. Với mỗi đỉnh v kề với u, chúng ta kiểm tra xem dist[v] có bằng -1 không (tức là v chưa được thăm).
7. Nếu v chưa thăm, ta cập nhật dist[v] = dist[u] + 1 (khoảng cách đến v là khoảng cách đến u cộng thêm 1 cạnh) và thêm v vào hàng đợi. Điều này đảm bảo rằng chúng ta thăm các đỉnh theo từng "lớp" khoảng cách tăng dần.
8. Nếu vòng lặp kết thúc mà không tìm thấy end_node (hàng đợi rỗng), nghĩa là không có đường đi từ start_node đến end_node, và chúng ta trả về -1.

3. Bài tập 2: Đếm số thành phần liên thông (Sử dụng DFS)

DFS rất tự nhiên trong việc khám phá toàn bộ một "khu vực" liên thông của đồ thị.

Bài toán: Cho một đồ thị vô hướng với $N$ đỉnh và $M$ cạnh. Đếm số lượng các thành phần liên thông trong đồ thị.

Phân tích: Một thành phần liên thông là một tập hợp con lớn nhất các đỉnh sao cho giữa bất kỳ hai đỉnh nào trong tập hợp đó đều có đường đi. Chúng ta có thể dùng DFS (hoặc BFS) để thăm toàn bộ các đỉnh trong một thành phần liên thông bắt đầu từ một đỉnh bất kỳ trong thành phần đó.

Giải thuật:

1. Sử dụng một mảng visited để đánh dấu các đỉnh đã được thăm trong quá trình duyệt. Khởi tạo tất cả đỉnh là chưa thăm.
2. Sử dụng một biến đếm count khởi tạo bằng 0.
3. Duyệt qua tất cả các đỉnh từ 0 đến $N-1$.
4. Nếu một đỉnh i chưa được thăm:
   • Tăng biến đếm count lên 1 (chúng ta vừa tìm thấy một thành phần liên thông mới).
   • Bắt đầu một cuộc duyệt DFS (hoặc BFS) từ đỉnh i. Trong quá trình duyệt này, đánh dấu tất cả các đỉnh mà DFS/BFS đi qua là đã thăm.
5. Sau khi duyệt hết tất cả các đỉnh từ 0 đến $N-1$, biến đếm count sẽ chứa tổng số thành phần liên thông.

Ví dụ minh họa (C++):

Giả sử đồ thị có 7 đỉnh (0 đến 6) và các cạnh sau: (0, 1), (0, 2), (1, 2), (3, 4), (5, 6). Rõ ràng có 3 thành phần liên thông: {0, 1, 2}, {3, 4}, {5, 6}.

#include <iostream>
#include <vector>
#include <stack> // Có thể dùng stack cho DFS, hoặc đơn giản hơn là dùng đệ quy

using namespace std;

// Hàm DFS đệ quy để thăm tất cả các đỉnh trong một thành phần liên thông
void dfs_visit(const vector<vector<int>>& adj, int u, vector<bool>& visited) {
    visited[u] = true; // Đánh dấu đỉnh hiện tại đã thăm

    // Duyệt qua các đỉnh kề với u
    for (int v : adj[u]) {
        // Nếu v chưa được thăm, thực hiện DFS trên v
        if (!visited[v]) {
            dfs_visit(adj, v, visited);
        }
    }
}

int count_connected_components(const vector<vector<int>>& adj, int num_nodes) {
    // Mảng visited để theo dõi các đỉnh đã được thăm
    vector<bool> visited(num_nodes, false);
    int count = 0; // Biến đếm số thành phần liên thông

    // Duyệt qua tất cả các đỉnh
    for (int i = 0; i < num_nodes; ++i) {
        // Nếu đỉnh i chưa được thăm, nó là khởi đầu của một thành phần liên thông mới
        if (!visited[i]) {
            count++; // Tăng số lượng thành phần
            dfs_visit(adj, i, visited); // Thực hiện DFS để thăm hết các đỉnh trong thành phần này
        }
    }

    return count;
}

int main() {
    int num_nodes = 7;
    vector<vector<int>> adj(num_nodes);

    // Thêm các cạnh cho ví dụ
    adj[0].push_back(1); adj[1].push_back(0);
    adj[0].push_back(2); adj[2].push_back(0);
    adj[1].push_back(2); adj[2].push_back(1);

    adj[3].push_back(4); adj[4].push_back(3);

    adj[5].push_back(6); adj[6].push_back(5);

    int components = count_connected_components(adj, num_nodes);

    cout << "So luong thanh phan lien thong trong do thi la: " << components << endl;

    // Output mong đợi: So luong thanh phan lien thong trong do thi la: 3

    return 0;
}

Giải thích Code:

1. Hàm dfs_visit là một hàm trợ giúp dùng đệ quy. Nó nhận đồ thị (adj), đỉnh hiện tại u, và mảng visited. Nhiệm vụ của nó là đi sâu vào đồ thị từ u và đánh dấu tất cả các đỉnh reachable từ u (trong cùng một thành phần) là true trong mảng visited.
2. Hàm chính count_connected_components khởi tạo mảng visited và biến đếm count.
3. Nó lặp qua tất cả các đỉnh i từ 0 đến num_nodes - 1.
4. Nếu visited[i] là false, điều này có nghĩa là đỉnh i chưa được thăm và nó thuộc về một thành phần liên thông mới mà chúng ta chưa khám phá.
5. Khi đó, chúng ta tăng count lên 1 và gọi dfs_visit bắt đầu từ đỉnh i. Cuộc gọi dfs_visit này sẽ thăm và đánh dấu tất cả các đỉnh trong cùng thành phần với i.
6. Sau khi vòng lặp kết thúc, mỗi lần chúng ta bắt đầu một DFS mới (khi gặp !visited[i]), điều đó tương ứng với việc khám phá một thành phần liên thông riêng biệt. Do đó, count chính là số lượng thành phần liên thông.

4. Bài tập 3: Phát hiện chu trình trong đồ thị có hướng (Sử dụng DFS)

Phát hiện chu trình là một bài toán quan trọng, đặc biệt là trong đồ thị có hướng khi cần thực hiện sắp xếp tô-pô. DFS có thể giúp chúng ta làm điều này một cách hiệu quả.

Bài toán: Cho một đồ thị có hướng với $N$ đỉnh và $M$ cạnh. Xác định xem đồ thị có chứa ít nhất một chu trình hay không.

Phân tích: Trong đồ thị có hướng, chu trình tồn tại nếu trong quá trình duyệt DFS, chúng ta gặp lại một đỉnh mà đỉnh đó đang nằm trong đường đi hiện tại từ đỉnh xuất phát DFS. Để theo dõi điều này, chúng ta cần nhiều hơn một trạng thái "đã thăm". Chúng ta cần ít nhất ba trạng thái: chưa thăm, đang thăm (trong stack đệ quy hiện tại), đã thăm xong (không còn trong stack đệ quy).

Giải thuật:

1. Sử dụng một mảng visited_state để lưu trạng thái của mỗi đỉnh. Có thể dùng 3 giá trị:
   • 0: Chưa thăm.
   • 1: Đang thăm (đang trong stack đệ quy của DFS).
   • 2: Đã thăm xong (đã thoát khỏi stack đệ quy). Khởi tạo tất cả đỉnh với trạng thái 0.
2. Duyệt qua tất cả các đỉnh từ 0 đến $N-1$.
3. Nếu một đỉnh i có trạng thái 0 (chưa thăm), gọi hàm DFS kiểm tra chu trình bắt đầu từ đỉnh i.
4. Hàm DFS kiểm tra chu trình has_cycle_util(u):
   • Đặt trạng thái của đỉnh u thành 1 (đang thăm).
   • Duyệt qua tất cả các đỉnh v kề với u:
     • Nếu trạng thái của v là 1, nghĩa là v đang trong stack đệ quy hiện tại -> tìm thấy chu trình. Trả về true.
     • Nếu trạng thái của v là 0, gọi đệ quy has_cycle_util(v). Nếu cuộc gọi này trả về true, nghĩa là có chu trình ở nhánh con -> trả về true.
   • Sau khi duyệt hết tất cả các đỉnh kề và không tìm thấy chu trình, đặt trạng thái của đỉnh u thành 2 (đã thăm xong).
   • Trả về false (không tìm thấy chu trình bắt đầu từ nhánh u).
5. Nếu bất kỳ cuộc gọi has_cycle_util nào trả về true, hàm chính sẽ trả về true.
6. Nếu duyệt hết tất cả các đỉnh mà không có cuộc gọi nào trả về true, nghĩa là không có chu trình trong đồ thị. Trả về false.

Ví dụ minh họa (C++):

Giả sử đồ thị có hướng 5 đỉnh (0 đến 4) và các cạnh: (0, 1), (0, 2), (1, 2), (2, 3), (3, 4), (4, 2). Chu trình tồn tại: 2 -> 3 -> 4 -> 2.

#include <iostream>
#include <vector>

using namespace std;

// Hàm DFS đệ quy để kiểm tra chu trình
// visited_state: 0 = chua tham, 1 = dang tham (trong stack de quy), 2 = da tham xong
bool has_cycle_util(const vector<vector<int>>& adj, int u, vector<int>& visited_state) {
    visited_state[u] = 1; // Danh dau dang tham

    // Duyet qua cac dinh ke cua u
    for (int v : adj[u]) {
        if (visited_state[v] == 1) {
            // Gap lai mot dinh dang trong stack de quy -> co chu trinh
            return true;
        }
        if (visited_state[v] == 0) {
            // Neu dinh v chua tham, tiep tuc DFS
            if (has_cycle_util(adj, v, visited_state)) {
                return true; // Tim thay chu trinh o nhanh con
            }
        }
        // Neu visited_state[v] == 2 (da tham xong), bo qua vinh vien
    }

    visited_state[u] = 2; // Danh dau da tham xong khi thoat khoi de quy cua dinh u
    return false; // Khong tim thay chu trinh tu nhanh nay
}

bool has_cycle_directed(const vector<vector<int>>& adj, int num_nodes) {
    // Mang luu trang thai tham cua cac dinh
    vector<int> visited_state(num_nodes, 0); // 0: chua tham, 1: dang tham, 2: da tham xong

    // Duyet qua tat ca cac dinh de dam bao xet het cac thanh phan lien thong
    for (int i = 0; i < num_nodes; ++i) {
        if (visited_state[i] == 0) {
            // Neu dinh i chua tham, bat dau DFS tu i
            if (has_cycle_util(adj, i, visited_state)) {
                return true; // Tim thay chu trinh
            }
        }
    }

    return false; // Khong tim thay chu trinh sau khi duyet het do thi
}

int main() {
    int num_nodes = 5;
    // Su dung adjacency list de bieu dien do thi co huong
    vector<vector<int>> adj(num_nodes);

    // Them cac canh cho vi du co chu trinh
    adj[0].push_back(1);
    adj[0].push_back(2);
    adj[1].push_back(2);
    adj[2].push_back(3);
    adj[3].push_back(4);
    adj[4].push_back(2); // Canh tao chu trinh: 2 -> 3 -> 4 -> 2

    bool cycle_exists = has_cycle_directed(adj, num_nodes);

    if (cycle_exists) {
        cout << "Do thi co huong co chua chu trinh." << endl;
    } else {
        cout << "Do thi co huong khong chua chu trinh." << endl;
    }

    // Output mong doi: Do thi co huong co chua chu trinh.

    // Vi du khong co chu trinh (Do thi co huong khong chu trinh - DAG)
    vector<vector<int>> adj_no_cycle(5);
    adj_no_cycle[0].push_back(1);
    adj_no_cycle[0].push_back(2);
    adj_no_cycle[1].push_back(3);
    adj_no_cycle[2].push_back(3);
    adj_no_cycle[3].push_back(4);

    bool cycle_exists_no = has_cycle_directed(adj_no_cycle, num_nodes);
    if (cycle_exists_no) {
         cout << "Do thi co huong co chua chu trinh (vi du 2)." << endl;
    } else {
         cout << "Do thi co huong khong chua chu trinh (vi du 2)." << endl;
    }
    // Output mong doi: Do thi co huong khong chua chu trinh (vi du 2).


    return 0;
}

Giải thích Code:

1. Chúng ta sử dụng mảng visited_state với ba trạng thái (0, 1, 2) như đã mô tả trong giải thuật. Trạng thái 1 (đang thăm) là chìa khóa để phát hiện chu trình trong đồ thị có hướng.
2. Hàm has_cycle_util(u) thực hiện DFS đệ quy. Khi vào hàm với đỉnh u, ta đặt visited_state[u] = 1.
3. Trong vòng lặp duyệt các đỉnh kề v của u:
   • Nếu visited_state[v] == 1, điều này chỉ xảy ra khi v là một tổ tiên của u trong cây DFS hiện tại và v chưa bị đánh dấu là 2 (đã thăm xong). Gặp đỉnh v trong trạng thái 1 từ đỉnh u tạo thành một cạnh ngược (back edge) trong cây DFS, chỉ ra sự tồn tại của chu trình. Ta trả về true ngay lập tức.
   • Nếu visited_state[v] == 0, v chưa thăm. Ta tiếp tục đệ quy has_cycle_util(v). Nếu cuộc gọi đệ quy này tìm thấy chu trình ở bất kỳ đâu trong nhánh con của v, nó sẽ trả về true, và chúng ta cũng trả về true.
   • Nếu visited_state[v] == 2, nghĩa là đỉnh v và toàn bộ nhánh con của nó đã được thăm xong và không có chu trình. Chúng ta bỏ qua đỉnh v.
4. Sau khi duyệt hết tất cả các đỉnh kề của u mà không tìm thấy chu trình, điều đó có nghĩa là nhánh từ u không tạo ra chu trình ngược nào với các đỉnh đang thăm. Ta đặt visited_state[u] = 2 và trả về false.
5. Hàm chính has_cycle_directed lặp qua tất cả các đỉnh. Nếu gặp một đỉnh chưa thăm (visited_state[i] == 0), ta bắt đầu một cuộc gọi has_cycle_util(i). Nếu bất kỳ cuộc gọi nào trả về true, đồ thị có chu trình và hàm chính trả về true. Nếu duyệt hết mà không tìm thấy chu trình nào, trả về false.

Bài tập ví dụ:

[Graph].DFS trên đồ thị có hướng.

Cho đồ thị có hướng G = (V, E) được biểu diễn dưới dạng danh sách cạnh. Hãy thực hiện in ra danh sách các đỉnh được duyệt theo thuật toán DFS(s).

Input Format

Dòng đầu tiên là 2 số n và m và s, tương ứng với số lượng đỉnh, cạnh của đồ thị và đỉnh bắt đầu duyệt. Các đỉnh của đồ thị được đánh số từ 1 tới n. m dòng tiếp theo mỗi dòng chứa đỉnh u, v (u != v) tương ứng với một cạnh của đồ thị. (1<=s<=n<=1000; 1<=m<=n*(n-1)/2)

Constraints

.

Output Format

In ra các đỉnh được duyệt theo thuật toán DFS(s). Chú ý trong quá trình mở rộng các đỉnh của thuật toán DFS luôn lựa chọn duyệt các đỉnh có thứ tự nhỏ hơn trước.

Ví dụ:

Dữ liệu vào

5 9 1
1 2
1 3
1 4
2 1
2 4
2 5
3 4
3 5
4 5

Dữ liệu ra

1 2 4 5 3

Đây là hướng dẫn giải bài [Graph].DFS trên đồ thị có hướng bằng C++:

1. Đọc Input: Đọc số đỉnh n, số cạnh m, và đỉnh bắt đầu s.
2. Biểu diễn đồ thị: Sử dụng danh sách kề (adjacency list). Do các đỉnh được đánh số từ 1 đến n, dùng vector<vector<int>> adj có kích thước n+1. Duyệt qua m cạnh, với mỗi cạnh u v, thêm v vào danh sách kề của u (adj[u].push_back(v)).
3. Sắp xếp danh sách kề: Để đảm bảo duyệt các đỉnh có thứ tự nhỏ hơn trước theo yêu cầu, sau khi đọc tất cả các cạnh, duyệt qua adj[i] cho mỗi đỉnh i từ 1 đến n và sắp xếp (sort) danh sách các đỉnh kề này theo thứ tự tăng dần.
4. Mảng visited: Khởi tạo một mảng boolean visited có kích thước n+1, tất cả các giá trị ban đầu là false. Mảng này dùng để đánh dấu các đỉnh đã được duyệt.
5. Hàm DFS đệ quy: Xây dựng một hàm void dfs(int u, vector<vector<int>>& adj, vector<bool>& visited):
   • Đánh dấu đỉnh u đã được thăm (visited[u] = true).
   • In đỉnh u.
   • Duyệt qua tất cả các đỉnh kề v của u trong adj[u] (lúc này đã được sắp xếp).
   • Nếu đỉnh v chưa được thăm (!visited[v]), gọi đệ quy dfs(v, adj, visited).
6. Thực hiện DFS: Từ hàm main, gọi hàm dfs(s, adj, visited) để bắt đầu quá trình duyệt từ đỉnh s.

Làm thêm nhiều bài tập miễn phí tại đây