CTDL và giải thuật - Bài tập 2
Bài tập.
Có n
thành phố được đánh số từ 1
đến n
. Cho ma trận a thể hiện tính liên thông giữa các thành phố, ví dụ a = [[1, 2], [3, 4]]
có nghĩa là:
- Thành phố
1
và2
có thể đi đến với nhau với quãng đường là1
. - Thành phố 3 và 4 cũng tương tự.
Cho hai số u
và v
phân biệt. Hãy đưa ra quãng đường ngắn nhất để đi từ thành phố u
đến thành phố v
. Trả về -1
nếu từ thành phố u không thể đi đến thành phố v
.
Ví dụ:
- Với
n = 6, e = [[1,3], [1,2], [2, 3], [3,4], [2,5], [4,6], [6,5], [4,5]], u = 1, v = 5
thìgraphFunction(n, e, u, v) = 2
.
Có nhiều cách di chuyển từ thành phố1
đến5
những cách nhanh nhất đó là1 -> 2 -> 5
với quãng đường là2
.
- Với
n = 2, e = [[1,2], [3,4]], u = 2, v = 3
thìgraphFunction(n, e, u, v) = -1.
Hướng dẫn bài tập.
Với bài này thì cách làm tốt nhất là tìm kiếm theo chiều rộng (Bfs).
Code mẫu:
Ngôn ngữ C++:
bool b[100001];
int c[100001];
bool a[1001][1001];
bool kt = false;
int bfs(int u, int v, int n){
int kq = n+1;
queue<int> q;
q.push(u);
b[u] = false;
while(!q.empty()){
int k = q.front();
for (int i = 1; i <=n; i++){
if (a[k][i] && b[i]){
c[i] = c[k] + 1;
b[i] = false;
q.push(i);
if (i == v) break;
}
}
q.pop();
}
return c[v];
}
int graphFunction(int n, std::vector<std::vector<int>> e, int u, int v)
{
for (int i = 0; i <= n; i++){
b[i] = true;
c[i] = 0;
}
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++){
a[i][j] = false;
}
}
for (int i = 0; i < e.size(); i++){
a[e[i][0]][e[i][1]] = true;
a[e[i][1]][e[i][0]] = true;
}
int k = bfs(u, v, n);
return (k == 0) ? -1 : k;
}