Khóa học CTDL và GT

Bài 18.4. Tìm đường đi trên đồ thị dùng BFS và DFS

Chào mừng trở lại với series Cấu trúc dữ liệu và Giải thuật của chúng ta! Sau khi đã làm quen với cách biểu diễn đồ thị và hai giải thuật duyệt đồ thị cơ bản là BFS và DFS, hôm nay chúng ta sẽ áp dụng ngay những kiến thức quý báu đó để giải quyết một bài toán rất thực tế và quan trọng: Tìm đường đi giữa hai đỉnh bất kỳ trên đồ thị.

Việc tìm đường đi là nền tảng cho rất nhiều ứng dụng, từ tìm đường trên bản đồ (Google Maps chẳng hạn), phân tích mạng xã hội, cho đến các bài toán về game (tìm đường đi cho nhân vật) hay mạng máy tính (tìm đường đi của gói tin). Chúng ta sẽ khám phá cách mà BFS và DFS, với những đặc điểm duyệt khác nhau, có thể được điều chỉnh để không chỉ duyệt qua các đỉnh mà còn ghi lại được con đường đã đi qua.

Hãy cùng nhau đi sâu vào chi tiết nhé!

1. Tìm đường đi bằng Breadth-First Search (BFS)

Như chúng ta đã biết, BFS duyệt đồ thị theo từng lớp (layer) hoặc từng mức (level). Nó bắt đầu từ đỉnh nguồn, thăm tất cả các đỉnh kề với đỉnh nguồn, sau đó thăm tất cả các đỉnh kề với các đỉnh đã thăm ở mức trước đó, và cứ thế lan rộng ra. Chính đặc điểm "lan rộng đều" này mang lại một ưu điểm cực kỳ quan trọng khi tìm đường đi trên đồ thị không có trọng số: BFS luôn tìm thấy đường đi ngắn nhất (theo số lượng cạnh).

Để sử dụng BFS để tìm đường đi, chúng ta cần làm thêm một bước trong quá trình duyệt: ghi lại đỉnh "cha" (parent) của mỗi đỉnh khi chúng ta lần đầu tiên thăm nó. Đỉnh cha chính là đỉnh mà từ đó chúng ta đi đến đỉnh hiện tại. Khi tìm thấy đỉnh đích, chúng ta có thể tái tạo lại đường đi bằng cách đi ngược lại từ đỉnh đích theo các đỉnh cha cho đến khi về tới đỉnh nguồn.

Các bước thực hiện:

1. Khởi tạo một hàng đợi (queue) để lưu trữ các đỉnh cần thăm.
2. Khởi tạo một mảng/map visited để đánh dấu các đỉnh đã thăm, ban đầu tất cả là false.
3. Khởi tạo một mảng/map parent để lưu đỉnh cha của mỗi đỉnh. Ban đầu, có thể đặt giá trị đặc biệt (ví dụ: -1) cho tất cả.
4. Đưa đỉnh nguồn (start_node) vào hàng đợi và đánh dấu visited[start_node] = true. Đặt parent[start_node] = -1 (hoặc một giá trị chỉ ra đây là đỉnh gốc).
5. Trong khi hàng đợi chưa rỗng:
   • Lấy một đỉnh u ra khỏi hàng đợi.
   • Nếu u là đỉnh đích (end_node), chúng ta đã tìm thấy đường đi. Dừng quá trình duyệt.
   • Với mỗi đỉnh kề v của u:
     • Nếu v chưa được thăm (visited[v] == false):
       • Đánh dấu visited[v] = true.
       • Đặt parent[v] = u.
       • Đưa v vào hàng đợi.
6. Sau khi quá trình BFS dừng (hoặc hàng đợi rỗng), nếu đỉnh đích đã được thăm (visited[end_node] == true), chúng ta tái tạo lại đường đi:
   • Bắt đầu từ đỉnh đích current = end_node.
   • Thêm current vào danh sách đường đi.
   • Di chuyển đến đỉnh cha của current: current = parent[current].
   • Lặp lại cho đến khi current là đỉnh nguồn (hoặc parent[current] là -1).
   • Danh sách đường đi lúc này đang theo chiều ngược lại (từ đích về nguồn), cần đảo ngược lại để có đường đi từ nguồn đến đích.
