資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會科學
時尚科學
法律科學使用隨機邊選擇法構建隨機圖的 C++ 程式
在此程式中，為隨機頂點和邊生成一個隨機圖。此程式的時間複雜度為 O(v*e)。其中，v 是頂點數，e 是邊數。
演算法
Begin Develop a function GenRandomGraphs(), with ‘e’ as the number of edges and ‘v’ as the number of vertexes, in the argument list. Assign random values to the number of vertex and edges of the graph, Using rand() function. Print the connections of each vertex, irrespective of the direction. Print “Isolated vertex” for the vertex having no degree. End
示例
#include<iostream>
#include<stdlib.h>
using namespace std;
void GenRandomGraphs(int NOEdge, int NOVertex) {
int i, j, edge[NOEdge][2], count;
i = 0;
//Assign random values to the number of vertex and edges of the graph, Using rand().
while(i < NOEdge) {
edge[i][0] = rand()%NOVertex+1;
edge[i][1] = rand()%NOVertex+1;
//Print the connections of each vertex, irrespective of the direction.
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!";
//Print “Isolated vertex” for the vertex having no degree.
}
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);
}輸出
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 }
更新於： 30-Jul-2019
112 次瀏覽
廣告