Đề bài
Cho đồ thị có 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 tìm đường đi bằng cách sử dụng giải thuật 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
- Biết rằng tồn tại ít nhất một đường đi từ tới , hãy chỉ ra đường đi đơn qua ít cung nhất. Nếu có nhiều đường đi đơn cùng qua ít cung nhất, hãy chỉ ra đường đi có thứ tự từ điển nhỏ nhất trong sốđó.
Input |
Output |
8 12 1 8
1 2
1 3
2 3
2 4
3 1
3 5
3 7
4 6
6 2
6 8
7 8
7 6
|
BFS: 1 2 3 4 5 7 6 8
Path: 1 3 7 8
|
Giải
#include<bits/stdc++.h>
#include<iostream>
using namespace std;
int n, m; // n: so dinh, m: so canh
int s, t; // s: dinh bat dau, t: dinh ket thuc
vector<int> adj[1001];
bool visited[1001];
int parent[1001];
void inp() {
cin >> n >> m >> s >> t;
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);
}
// Sap xep cac gia tri trong vector tang dan A-Z
for(int i = 1; i <= n; i++) {
sort(adj[i].begin(), adj[i].end());
}
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;
parent[x] = v; // Ghi nhan cha cua x la v
}
}
}
}
void path(int s, int t) {
memset(visited, false, sizeof(visited));
memset(parent, 0, sizeof(parent));
cout << "BFS: ";
bfs(s);
cout << endl;
cout << "Path: ";
if(!visited[t]) {
cout << "Khong co duong di tu " << s << " den " << t;
}
else {
// Truy vet duong di
vector<int> path;
// Bat dau di nguoc tu dinh t
while(t != s) {
path.push_back(t);
t = parent[t]; // Lan nguoc lai
}
path.push_back(s);
reverse(path.begin(), path.end());
// In duong di
for(int x: path) {
cout << x << " ";
}
}
}
int main() {
// Chuyen NHAP, XUAT thanh file
freopen("lab_3_2_input.INP", "r", stdin);
freopen("lab_3_2_output.OUT", "w", stdout);
// INPUT
inp();
// Duong di tu dinh s -> dinh t
path(s, t);
}
|