BFS: duyệt theo chiều rộng và đường đi ít cạnh nhất

Từ một nguồn lan ra từng lớp

Giả sử bắt đầu ở đỉnh 0. Những đỉnh nối trực tiếp với 0 chỉ cần một cạnh, nên thuộc lớp 1. Các đỉnh chưa gặp nhưng nối với lớp 1 có thể tới bằng hai cạnh, thuộc lớp 2. BFS xử lý hết lớp gần hơn trước khi chuyển sang lớp xa hơn, giống việc lan một làn sóng trên đồ thị.

Ví dụ gồm các cạnh vô hướng 0–1, 0–2, 1–3, 2–3, 3–4 và một đỉnh 5 đứng riêng. Từ 0, lớp 1 có 1 và 2; lớp 2 có 3; lớp 3 có 4. Đỉnh 5 không thuộc lớp nào vì không có đường đi từ nguồn tới nó.

Vì sao cần hàng đợi FIFO?

Hàng đợi lấy phần tử được đưa vào sớm nhất. Khi đang xử lý một đỉnh ở khoảng cách k, các đỉnh mới được phát hiện có khoảng cách k+1 và được thêm ở cuối. Những đỉnh còn chờ ở khoảng cách k không bị vượt qua, nên thứ tự tăng lớp được bảo toàn.

Nếu thay queue bằng stack và giữ nguyên mọi dòng khác, bạn thường chuyển sang một kiểu đi sâu trước. Thuật toán đó có thể vẫn tìm được các đỉnh đi tới được, nhưng không còn lý do bảo đảm lần gặp đầu tiên dùng ít cạnh nhất. Xem so sánh BFS và DFS để thấy một phản ví dụ cụ thể.

Trong Python dùng deque với popleft, không dùng list.pop(0). Thao tác lấy đầu list phải dồn phần còn lại, có thể làm tổng chi phí vượt cận O(n+m) của bản BFS chuẩn trên danh sách kề.

Chạy tay ví dụ sáu đỉnh

Khởi tạo d[0] = 0, mọi vị trí khác bằng -1, hàng chờ chứa 0. Lấy 0 ra, thêm 1 và 2 với khoảng cách 1. Lấy 1 ra, gặp 3 chưa có khoảng cách nên đặt d[3] = 2 và thêm 3. Lấy 2 ra cũng nhìn thấy 3, nhưng không thêm lại vì 3 đã được đánh dấu.

Đánh dấu lúc thêm làm hai nhánh 1 và 2 không đưa trùng 3 vào hàng. Trên đồ thị có nhiều đường cùng dẫn tới một đỉnh, việc này giữ mỗi đỉnh chỉ vào hàng một lần. Bản dùng d = -1 làm cả thông tin khoảng cách lẫn dấu chưa gặp, nên không cần mảng visited riêng.

Code C++ và Python

#include <algorithm>
#include <functional>
#include <iostream>
#include <numeric>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;
const long long INF=1LL<<60;
vector<int> bfs(int n,const vector<pair<int,int>>&edges,int s){
    vector<vector<int>> adj(n);for(auto[u,v]:edges){adj[u].push_back(v);adj[v].push_back(u);}
    vector<int>d(n,-1);queue<int>q;d[s]=0;q.push(s);
    while(!q.empty()){int u=q.front();q.pop();for(int v:adj[u])if(d[v]<0){d[v]=d[u]+1;q.push(v);}}
    return d;
}

int main(){int n=6,m,s=0;vector<pair<int,int>>edges={{0,1},{0,2},{1,3},{2,3},{3,4}};
if(cin>>n>>m>>s){edges.resize(m);for(auto&[u,v]:edges)cin>>u>>v;}
for(auto x:bfs(n,edges,s)) { cout<<x<<' '; }
cout<<'\n';}

INF=1<<60
def solve(n,edges,s):
    from collections import deque
    adj=[[] for _ in range(n)]
    for u,v in edges:adj[u].append(v);adj[v].append(u)
    d=[-1]*n;d[s]=0;q=deque([s])
    while q:
        u=q.popleft()
        for v in adj[u]:
            if d[v]<0:d[v]=d[u]+1;q.append(v)
    return d