7. Nếu đỉnh đích không bao giờ được thăm, có nghĩa là không có đường đi từ nguồn đến đích.

Ví dụ C++ minh họa cho BFS tìm đường đi:

Giả sử chúng ta có đồ thị vô hướng sau:

0 -- 1 -- 3
| \  |
|  \ |
4 -- 2 -- 5

Chúng ta muốn tìm đường đi từ đỉnh 0 đến đỉnh 5.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm> // For std::reverse

using namespace std;

// Hàm tìm đường đi bằng BFS
vector<int> find_path_bfs(const vector<vector<int>>& adj, int start_node, int end_node) {
    int num_vertices = adj.size();
    vector<int> parent(num_vertices, -1); // Lưu đỉnh cha
    vector<bool> visited(num_vertices, false); // Đánh dấu đỉnh đã thăm
    queue<int> q; // Hàng đợi cho BFS

    // Bắt đầu từ đỉnh nguồn
    q.push(start_node);
    visited[start_node] = true;
    // parent[start_node] đã là -1 mặc định

    bool found = false;

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        // Nếu tìm thấy đỉnh đích
        if (u == end_node) {
            found = true;
            break; // Dừng BFS ngay khi tìm thấy đích
        }

        // Duyệt qua các đỉnh kề
        for (int v : adj[u]) {
            if (!visited[v]) {
                visited[v] = true;
                parent[v] = u; // Lưu lại đỉnh cha
                q.push(v);
            }
        }
    }

    // Tái tạo lại đường đi nếu tìm thấy
    vector<int> path;
    if (found) {
        int current = end_node;
        while (current != -1) {
            path.push_back(current);
            current = parent[current];
        }
        reverse(path.begin(), path.end()); // Đảo ngược để có đường đi từ nguồn đến đích
    }

    return path; // Trả về đường đi (rỗng nếu không tìm thấy)
}

int main() {
    // Biểu diễn đồ thị bằng danh sách kề (adjacency list)
    // Đồ thị vô hướng với 6 đỉnh (0 đến 5)
    vector<vector<int>> adj(6);
    adj[0].push_back(1);
    adj[0].push_back(2);
    adj[0].push_back(4);
    adj[1].push_back(0);
    adj[1].push_back(2);
    adj[1].push_back(3);
    adj[2].push_back(0);
    adj[2].push_back(1);
    adj[2].push_back(4);
    adj[2].push_back(5);
    adj[3].push_back(1);
    adj[4].push_back(0);
    adj[4].push_back(2);
    adj[5].push_back(2);

    int start = 0;
    int end = 5;

    cout << "Tim duong di tu " << start << " den " << end << " bang BFS:" << endl;
    vector<int> path = find_path_bfs(adj, start, end);

    if (!path.empty()) {
        cout << "Duong di tim thay: ";
        for (size_t i = 0; i < path.size(); ++i) {
            cout << path[i] << (i == path.size() - 1 ? "" : " -> ");
        }
        cout << endl;
    } else {
        cout << "Khong tim thay duong di." << endl;
    }

    // Ví dụ khác: tìm đường đi không tồn tại
    int start2 = 3;
    int end2 = 5; // Giả sử đỉnh 3 và 5 không có đường đi (trong đồ thị này thì có, nhưng ví dụ cho trường hợp không có)
    // Để minh họa trường hợp không có đường đi, hãy thử tìm từ 3 đến một đỉnh không liên thông, ví dụ 6 nếu đồ thị lớn hơn
    // Trong đồ thị hiện tại, mọi đỉnh đều liên thông. Giả sử start=0, end=10 trong đồ thị 6 đỉnh.

    cout << "\nTim duong di tu 0 den 10 (khong ton tai) bang BFS:" << endl;
    vector<vector<int>> adj_small(6); // Dùng lại đồ thị cũ
    // ... (copy adjacency list setup from above)
    adj_small[0].push_back(1); adj_small[0].push_back(2); adj_small[0].push_back(4);
    adj_small[1].push_back(0); adj_small[1].push_back(2); adj_small[1].push_back(3);
    adj_small[2].push_back(0); adj_small[2].push_back(1); adj_small[2].push_back(4); adj_small[2].push_back(5);
    adj_small[3].push_back(1);
    adj_small[4].push_back(0); adj_small[4].push_back(2);
    adj_small[5].push_back(2);

    int start_nonexistent = 0;
    int end_nonexistent = 10; // Đỉnh không tồn tại

    // Cần kiểm tra đỉnh đích có hợp lệ không trước khi gọi hàm
    if (end_nonexistent >= 0 && end_nonexistent < adj_small.size()) {
        vector<int> path_nonexistent = find_path_bfs(adj_small, start_nonexistent, end_nonexistent);
         if (!path_nonexistent.empty()) {
             // Code này sẽ không chạy vì end_nonexistent > adj_small.size() - 1
         } else {
             cout << "Khong tim thay duong di." << endl;
         }
    } else {
         cout << "Dinh dich khong hop le." << endl;
    }


    return 0;
}

