โปรแกรม C++ เพื่อสร้าง DAC กราฟ Acyclic แบบสุ่มสำหรับจำนวนขอบที่กำหนด

ในโปรแกรมนี้ เราสร้างกราฟ acyclic กำกับแบบสุ่มสำหรับขอบ '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 the current vertex is visited already, then the graph contains cycle.
   if(check[v] == true) {
      return false;
   } else {
      check[v] = true;
      // For each vertex, go for all the vertex connected to it.
      for(i = edge; i >= 0; i--) {
         if(ed[i][0] == v) {
            return Checkcyclic(ed, edge, check, ed[i][1]);
         }
      }
   }
   // In case, if the path ends then reassign the vertexes visited in that path to false again.
   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<<"Isolated Vertex!";
         }
         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-> { Isolated Vertex! }
5-> { 1 }
6-> { Isolated Vertex! }
7-> { Isolated Vertex! }
8-> { }
9-> { Isolated Vertex! }
10-> { 5 }