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 送给学长毕业祝福语简短