Giải thích Code BFS:

• Chúng ta sử dụng std::vector<std::vector<int>> adj để biểu diễn đồ thị bằng danh sách kề. Mỗi phần tử adj[i] là một vector chứa các đỉnh kề với đỉnh i.
• parent là một std::vector<int> cùng kích thước với số đỉnh, lưu đỉnh cha của mỗi đỉnh. parent[v] = u nghĩa là chúng ta đi từ u đến v. Giá trị -1 cho đỉnh nguồn hoặc các đỉnh chưa được thăm từ bất kỳ đâu.
• visited là std::vector<bool> để tránh việc thăm lại các đỉnh đã xử lý, giúp đảm bảo mỗi đỉnh được thêm vào hàng đợi và xử lý duy nhất một lần.
• q là std::queue<int>, cấu trúc dữ liệu trung tâm của BFS, giúp chúng ta duyệt theo từng lớp.
• Chúng ta bắt đầu bằng cách đưa đỉnh nguồn vào hàng đợi và đánh dấu đã thăm.
• Vòng lặp while (!q.empty()) là trái tim của BFS. Chúng ta lấy đỉnh u ra khỏi hàng đợi, kiểm tra xem nó có phải là đích không.
• Sau đó, chúng ta duyệt qua tất cả các đỉnh kề v của u. Nếu v chưa được thăm, chúng ta đánh dấu nó đã thăm, đặt đỉnh cha của v là u (parent[v] = u), và đưa v vào hàng đợi. Bước đặt parent[v] = u này là quan trọng nhất để tái tạo đường đi.
• Nếu u là đỉnh đích, chúng ta đặt cờ found = true và dùng break để dừng sớm BFS.
• Sau vòng lặp BFS, nếu found là true, chúng ta tái tạo đường đi. Bắt đầu từ end_node, chúng ta thêm nó vào vector path, sau đó nhảy lên đỉnh cha của nó (parent[end_node]), rồi đỉnh cha của đỉnh đó, và cứ thế cho đến khi gặp đỉnh có parent là -1 (đỉnh nguồn).
• Cuối cùng, chúng ta dùng std::reverse để đảo ngược vector path vì nó đang chứa đường đi từ đích về nguồn.
• Nếu found vẫn là false sau khi hàng đợi rỗng, hoặc nếu đỉnh đích không hợp lệ (như trong ví dụ thứ hai), vector path sẽ rỗng, chỉ ra rằng không có đường đi.

Ưu điểm của BFS cho bài toán tìm đường đi trên đồ thị không trọng số là nó luôn tìm ra đường đi có ít cạnh nhất. Điều này rất hữu ích khi bạn cần đường đi "thẳng" nhất hoặc "ngắn" nhất tính theo số bước nhảy.

2. Tìm đường đi bằng Depth-First Search (DFS)

DFS duyệt đồ thị theo chiều sâu. Nó đi sâu vào một nhánh càng xa càng tốt trước khi quay lui (backtrack) để khám phá các nhánh khác. Để sử dụng DFS để tìm một đường đi (không nhất thiết là đường đi ngắn nhất) từ đỉnh nguồn đến đỉnh đích, chúng ta cũng cần theo dõi đường đi hiện tại đang khám phá.

