Đề bài
Cho đồ thị vô hướng G=<V,E> được biểu diễn dưới dạng danh sách cạnh. Hãy viết chương trình thực hiện duyệt cây theo BFS.
Input
- Dòng đầu tiên chứa 2 số n, m là số đỉnh và số cạnh của đồ thị (1 <= n <= 1000, 1 <= m <= n*(n-1)/2).
- M dòng tiếp theo, mỗi dòng là 2 số u, v biểu diễn cạnh u, v của đồ thị (1 <= u, v <= n). Các cạnh được liệt kê theo thứ tự tăng dần của các đỉnh đầu.
Output
- In ra duyệt cây BFS tương ứng
Input |
Output |
10 11
1 2
1 3
1 5
1 10
2 4
3 6
3 7
3 9
6 7
5 8
8 9
|
1 2 3 5 10 4 6 7 9 8
|
Giải
#include<bits/stdc++.h>
#include<iostream>
using namespace std;
int n, m;
vector<int> adj[1001];
bool visited[1001];
void inp() {
cin >> n >> m;
for(int i = 0; i < m; i++) {
int x, y;
cin >> x >> y;
adj[x].push_back(y);
// Do thi co huong thi comment dong code sau
adj[y].push_back(x);
}
memset(visited, false, sizeof(visited));
}
void bfs(int u) {
// Khoi tao
queue<int> q;
q.push(u);
visited[u] = true;
// Lap
while(!q.empty()) {
int v = q.front(); // Lay phan tu o dau hang doi
q.pop(); // xoa bo phan tu o dau ra khoi hang doi
cout << v << " ";
for(int x: adj[v]) {
if(!visited[x]) {
q.push(x);
visited[x] = true;
}
}
}
}
int main() {
// Chuyen NHAP, XUAT thanh file
freopen("lab_3_1_input.INP", "r", stdin);
freopen("lab_3_1_output.OUT", "w", stdout);
// INPUT
inp();
// OUTPUT: duyet DFS
bfs(1);
}
|