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 }