Phương pháp phổ biến để làm điều này với DFS là sử dụng đệ quy và truyền theo danh sách các đỉnh đã đi qua trên đường đi hiện tại, hoặc sử dụng một mảng parent tương tự BFS nhưng cần quản lý cẩn thận hơn do cơ chế quay lui. Cách dùng đệ quy và lưu đường đi trong tham số là khá trực quan.

Các bước thực hiện (sử dụng đệ quy và lưu đường đi tạm thời):

1. Khởi tạo một mảng/map visited để đánh dấu các đỉnh đã thăm trong quá trình tìm kiếm tổng thể, ban đầu tất cả là false. Điều này giúp tránh lặp vô hạn trong đồ thị có chu trình.
2. Sử dụng một hàm đệ quy, ví dụ find_path_dfs_recursive(current_node, target_node, visited, adj, current_path, result_path).
   • current_node: Đỉnh hiện tại đang xét.
   • target_node: Đỉnh đích cần tìm.
   • visited: Mảng/map đánh dấu các đỉnh đã thăm (toàn cục hoặc truyền theo tham chiếu).
   • adj: Biểu diễn đồ thị.
   • current_path: Vector lưu trữ đường đi từ nguồn đến current_node trong lần đệ quy hiện tại.
   • result_path: Vector để lưu đường đi cuối cùng nếu tìm thấy (truyền theo tham chiếu).
3. Trong hàm đệ quy find_path_dfs_recursive(u, target, visited, adj, current_path, result_path):
   • Đánh dấu đỉnh hiện tại u đã thăm: visited[u] = true.
   • Thêm u vào current_path.
   • Trường hợp cơ sở: Nếu u là đỉnh đích (u == target), chúng ta đã tìm thấy một đường đi. Sao chép current_path vào result_path và trả về true.
   • Bước đệ quy: Với mỗi đỉnh kề v của u:
     • Nếu v chưa được thăm (!visited[v]):
       • Gọi đệ quy: find_path_dfs_recursive(v, target, visited, adj, current_path, result_path).
       • Nếu lời gọi đệ quy này trả về true (nghĩa là tìm thấy đích từ v), thì đường đi đã hoàn thành. Trả về true ngay lập tức.
   • Quay lui (Backtracking): Nếu sau khi thử tất cả các đỉnh kề mà không tìm thấy đích, điều này có nghĩa là đỉnh u hiện tại không nằm trên đường đi thành công. Chúng ta cần quay lui:
     • Xóa u khỏi cuối current_path (current_path.pop_back()).
     • Đánh dấu u là chưa thăm lại (visited[u] = false). Điều này quan trọng để cho phép các nhánh khác của DFS có thể đi qua đỉnh u này như một phần của một con đường khác. (Lưu ý: Nếu bạn chỉ muốn tìm một đường đi bất kỳ, không cần đánh dấu lại là chưa thăm, chỉ cần xóa khỏi current_path thôi). Tuy nhiên, cách đánh dấu lại cho phép tìm kiếm linh hoạt hơn hoặc tìm tất cả các đường đi (với biến đổi nhỏ). Ở đây, chúng ta tìm một đường đi nên việc đánh dấu lại là không bắt buộc nếu bạn chỉ cần dừng ở đường đi đầu tiên tìm thấy. Để đơn giản cho việc tìm một đường đi, chúng ta chỉ cần visited toàn cục mà không cần unmark. Hãy điều chỉnh lại bước 1 và 3: visited chỉ dùng để tránh lặp vô hạn trong chu trình, không cần unmark khi quay lui nếu chỉ tìm 1 path.

Các bước thực hiện (làm lại, đơn giản hơn cho tìm một đường đi):

