数据结构
网络
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 次浏览
广告