Trong chương trình này, một đồ thị ngẫu nhiên được tạo cho các đỉnh và cạnh ngẫu nhiên. Độ phức tạp thời gian là O(v*e), với v là số đỉnh và e là số cạnh.
Thuật toán
Begin Phát triển hàm GenRandomGraphs(), với 'e' là số cạnh và 'v' là số đỉnh, trong danh sách tham số. Gán giá trị ngẫu nhiên cho số đỉnh và cạnh của đồ thị, dùng hàm rand(). In kết nối của mỗi đỉnh, không phụ thuộc hướng. In "Isolated vertex" cho đỉnh không có bậc. End
Ví dụ
#include<iostream> #include<stdlib.h> using namespace std; void GenRandomGraphs(int NOEdge, int NOVertex) { int i, j, edge[NOEdge][2], count; i = 0; //Gán giá trị ngẫu nhiên cho số đỉnh và cạnh, dùng rand(). while(i < NOEdge) { edge[i][0] = rand()%NOVertex+1; edge[i][1] = rand()%NOVertex+1; //In kết nối của mỗi đỉnh, không phụ thuộc hướng. if(edge[i][0] == edge[i][1]) continue; else { for(j = 0; j < i; j++) { if((edge[i][0] == edge[j][0] && edge[i][1] == edge[j][1]) || (edge[i][0] == edge[j][1] && edge[i][1] == edge[j][0]))i--; } } i++; } cout<<"\nThe generated random graph is: "; for(i = 0; i < NOVertex; i++) { count = 0; cout<<"\n\t"<<i+1<<"-> { "; for(j = 0; j < NOEdge; j++) { if(edge[j][0] == i+1) { cout<<edge[j][1]<<" "; count++; } else if(edge[j][1] == i+1) { cout<<edge[j][0]<<" "; count++; } else if(j== NOEdge-1&& count == 0)cout<<"Isolated Vertex!"; //In "Isolated vertex" cho đỉnh không có bậc. } cout<<" }"; } } int main() { int i, e, n; cout<<"Random graph generation: "; n= 7 + rand()%6; cout<<"\nThe graph has "<<n<<" vertices"; e = rand()%((n*(n-1))/2); cout<<"\nand has "<<e<<" edges."; GenRandomGraphs(e, n); }Kết quả
Random graph generation: The graph has 8 vertices and has 18 edges. The generated random graph is: 1-> { 5 4 2 } 2-> { 4 8 6 3 1 5 } 3-> { 5 4 7 2 } 4-> { 2 3 7 1 8 5 } 5-> { 3 1 7 4 2 8 } 6-> { 2 8 7 } 7-> { 4 3 5 6 } 8-> { 2 6 4 5 }