TTBFS - Minh họa thuật toán BFS

Xem dạng PDF
Gửi bài giải
Điểm: 1,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Tác giả:
Hieu Nguyen
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift

Tìm kiếm ưu tiên chiều rộng hay tìm kiếm theo chiều rộng (tiếng Anh: Breadth-first search - BFS) là một thuật toán duyệt hoặc tìm kiếm trên một cây hoặc một đồ thị.

Thuật toán khởi đầu tại gốc (hoặc chọn một đỉnh nào đó coi như gốc) và phát triển theo nguyên tắc "gần trước xa sau".

Ví dụ:

BFSDEMO.jpg

Bài toán đặt ra là:

Cho đơn đồ thị vô hướng liên thông ~G = (V, E)~ gồm ~n~ đỉnh và ~m~ cạnh, các đỉnh được đánh số từ ~1~ tới ~n~ và các cạnh được đánh số từ ~1~ tới ~m~.

Bằng thuật toán tìm kiếm theo chiều rộng, hãy đưa ra danh sách các đỉnh theo thứ tự tìm kiếm (thăm). Biết rằng: Đỉnh nào có chỉ số bé hơn sẽ được ưu tiên thăm trước.

Input

  • Dòng đầu ghi hai số nguyên ~n, m~;
  • ~m~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~i, j~ mô tả một cạnh (nối giữa đỉnh ~i~ và đỉnh ~j~).

Giới hạn:

  • ~1 ≤ n ≤ 100; 1 ≤ m ≤ \frac{n(n-1)}{2}~.

Output

  • Gồm ~n~ dòng, mỗi dòng gồm một số ghi số hiệu đỉnh theo thứ tự duyệt BFS

Sample

Input #1
7 7
1 2
1 3
1 5
2 4
2 6
3 7
5 6
Output #1
1
2
3
5
4
6
7

Problem source: Chuyên Sơn La Online Judge

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • 2
    dungolduck  đã bình luận lúc 16, Tháng 2, 2024, 6:49

    mấy bạn để ý nhá nó có thể chia thành nhiều liên thông nên bạn cần vòng for để duyệt xem đỉnh nào chưa đc duyệt thì sẽ cho chạy: #include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; const int MOD = 1000007; const int MAXN = 2001;

    vector<int> a[1001]; vector<int> res; int check[1001];

    void bfs(int k) { queue<int> que; que.push(k); res.pushback(k); check[k] = 1; while (!que.empty()) { int l = que.front(); que.pop(); for (int x : a[l]) { if (!check[x]) { que.push(x); check[x] = 1; res.pushback(x); } } } } int main() { // freopen("BAI.INP", "r", stdin); // freopen("BAI.OUT", "w", stdout); ios::syncwithstdio(0); cin.tie(0); cout.tie(0);

    int n, m;
cin >> n >> m;
for (int i = 1; i <= m; i++) {
    int x, y;
    cin >> x >> y;
    a[x].push_back(y);
    a[y].push_back(x);
}
for (int i = 1; i <= n; i++)
    if (!check[i])
        bfs(i);
for (int x : res) {
    cout << x << '\n';
}
return 0;

    }


  • 0
    dientm022  đã bình luận lúc 22, Tháng 11, 2023, 3:01

    +1


  • 0
    vuonghao  đã bình luận lúc 29, Tháng 8, 2023, 8:16

    mọi người AC bài này chỉ giúp mình sao lại RLE từ test 1. Trong khi mình test theo đề bài thì ok