1. Khởi tạo mảng visited toàn cục (hoặc truyền reference), ban đầu false.
2. Khởi tạo vector path toàn cục (hoặc truyền reference) để lưu đường đi tìm được.
3. Sử dụng hàm đệ quy bool find_path_dfs_recursive(u, target, visited, adj, current_path):
   • u: Đỉnh hiện tại.
   • target: Đỉnh đích.
   • visited: Mảng visited (truyền reference).
   • adj: Danh sách kề (truyền const reference).
   • current_path: Vector để xây dựng đường đi hiện tại (truyền reference).
   • Thêm u vào current_path.
   • Đánh dấu visited[u] = true.
   • Trường hợp cơ sở: Nếu u == target, trả về true (đã tìm thấy đích).
   • Bước đệ quy: Với mỗi đỉnh kề v của u:
     • Nếu !visited[v]:
       • Gọi đệ quy find_path_dfs_recursive(v, target, visited, adj, current_path).
       • Nếu lời gọi này trả về true, có nghĩa là đã tìm thấy đường đi từ v đến đích. Vì u đang ở trên đường đi đến v, nên u cũng nằm trên đường đi đến đích. Trả về true ngay lập tức.
   • Quay lui (Backtracking): Nếu vòng lặp kết thúc mà không tìm thấy đích từ bất kỳ đỉnh kề nào, điều này có nghĩa là không có đường đi từ u đến đích thông qua nhánh này. u không thuộc về đường đi thành công. Xóa u khỏi cuối current_path: current_path.pop_back(). Đỉnh u vẫn giữ trạng thái visited = true để tránh thăm lại nó trong các nhánh khác nếu ta chỉ muốn tìm một path. Nếu muốn tìm tất cả paths, ta cần unmark visited[u] = false. Ở đây, chúng ta tìm một path, nên giữ visited[u] = true là ok, nhưng việc xóa u khỏi current_path là cần thiết để vector current_path chỉ chứa các đỉnh trên đường đi thực sự dẫn đến đích.
   • Trả về false vì không tìm thấy đường đi từ u đến đích qua nhánh này.
4. Hàm gọi ban đầu sẽ khởi tạo visited và current_path rỗng, sau đó gọi đệ quy từ đỉnh nguồn. Nếu kết quả trả về là true, current_path sẽ chứa đường đi.

Ví dụ C++ minh họa cho DFS tìm đường đi:

Sử dụng lại đồ thị trên:

0 -- 1 -- 3
| \  |
|  \ |
4 -- 2 -- 5

Tìm đường đi từ đỉnh 0 đến đỉnh 5.

#include <iostream>
#include <vector>
#include <algorithm> // Not needed for this DFS implementation, but good to include
#include <stack> // Could be used for iterative DFS, but we use recursion here

using namespace std;

// Hàm đệ quy tìm đường đi bằng DFS
// Trả về true nếu tìm thấy đường đi từ u đến target, false ngược lại
bool find_path_dfs_recursive(const vector<vector<int>>& adj, int u, int target,
                             vector<bool>& visited, vector<int>& current_path) {

    visited[u] = true; // Đánh dấu đỉnh hiện tại đã thăm
    current_path.push_back(u); // Thêm đỉnh hiện tại vào đường đi đang xét

    // Trường hợp cơ sở: Đã đến đỉnh đích
    if (u == target) {
        return true; // Tìm thấy đường đi
    }

    // Duyệt qua các đỉnh kề
    for (int v : adj[u]) {
        if (!visited[v]) {
            // Gọi đệ quy trên đỉnh kề chưa thăm
            if (find_path_dfs_recursive(adj, v, target, visited, current_path)) {
                return true; // Nếu tìm thấy đích từ v, trả về true ngay lập tức
            }
        }
    }

    // Nếu không tìm thấy đích từ bất kỳ đỉnh kề nào, đỉnh u không thuộc đường đi thành công
    current_path.pop_back(); // Quay lui: Xóa đỉnh hiện tại khỏi đường đi
    // Note: visited[u] vẫn giữ là true để tránh chu trình trong trường hợp tìm 1 path
    return false; // Không tìm thấy đường đi từ u qua nhánh này
}

