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