if __name__=='__main__':
    import sys
    d=list(map(int,sys.stdin.read().split()))
    if d:
        n,m=d[:2];off=3;s=0 if off==2 else d[2]
        width=2;edges=[tuple(d[i:i+width]) for i in range(off,off+width*m,width)]
    else:
        n,s,edges=6,0,[(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)]
    print(*solve(n,edges,s))

Chạy ví dụ mặc định nhận 0 1 1 2 3 -1. Với đầu vào khác, nhập n, m, s rồi m cặp đỉnh; s là nguồn, các chỉ số từ 0 tới n−1. Code tự thêm cả hai chiều cho mỗi cạnh, nên đây là phiên bản đồ thị vô hướng. Nếu đề có hướng, chỉ thêm chiều được cung cấp, không giữ nguyên dòng thêm ngược.

Nguồn phải nằm trong đồ thị và n phải dương. Số -1 báo không có đường đi; nó không phải khoảng cách âm. Với bài hỏi một đích t, có thể dừng khi khoảng cách t đã được xác định nếu không cần các đỉnh còn lại. Bản ví dụ duyệt hết phần liên thông với nguồn để cho đầy đủ mảng kết quả.

Lý do lần phát hiện đầu là tối ưu

Mỗi lần từ u thêm v, chương trình có một đường đi thật tới v dài d[u]+1 cạnh. Giả sử tồn tại đường ngắn hơn nhưng BFS lại phát hiện v quá muộn. Đỉnh đứng ngay trước v trên đường ngắn hơn đó có khoảng cách nhỏ hơn d[u], nên phải được xử lý trước theo thứ tự lớp. Khi ấy nó đã thêm v sớm hơn, mâu thuẫn với giả sử.

Chứng minh dựa vào việc mọi lần đi qua cạnh làm số bước tăng đúng một. Nếu một cạnh giá 100 và một cạnh giá 1, ít cạnh hơn không có nghĩa chi phí nhỏ hơn. Khi trọng số chỉ là 0 và 1 có thuật toán 0–1 BFS riêng; với trọng số không âm tổng quát, xem Dijkstra.

Truy vết đường đi và BFS nhiều nguồn

Muốn in một đường đi, tại thời điểm phát hiện v lưu parent[v] = u. Sau khi BFS kết thúc, nếu đích đi tới được, lần ngược parent từ đích về nguồn rồi đảo danh sách. Nếu có nhiều đường ngắn nhất, thứ tự danh sách kề có thể quyết định đường nào được chọn, nhưng không đổi khoảng cách.

BFS nhiều nguồn khởi tạo tất cả nguồn có khoảng cách 0 và đưa vào hàng ngay từ đầu. Khi đó khoảng cách mỗi đỉnh là số cạnh ít nhất tới một nguồn phù hợp trong đồ thị vô hướng. Bài ma trận khoảng cách tới số 0 miễn phí bên dưới dùng ý tưởng này; không cần chạy BFS riêng từ từng ô.

Thời gian, bộ nhớ và ca kiểm

Với n đỉnh, m cạnh và danh sách kề, mỗi đỉnh vào hàng tối đa một lần, mỗi mục kề được xét một lần, tổng O(n+m) thời gian. Bộ nhớ gồm danh sách kề O(n+m), khoảng cách O(n) và hàng chờ O(n). Nếu lưu bằng ma trận và quét cả hàng ở mỗi đỉnh, cận duyệt thường thành O(n²), không còn O(n+m) trên đồ thị thưa.

Để tự kiểm tra trên đồ thị nhỏ, bạn có thể thử đỉnh nguồn cô lập, đồ thị không có cạnh và đồ thị ngẫu nhiên ít đỉnh rồi so sánh với kết quả quy hoạch động theo số cạnh. Khi tự thử, thêm đường vòng để kiểm đỉnh không được đưa lại mãi, và hai đường bằng nhau tới cùng đích để kiểm khoảng cách vẫn ổn định.

Luyện ngay trên Big-O Coding

Bắt đầu với đường ngắn nhất không trọng số, rồi chuyển sang mê cung lưới. Bài ma trận miễn phí là biến thể nhiều nguồn, cần đưa mọi ô 0 vào hàng trước khi lan.

Câu hỏi thường gặp

Nguồn tham khảo

• cp-algorithms: Breadth First Search
• Open Data Structures: Graph Traversal
• Python: collections.deque