Tạo bài viết
Đăng ký
02/10/2018, 15:04

Bài 5: Thuật toán tìm kiếm theo chiều rộng BFS pascal c++

Bài viết này là phần 5 trong 7 bài của Series Lý thuyết đồ thị căn bản Lý thuyết đồ thị căn bản Bài 1: Ma trận kề C++/Pascal Lý thuyết đồ thị Bài 2: Danh sách cạnh C++ Lý thuyết đồ thị Bài 3: Danh sách kề C++ Lý thuyết đồ thị Bài 4: Thuật toán tìm kiếm theo chiều sâu DFS ...

Bài viết này là phần 5 trong 7 bài của Series Lý thuyết đồ thị căn bản

Lý thuyết đồ thị căn bản
  • Bài 1: Ma trận kề C++/Pascal Lý thuyết đồ thị
  • Bài 2: Danh sách cạnh C++ Lý thuyết đồ thị
  • Bài 3: Danh sách kề C++ Lý thuyết đồ thị
  • Bài 4: Thuật toán tìm kiếm theo chiều sâu DFS pascal c++
  • Bài 5: Thuật toán tìm kiếm theo chiều rộng BFS pascal c++
  • Bài 6: Thuật toán loang trên ma trận
  • Cấu trúc dữ liệu Disjoint Sets

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:

Bài 4: Thuật toán tìm kiếm theo chiều sâu DFS pascal c++

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 } }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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; }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
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:

InputOutput
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:

InputOutput
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.

Bùi Văn Nam

27 chủ đề

7090 bài viết

Có thể bạn quan tâm
0
Các chủ đề đang được quan tâm
phần mềm lập trình php | lập trình web php + mysql | khóa học lập trình php | tự học lập trình php | học php cơ bản thachpham | Code24h | Cho thuê phòng trọ hà nội | Cho thuê phòng trọ bình thạnh | Cho thuê phòng trọ | Cho thuê nhà trọ
Đăng ký

Đăng ký nhận thông báo

Các bài học thú vị sẽ được gửi đến inbox của bạn

HỖ TRỢ HỌC VIÊN
VỀ CODE24H
HỢP TÁC VÀ LIÊN KẾT
KẾT NỐI VỚI CHÚNG TÔI
TẢI ỨNG DỤNG TRÊN ĐIỆN THOẠI

CCode 24h, code mọi lúc, mọi nơi

© Copy right 2018 - 2024