// Hàm wrapper để gọi DFS và lấy kết quả
vector<int> find_path_dfs(const vector<vector<int>>& adj, int start_node, int end_node) {
    int num_vertices = adj.size();
    vector<bool> visited(num_vertices, false); // Đánh dấu đỉnh đã thăm
    vector<int> path; // Vector để lưu đường đi

    // Kiểm tra các đỉnh có hợp lệ không
    if (start_node < 0 || start_node >= num_vertices || end_node < 0 || end_node >= num_vertices) {
        return path; // Trả về vector rỗng nếu không hợp lệ
    }

    // Nếu đỉnh bắt đầu và kết thúc giống nhau
    if (start_node == end_node) {
        path.push_back(start_node);
        return path;
    }

    // Gọi hàm đệ quy chính
    // visited được truyền reference để duy trì trạng thái giữa các lần gọi
    // path được truyền reference để hàm đệ quy xây dựng đường đi trực tiếp vào đây
    if (find_path_dfs_recursive(adj, start_node, end_node, visited, path)) {
        return path; // Trả về đường đi nếu tìm thấy
    } else {
        return {}; // Trả về vector rỗng nếu không tìm thấy
    }
}

int main() {
    // Biểu diễn đồ thị bằng danh sách kề
    vector<vector<int>> adj(6); // 6 đỉnh: 0 đến 5
    adj[0].push_back(1);
    adj[0].push_back(2);
    adj[0].push_back(4);
    adj[1].push_back(0);
    adj[1].push_back(2);
    adj[1].push_back(3);
    adj[2].push_back(0);
    adj[2].push_back(1);
    adj[2].push_back(4);
    adj[2].push_back(5);
    adj[3].push_back(1);
    adj[4].push_back(0);
    adj[4].push_back(2);
    adj[5].push_back(2);

    int start = 0;
    int end = 5;

    cout << "Tim duong di tu " << start << " den " << end << " bang DFS:" << endl;
    vector<int> path = find_path_dfs(adj, start, end);

    if (!path.empty()) {
        cout << "Duong di tim thay: ";
        for (size_t i = 0; i < path.size(); ++i) {
            cout << path[i] << (i == path.size() - 1 ? "" : " -> ");
        }
        cout << endl;
    } else {
        cout << "Khong tim thay duong di." << endl;
    }

    // Ví dụ khác: tìm đường đi không tồn tại
    cout << "\nTim duong di tu 0 den 10 (khong ton tai) bang DFS:" << endl;
    int start_nonexistent = 0;
    int end_nonexistent = 10; // Đỉnh không tồn tại

     if (end_nonexistent >= 0 && end_nonexistent < adj.size()) {
        vector<int> path_nonexistent = find_path_dfs(adj, start_nonexistent, end_nonexistent);
         if (!path_nonexistent.empty()) {
             // Code này sẽ không chạy
         } else {
             cout << "Khong tim thay duong di." << endl;
         }
    } else {
         cout << "Dinh dich khong hop le." << endl;
    }


    return 0;
}

Giải thích Code DFS:

• adj vẫn là danh sách kề biểu diễn đồ thị.
• visited là std::vector<bool> được truyền bằng tham chiếu (vector<bool>& visited) vào hàm đệ quy. Nó giúp chúng ta theo dõi những đỉnh nào đã được thăm tổng thể trong toàn bộ quá trình tìm kiếm. Điều này là cần thiết để tránh bị kẹt trong chu trình.
• current_path là std::vector<int> cũng được truyền bằng tham chiếu (vector<int>& current_path). Vector này đóng vai trò như một ngăn xếp (stack) ngầm định, lưu trữ các đỉnh trên đường đi từ đỉnh nguồn đến đỉnh u hiện tại trong lần gọi đệ quy.
• Trong find_path_dfs_recursive(adj, u, target, visited, current_path):
  • Chúng ta đánh dấu u đã thăm và thêm u vào cuối current_path.
  • Nếu u bằng target, chúng ta đã tìm thấy đích. Hàm trả về true, và do cơ chế đệ quy, các lời gọi trước đó cũng sẽ trả về true, đồng thời current_path tại thời điểm này chính là đường đi từ nguồn đến đích.
  • Nếu u không phải là đích, chúng ta duyệt qua các đỉnh kề v.
  • Nếu v chưa thăm, chúng ta gọi đệ quy find_path_dfs_recursive(adj, v, target, visited, current_path).
  • Nếu bất kỳ lời gọi đệ quy nào trả về true (nghĩa là tìm thấy đích ở sâu hơn), chúng ta cũng trả về true ngay lập tức. Điều này đảm bảo rằng khi tìm thấy đích, chúng ta dừng việc khám phá các nhánh khác và giữ nguyên trạng thái current_path chứa đường đi thành công.
  • Nếu vòng lặp qua tất cả các đỉnh kề kết thúc mà không có lời gọi đệ quy nào trả về true (nghĩa là không tìm thấy đường đi từ u qua bất kỳ đỉnh kề chưa thăm nào), điều này có nghĩa là u không nằm trên đường đi dẫn đến đích. Chúng ta cần quay lui: xóa u khỏi cuối current_path bằng current_path.pop_back(). Đỉnh u vẫn được giữ là visited = true để tránh thăm lại nó (và tạo chu trình) khi khám phá các nhánh khác từ các đỉnh khác.
  • Nếu không tìm thấy đường đi, hàm cuối cùng trả về false.
