Hiểu bài toán

Bài toán yêu cầu tìm đường đi ngắn nhất (tính theo số cạnh) từ một đỉnh nguồn s đến một đỉnh đích t trong một đồ thị vô hướng, không trọng số. Dữ liệu đầu vào (từ file BFS.INP) bao gồm: số đỉnh n, số cạnh m, đỉnh nguồn s và đỉnh đích t. Mảng m dòng tiếp theo mô tả các cạnh nối hai đỉnh. Nếu không có đường đi từ s đến t, output là -1.

Các cách tiếp cận

Cách BFS (Breadth-First Search) - Dùng mảng đánh dấu và truy vết đường đi

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

int n, m, start, en;
vector<int> adj[1001];
bool visited[1001];
int parent[1001];

void inp(ifstream &fin){
    fin >> n >> m >> start >> en;
    for(int i = 0; i < m; i++){
        int x, y;
        fin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    memset(visited, false, sizeof(visited));
    memset(parent, -1, sizeof(parent));
}

void bfs(int u){
    queue<int> q;
    q.push(u);
    visited[u] = true;
    while(!q.empty()){
        int v = q.front();
        q.pop();
        for(auto i : adj[v]){
            if(!visited[i]){
                q.push(i);
                parent[i] = v;
                visited[i] = true;
            }
        }
    }
}

int Path(int s, int l){
    bfs(s);
    if(!visited[l]){
        return -1;
    } 
    else{
        int count = 0;
        while (l != s) {
            l = parent[l];
            count++;
        }
        return count;
    }
}

• Time Complexity: O(N + M)
• Space Complexity: O(N + M)

Đây là cách tiếp cận tiêu chuẩn giải quyết bài toán tìm đường đi ngắn nhất trên đồ thị vô hướng, không trọng số.

1. Cấu trúc dữ liệu:

   • adj[1001]: Mảng các danh sách kề để lưu đồ thị.
   • visited[1001]: Mảng đánh dấu các đỉnh đã được thăm.
   • parent[1001]: Mảng lưu đỉnh cha của mỗi đỉnh (dùng để truy vết đường đi).

2. Quy trình BFS:

   • Bắt đầu từ đỉnh nguồn s, thêm s vào hàng đợi.
   • Lần lượt lấy các đỉnh ra khỏi hàng đợi, duyệt qua các đỉnh kề của nó.
   • Nếu đỉnh kề chưa được thăm, đánh dấu đã thăm, gán đỉnh hiện tại làm cha của nó, và thêm vào hàng đợi.

3. Tính toán khoảng cách:

   • Sau khi BFS chạy xong từ s, ta chỉ cần truy vết đường đi từ t về s bằng mảng parent và đếm số bước.
   • Nếu t không được đánh dấu là đã thăm sau BFS, tức là không có đường đi, trả về -1.

Cách BFS (Breadth-First Search) - Cập nhật khoảng cách trực tiếp

#include <bits/stdc++.h>
using namespace std;
const int N = 2e3;
vector<int> adj[N + 5];
int dist[N + 5];
void BFS(int s){
    for(int i=1;i<=N;++i) dist[i]=1e9;
    queue<int> q;
    q.push(s);
    dist[s]=0;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int v:adj[u]){
            if(dist[v]>dist[u]+1){
                dist[v]=dist[u]+1;
                q.push(v);
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    freopen("bfs.inp","r",stdin);
    freopen("bfs.out","w", stdout);
    int n,m,s,t;
    cin>>n>>m>>s>>t;
    while(m--){
        int u,v;
        cin>>u>>v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }
    BFS(s);
    cout << (dist[t]==1e9?-1:dist[t]);
    return 0;
}

• Time Complexity: O(N + M)
• Space Complexity: O(N + M)

Phương pháp này cũng sử dụng BFS nhưng thay vì dùng mảng visited và truy vết sau, ta dùng mảng dist để lưu khoảng cách ngay trong quá trình BFS.

1. Khởi tạo:

   • Gán tất cả khoảng cách dist[i] về một giá trị vô cùng lớn (ví dụ: 1e9).
   • Gán dist[s] = 0.

2. Quy trình BFS:

   • Khi duyệt từ đỉnh u sang đỉnh kề v, ta kiểm tra xem có thể cải tiến khoảng cách đến v không (thông qua u).
   • Điều kiện: dist[v] > dist[u] + 1. Nếu thỏa mãn, cập nhật dist[v] = dist[u] + 1 và đưa v vào hàng đợi.

3. Kết quả:

   • Sau khi BFS, khoảng cách từ s đến t chính là giá trị dist[t]. Nếu dist[t] vẫn bằng giá trị vô cùng, trả về -1.

Lưu ý: Trong đồ thị không trọng số, cách này về cơ bản hiệu quả như cách dùng mảng visited nhưng code ngắn gọn hơn.

Phân tích độ phức tạp

Bài học kinh nghiệm

• BFS là thuật toán tối ưu để tìm đường đi ngắn nhất trên đồ thị không trọng số.
• Việc lưu lại đường đi (truy vết) cần dùng thêm mảng phụ (thường là mảng parent), trong khi chỉ cần khoảng cách thì không cần.

Lỗi thường gặp

• Quên kiểm tra xem đỉnh đích đã được thăm hay chưa trước khi in kết quả (nếu dùng mảng visited).
• Lỗi truy cập ngoài biên mảng do khai báo kích thước vector adjacency quá nhỏ so với n.