Thuật toán tìm kiếm theo chiều rộng BFS là thuật toán tìm kiếm trong đồ thị bằng cách tìm kiếm dựa trên 2 thao tác chính là: cho trước một đỉnh của đồ thị và thêm các đỉnh kề với nó vào danh sách chờ duyệt. Phương pháp cài đặt này là “lập lịch” để duyệt các đỉnh theo thứ tự duyệt ưu tiên trên chiều rộng (đỉnh nào gần với đỉnh gốc sẽ được duyệt trước)
Hình ảnh minh họa BFS, nguồn wikipedia
Vì nguyên tắc trên (đỉnh nào gần gốc sẽ được duyệt trước) nên thuật toán tìm kiếm theo chiều rộng BFS thường được dùng để tìm đường đi ngắn nhất giữa các đỉnh.
Chúng ta sẽ xây dựng một danh sách chứa các đỉnh đang chờ duyệt, tại mỗi bước chúng ta thăm đỉnh ở đầu danh sách và thêm những đỉnh kề với nó chưa có trong danh sách chờ vào cuối danh sách.
Vì nguyên tắc đó nên chúng ta có thể tổ chức danh sách chờ đó bằng cấu trúc dữ liệu hàng đợi (Queue).
Bạn có thể tham khảo thêm:
Quy ước như sau:
- Push(x) là đẩy đỉnh x vào queue chờ
- Pop() lấy một đỉnh từ hàng đợi
- Empty() xác định queue còn đỉnh nào hay không?
– Chúng ta xây dựng bool Free[u] với ý nghĩa đỉnh u trong đồ thị chưa được duyệt đúng không?
– N là số đỉnh của đồ thị
1. Mô hình giải thuật BFS
Giải thuật BFS có thể viết theo mô hình dưới đây:
Free[u]=true; //với mọi u=1...n
Queue ban đầu rỗng.
Push(s); // Đẩy đỉnh đầu tiên vào queue
Free[s]=false; // đánh dấu đỉnh s
while (not empty())
{
u = pop(); // lấy từ queue đỉnh u
for (v=1; v<=n; v++)
if ((tồn tại cạnh u,v) và Free[v]==true)
{
Free[v]=false; // đánh dấu đỉnh v
Push(v); // đẩy đỉnh v vào queue
}
}Ví dụ: Viết chương trình ghi ra thứ tự duyệt BFS xuất phát từ đỉnh s. Đồ thi gồm n đỉnh, m cạnh 2 chiều, các thành phần trên đồ thị liên thông với nhau.
Dữ liệu vào:
- Dòng đầu: gồm 3 số nguyên n, m, s (1<=n, m<=100, 1<=s<=n)
- M dòng tiếp theo: mỗi dòng gồm 2 số u, v, mô tả 1 cạnh trong đồ thị
Dữ liệu ra:
- Gồm nhiều dòng, là thứ tự duyệt BFS
2. Code thuật toán tìm kiếm theo chiều rộng BFS
Tham khảo thêm về ma trận kề: https://kienthuc24h.com/ma-tran-ke-cpascal-ly-thuyet-thi/
a. Code thuật toán BFS C++
#include <bits/stdc++.h>
using namespace std;
int a[101][101];
queue <int> q;
int n,m,Free[101], u,v,s;
void BFS(int s)
{
q.push(s);
Free[s]=0;
while (!q.empty())
{
int u = q.front();
q.pop();
cout << u << endl;
for (int v=1; v<=n; v++)
if (Free[v] && a[u][v]==1)
{
Free[v] = 0;
q.push(v);
}
}
}
int main()
{
cin >> n >> m>> s;
for (int i=1; i<=n; i++)
for (int j=1; j<=n; j++)
a[i][j]=0;
for (int i=1; i<=m; i++)
{
cin >> u>> v;
a[u][v]=1;
a[v][u]=1;
}
for (int i=1; i<=n; i++)
Free[i]=1;
BFS(s);
return 0;
}
b. Code thuật toán tìm kiếm theo chiều rộng bfs trong pascal
Const maxn = 101;
Var a : array [1..maxn,1..maxn] of boolean;
free : array [1..maxn] of boolean;
Q : array [1..maxn] of integer;
n, m, s: integer;
dau, cuoi : integer;
Procedure init;
Begin
fillchar(a,sizeof(a),false);
fillchar(Free,sizeof(Free),true);
dau:=1; cuoi:=0;
end;
Procedure readf;
Var i, u, v : integer;
Begin
readln(n,m,s);
for i := 1 to m do
begin
readln(u,v);
A[u,v] := true;
A[v,u] := true;
end;
end;
Procedure Push(u:integer);
begin
inc(cuoi);
Q[cuoi] := u;
end;
Function Pop : integer;
Begin
Pop := Q[dau];
inc(dau);
end;
Procedure BFS(i : integer);
Var u, v : integer;
Begin
Push(i);
Free[i] := false;
While dau<=cuoi do
begin
u := Pop;
writeln(u);
For v := 1 to n do
If A[u,v] and Free[v] then
begin
Push(v);
Free[v] := false;
end;
end;
end;
Procedure main;
Var i : integer;
Begin
init;
readf;
BFS(s);
end;
BEGIN
main;
END.c. Test ví dụ
Các bạn có thể thử các bộ test sau:
Test 1:
| Input | Output |
| 7 7 1 1 2 1 3 1 5 2 4 2 6 3 7 5 6 | 1 2 3 5 4 6 7 |
Test 2:
| Input | Output |
| 7 7 4 1 2 1 3 1 5 2 4 2 6 3 7 5 6 | 4 2 1 6 3 5 7 |
3. Độ phức tạp thuật toán BFS
Độ phức tạp thời gian: O(|V|+|E|) với |V| là số đỉnh của đồ thị, |E| là số cạnh
Độ phức tạp dữ liệu: O(|V|)
4. Bài tập ứng dụng thuật toán BFS
Bạn có thể áp dụng ngay để làm các bài tập sau về BFS:
https://kienthuc24h.com/wecode-2015-problem-h-tim-duong-di-ngan-nhat/
https://kienthuc24h.com/upcoder-bfs-r2-b3-hereditament-hereditament/
Bài này yêu cầu bạn phải có kiến thức về thành phần liên thông:
https://kienthuc24h.com/bclkcoun-spoj-ptit-dem-so-ao/
https://kienthuc24h.com/bcdaisy-spoj-ptit-chu-bo-hu-hong/
https://kienthuc24h.com/bfs-spoj-ppath/
Và nhiều bài khác liên quan đến BFS bạn có thể tìm trên blog của mình.
Có thắc mắc gì các bạn vui lòng comment dưới đây, mình sẽ giải đáp.
