C ++程序为给定数量的边生成随机有向无环图DAC
在此程序中，我们为给定的边“e”生成一个随机的有向无环图。该程序的时间复杂度为O（e*v*e）。
算法
Begin
function GenerateRandomGraphs(), has ‘e’ as the number edges in the argument list.
generate a connection between two random numbers, for sample a small case, limit the number of vertex to 20.
Check for the cycle in the graph Using CheckAcyclic(),
if it returns false discard this edge.
Else maintain the edge in the graph.
Print all the directed connection of each vertex.
If the in+out degree of each vertex is zero then print the vertex as “isolated vertex”.
End范例程式码
#include<iostream>
#include<stdlib.h>
#define N 10
using namespace std;
bool Checkcyclic(int ed[][2], int edge, bool check[], int v)//to check for the cycle, on addition of a new edge in the random graph.{
int i;
//如果当前顶点已被访问，则图形包含循环。
if(check[v] == true) {
return false;
} else {
check[v] = true;
//对于每个顶点，请查找与其连接的所有顶点。
for(i = edge; i >= 0; i--) {
if(ed[i][0] == v) {
return Checkcyclic(ed, edge, check, ed[i][1]);
}
}
}
//如果路径结束，则将在该路径中访问的顶点重新分配为false。
check[v] = false;
if(i == 0)
return true;
}
void GenerateRandomGraphs(int e) {
int i, j, ed[e][2], count;
bool c[11];
i = 0;
while(i < e) {
ed[i][0] = rand()%N+1;
ed[i][1] = rand()%N+1;
for(j = 1; j <= 10; j++)
c[j] = false;
if(Checkcyclic(ed, i, c, ed[i][0]) == true)
i++;
}
cout<<"\nThe generated random random graph is: ";
for(i = 0; i < N; i++) {
count = 0;
cout<<"\n\t"<<i+1<<"-> { ";
for(j = 0; j < e; j++) {
if(ed[j][0] == i+1) {
cout<<ed[j][1]<<" ";
count++;
} else if(ed[j][1] == i+1) {
count++;
} else if(j == e-1 && count == 0)
cout<<"孤立的顶点！";
}
cout<<" }";
}
}
int main() {
int e;
cout<<"Enter the number of edges for the random graphs: ";
cin>>e;
GenerateRandomGraphs(e);
}
}输出结果
Enter the number of edges for the random graphs: 4
The generated random random graph is:
1-> { }
2-> { 8 }
3-> { 5 }
4-> { 孤立的顶点！ }
5-> { 1 }
6-> { 孤立的顶点！ }
7-> { 孤立的顶点！ }
8-> { }
9-> { 孤立的顶点！ }
10-> { 5 }热门推荐
10 朋友新年祝福语大全 简短
11 新年祝福语简短大方兔年
12 搬新家礼物祝福语简短
13 同学见面花束祝福语简短
14 五一假期祝福语幽默简短
15 离职欢送敬酒祝福语简短
16 对学弟的祝福语简短
17 考老师辞职祝福语简短
18 祝福语驱散霉运的话简短