Đây là chương trình C++ tạo đồ thị vô hướng ngẫu nhiên cho số cạnh 'e' cho trước. Thuật toán này thực hiện trên mạng lớn và độ phức tạp thời gian là O(log n).
Thuật toán
Bắt đầu
Hàm GenerateRandomGraphs(), có 'e' là số cạnh trong danh sách tham số.
Khởi tạo i = 0
while(i < e)
edge[i][0] = rand()%N+1
edge[i][1] = rand()%N+1
Tăng i;
For i = 0 đến N-1
Khởi tạo count = 0
For j = 0 đến e-1
if(edge[j][0] == i+1)
In edge[j][1]
Tăng count
else if(edge[j][1] == i+1)
In edge[j][0]
Tăng count
else if(j == e-1 && count == 0)
In Isolated Vertex
Kết thúc
Ví dụ
#include<iostream>
#include<stdlib.h>
#define N 10
using namespace std;
void GenerateRandomGraphs(int e) {
int i, j, edge[e][2], count;
i = 0;
// tạo kết nối giữa hai số ngẫu nhiên, cho mẫu nhỏ, giới hạn đỉnh là 10.
while(i < e) {
edge[i][0] = rand()%N+1;
edge[i][1] = rand()%N+1;
i++;
}
// In tất cả kết nối của mỗi đỉnh, bất kể hướng.
cout << "\nThe generated random graph is: ";
for(i = 0; i < N; i++) {
count = 0;
cout << "\n\t" << i+1 << "-> { ";
for(j = 0; j < e; j++) {
if(edge[j][0] == i+1) {
cout << edge[j][1] << " ";
count++;
}
else if(edge[j][1] == i+1) {
cout << edge[j][0] << " ";
count++;
}
// In "Isolated vertex" cho đỉnh bậc 0.
else if(j == e-1 && count == 0)
cout << "Isolated Vertex!";
}
cout << " }";
}
}
int main() {
int n, i, e;
cout << "Enter the number of edges for the random graphs: ";
cin >> e;
GenerateRandomGraphs(e);
return 0;
}
Kết quả
Enter the number of edges for the random graphs: 10
The generated random graph is:
1-> { 10 7 }
2-> { 10 }
3-> { 7 8 7 }
4-> { 7 6 7 }
5-> { Isolated Vertex! }
6-> { 8 4 }
7-> { 4 3 4 1 3 }
8-> { 6 3 }
9-> { Isolated Vertex! }
10-> { 2 1 }