Breadth-First Search
Published:
BFS (Breadth-first search) là thuật toán tìm kiếm trên đồ thị với tư tưởng:
- Ưu tiên “chiều rộng” hơn “chiều sâu”
- Tìm kiếm xung quanh trước khi đi xuống sâu hơn
Xuất phát từ một nút, ta bắt đầu duyệt tất cả các nhánh ở lớp liền kề nó, rồi từ các nhánh đó duyệt tiếp lớp liền kề tiếp theo, cứ như vậy cho tới hết vùng liên thông.
Nguyên lý hoạt động
- Bắt đầu từ một đỉnh xuất phát
- Đánh dấu đỉnh hiện tại là đã thăm
- Thêm tất cả các đỉnh kề chưa được thăm vào hàng đợi
- Lấy đỉnh đầu tiên từ hàng đợi và lặp lại quá trình
Cài đặt
void bfs(int start) {
queue<int> q;
q.push(start);
visited[start] = true;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : adj[u]) {
if (!visited[v]) {
visited[v] = true;
q.push(v);
}
}
}
}
Ứng dụng
- Tìm đường đi ngắn nhất trong đồ thị không có trọng số
- Kiểm tra tính liên thông của đồ thị
- Tìm thành phần liên thông
- Kiểm tra đồ thị hai phía
- Giải các bài toán mê cung
Độ phức tạp
- Thời gian: O(V + E) với V là số đỉnh và E là số cạnh
- Không gian: O(V) cho việc lưu trữ mảng visited và queue
Ví dụ
/************************************************\
* *
* you know that i can't stop thinkin bout you *
* you're the source of everything i do *
* *
\************************************************/
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
int n, m;
vector > adj;
bool unused[110];
void init(){
int u, v;
cin >>n >> m;
adj.resize(n+1);
while (m--){
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
}
void BFS(int u){
memset(unused, true, sizeof unused);
queue Q;
Q.push(u);
unused[u] = false;
while(!Q.empty()){
u = Q.front();
cout << u << " ";
Q.pop();
for(int i = 0; i
int v = adj[u][i];
if(unused[v]){
Q.push(v);
unused[v] = false;
}
}
}
}
int main(){
init();
BFS(1);
}