Chương trình C ++ để tạo một đồ thị ngẫu nhiên không định hướng cho một số cạnh nhất định

Đây là một chương trình C ++ trong đó chúng tôi tạo một đồ thị ngẫu nhiên vô hướng cho các cạnh ‘e’ đã cho. Thuật toán này về cơ bản thực hiện trên một mạng lớn và độ phức tạp về thời gian của thuật toán này là O (log (n)).

Thuật toán

Begin
   Function GenerateRandomGraphs(), has ‘e’ as the number edges in the argument list.
   Initialize i = 0
   while(i < e)
      edge[i][0] = rand()%N+1
      edge[i][1] = rand()%N+1
      Increment I;
   For i = 0 to N-1
      Initialize count = 0
      For j = 0 to e-1
         if(edge[j][0] == i+1)
            Print edge[j][1]
            Increase count
         else if(edge[j][1] == i+1)
            Print edge[j][0]
            Increase count
         else if(j == e-1 && count == 0)
   Print Isolated Vertex
End

Ví dụ

#include<iostream>
#include<stdlib.h>
#define N 10
using namespace std;
void GenerateRandomGraphs(int e) {
   int i, j, edge[e][2], count;
   i = 0;
   // generate a connection between two random numbers, for //sample a small case, limit the number of vertex to 10.
   while(i < e) {
      edge[i][0] = rand()%N+1;
      edge[i][1] = rand()%N+1;
      i++;
   }
   //Print all the connection of each vertex, irrespective of the //direction.
   cout<<"\nThe generated random graph is: ";
   for(i = 0; i < N; i++) {
      count = 0;
      cout<<"\n\t"<<i+1<<"-> { ";
         for(j = 0; j < e; j++) {
            if(edge[j][0] == i+1) {
               cout<<edge[j][1]<<" ";
               count++;
            }
            else if(edge[j][1] == i+1) {
               cout<<edge[j][0]<<" ";
               count++;
            }
            //Print “Isolated vertex” for the vertex having zero degree.
            else if(j == e-1 && count == 0)
               cout<<"Isolated Vertex!";
         }
      cout<<" }";
   }
}
int main() {
   int n, i ,e;
   cout<<"Enter the number of edges for the random graphs: ";
   cin>>e;
   GenerateRandomGraphs(e);
}

Đầu ra

Enter the number of edges for the random graphs: 10

The generated random graph is:
1-> { 10 7 }
2-> { 10 }
3-> { 7 8 7 }
4-> { 7 6 7 }
5-> { Isolated Vertex! }
6-> { 8 4 }
7-> { 4 3 4 1 3 }
8-> { 6 3 }
9-> { Isolated Vertex! }
10-> { 2 1 }