• Hàm find_path_dfs là một hàm "bao bọc" (wrapper function) để khởi tạo visited và path, xử lý các trường hợp đặc biệt (nguồn = đích, đích không hợp lệ), sau đó gọi hàm đệ quy và trả về kết quả.

DFS tìm đường đi theo kiểu "thử và sai". Nó đi sâu vào một con đường, nếu con đường đó không dẫn đến đích, nó quay lui và thử con đường khác. Đường đi mà DFS tìm được không đảm bảo là ngắn nhất, nó chỉ là một trong những đường đi có thể có. Tuy nhiên, trên một số cấu trúc đồ thị hoặc khi bạn chỉ cần một đường đi bất kỳ và không quan tâm đến độ dài, DFS có thể là một lựa chọn tốt, đặc biệt là khi đồ thị rất sâu và hẹp (DFS có thể dùng ít bộ nhớ hơn BFS trong trường hợp này).

3. So sánh BFS và DFS trong bài toán tìm đường đi

Bài tập ví dụ:

[Graph].BFS trên đồ thị vô hướng.

Cho đồ thị vô 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 BFS(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 BFS(s). Chú ý trong quá trình mở rộng các đỉnh của thuật toán BFS 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 4
1 2
1 3
1 4
2 3
2 4
2 5
3 4
3 5
4 5

Dữ liệu ra

4 1 2 3 5

Đây là hướng dẫn giải bài toán BFS trên đồ thị vô hướng theo yêu cầu:

1. Biểu diễn đồ thị: Sử dụng danh sách kề (adjacency list). Dùng std::vector<std::vector<int>> adj trong C++, kích thước n+1 nếu đỉnh đánh số từ 1. Đọc m cạnh, với mỗi cạnh u v, thêm v vào danh sách kề của u và u vào danh sách kề của v.

2. Xử lý yêu cầu thứ tự duyệt: Sau khi xây dựng danh sách kề, duyệt qua từng danh sách adj[i] và sắp xếp nó theo thứ tự tăng dần. Điều này đảm bảo khi duyệt các đỉnh kề của một đỉnh u, ta luôn xem xét các đỉnh có chỉ số nhỏ hơn trước.

3. Thuật toán BFS:

   • Cần một hàng đợi (std::queue<int>) để lưu các đỉnh sẽ được thăm.
   • Cần một mảng/vector boolean (std::vector<bool> visited) kích thước n+1 để đánh dấu các đỉnh đã thăm, khởi tạo tất cả là false.
   • Đưa đỉnh bắt đầu s vào hàng đợi và đánh dấu visited[s] = true.
   • Trong khi hàng đợi chưa rỗng:
     • Lấy đỉnh u từ đầu hàng đợi và loại bỏ nó.
     • In đỉnh u.
     • Duyệt qua các đỉnh kề v của u trong danh sách adj[u (lúc này đã được sắp xếp).
     • Nếu v chưa được thăm (!visited[v]):
       • Đánh dấu visited[v] = true.
       • Đưa v vào cuối hàng đợi.

4. Output: In các đỉnh u khi lấy ra từ hàng đợi, cách nhau bằng dấu cách.

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