ĐỀ CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CÓ ĐÁP ÁN CÀI ĐẶT BẰNG NGÔN NGỮ C - ĐỀ SỐ 18
Cho đồ thị vô hướng liên thông gồm N đỉnh G = <V,E>. Sử dụng thuật toán BFS, hãy viết chương trình xây dựng một cây khung của đồ thị bắt đầu tại đỉnh u. Dữ liệu vào cho bởi file dothi.in là biểu diễn của đồ thị dưới dạng ma trận kề theo khuôn dạng sau:
-
Dòng đầu tiên ghi số tự nhiên N, u tương ứng với số đỉnh và đỉnh bắt đầu xây dựng cây khung. Hai số được viết cách nhau bởi một vài khoảng trống.
-
N dòng kế tiếp ghi lại ma trận kề của đồ thị, hai phần tử khác nhau của ma trận kề được viết cách nhau một vài khoảng trống.
Cây khung xây dựng từ đỉnh u tìm được ghi lại trong file cay.out theo khuôn dạng sau:
-
Dòng đầu tiên ghi lại số N, K tương ứng với số đỉnh và số cạnh của cây khung. Hai số được viết cách nhau một vài ký tự trống;
-
K dòng kế tiếp ghi lại một cạnh của cây khung, đỉnh đầu và đỉnh cuối của mỗi cạnh được ghi cách nhau bởi một vài ký tự trống.
Ví dụ với đồ thị G=<V,E> được tổ chức trong file dothi.in dưới đây sẽ cho ta file cay.out tương ứng:
|
dothi.in |
cay.out |
|
5 1 0 1 1 1 1 1 0 1 0 1 1 1 0 1 0 1 0 1 0 1 1 1 0 1 0 |
5 4 1 2 1 3 1 4 1 5 |
#include<iostream.h>
#include<fstream.h>
#include<math.h>
#include<conio.h>
#include<time.h>
#include<string.h>
#include<stdio.h>
ifstream datain("C:/cau truc du lieu/dethi/dothi18.in.txt");
ofstream dataout("C:/cau truc du lieu/dethi/cay18.out.txt");
int n, m, k, ax[100], bx[100], dem = 0, x[100], a[100][100];
/*
Tao cay khung theo thuat toan BFS
Duyet theo chieu rong
*/
void NhapDL(int & n, int & m) {
datain >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
datain >> a[i][j];
}
void BFS(int i, int bd[][100], int n) {
int q[200], dq, cq;
x[i] = 1;
dq = 1;
cq = 1;
q[cq] = i;
while (dq <= cq) {
int u = q[dq], j;
dq++;
for (j = 1; j <= n; j++)
if (x[j] == 0 && bd[u][j] == 1) {
dem++;
ax[dem] = u;
bx[dem] = j;
x[j] = 1;
cq++;
}
}
}
main() {
dem = 0;
NhapDL(n, m);
dem = 0;
BFS(m, a, n);
dataout << n << "\t" << dem << endl;
for (int i = 1; i <= dem; i++)
dataout << ax[i] << " " << bx[i] << endl;
}
