Trong chương trình này, chúng ta tạo một đồ thị có hướng không chu trình (Directed Acyclic Graph - DAG) ngẫu nhiên cho số cạnh 'e' cho trước. Độ phức tạp thời gian của chương trình là O(e*v*e).
Thuật toán
Bắt đầu
hàm GenerateRandomGraphs(), có 'e' là số cạnh trong danh sách tham số.
Tạo kết nối giữa hai số ngẫu nhiên, cho trường hợp mẫu nhỏ, giới hạn số đỉnh là 20.
Kiểm tra chu trình trong đồ thị dùng CheckAcyclic(),
nếu trả về false thì loại bỏ cạnh này.
ngược lại giữ cạnh trong đồ thị.
In tất cả các kết nối có hướng của mỗi đỉnh.
Nếu bậc vào + bậc ra của mỗi đỉnh bằng 0 thì in đỉnh đó là "đỉnh cô lập".
Kết thúc
Mã ví dụ
#include <iostream>
#include <stdlib.h>
#define N 10
using namespace std;
bool Checkcyclic(int ed[][2], int edge, bool check[], int v) {
int i;
if(check[v] == true) {
return false;
} else {
check[v] = true;
for(i = edge; i >= 0; i--) {
if(ed[i][0] == v) {
return Checkcyclic(ed, edge, check, ed[i][1]);
}
}
}
check[v] = false;
if(i == 0)
return true;
}
void GenerateRandomGraphs(int e) {
int i, j, ed[e][2], count;
bool c[11];
i = 0;
while(i < e) {
ed[i][0] = rand() % N + 1;
ed[i][1] = rand() % N + 1;
for(j = 1; j <= 10; j++)
c[j] = false;
if(Checkcyclic(ed, i, c, ed[i][0]) == true)
i++;
}
cout << "\nĐồ thị ngẫu nhiên DAG được tạo: ";
for(i = 0; i < N; i++) {
count = 0;
cout << "\n\t" << i+1 << "-> { ";
for(j = 0; j < e; j++) {
if(ed[j][0] == i+1) {
cout << ed[j][1] << " ";
count++;
} else if(ed[j][1] == i+1) {
count++;
} else if(j == e-1 && count == 0)
cout << "Đỉnh cô lập!";
}
cout << " }";
}
}
int main() {
int e;
cout << "Nhập số cạnh cho đồ thị ngẫu nhiên: ";
cin >> e;
GenerateRandomGraphs(e);
}
Kết quả đầu ra
Nhập số cạnh cho đồ thị ngẫu nhiên: 4
Đồ thị ngẫu nhiên DAG được tạo:
1-> { }
2-> { 8 }
3-> { 5 }
4-> { Đỉnh cô lập! }
5-> { 1 }
6-> { Đỉnh cô lập! }
7-> { Đỉnh cô lập! }
8-> { }
9-> { Đỉnh cô lập! }
10-> { 5 }