C++ Program to Create a Random Graph using Random Edge Selection

«
»

This is a C++ program to construct a random graph by the method of random edge selection.

Problem Description

1. This algorithm generates a undirected random graph for the given number edges and vertexes.
2. The time complexity of this algorithm is O(v*e).

Problem Solution

1. This algorithm takes the input of the number of vertexes and edges of the graph.
2. It connects vertexes randomly and generates cyclic, acyclic or disconnected undirected graphs.

advertisement
Program/Source Code

C++ Program to construct a random graph by the method of random edge selection.
This program is successfully run on Dev-C++ using TDM-GCC 4.9.2 MinGW compiler on a Windows system.

#include<iostream>
#include<stdlib.h>
 
using namespace std;
 
// A function to generate random graph.
void GenerateRandGraphs(int NOE, int NOV)
{
	int i, j, edge[NOE][2], count;
 
	i = 0;
	// Build a connection between two random vertex.
	while(i < NOE)
	{
		edge[i][0] = rand()%NOV+1;
		edge[i][1] = rand()%NOV+1;
 
		if(edge[i][0] == edge[i][1])
			continue;
		else
		{
			for(j = 0; j < i; j++)
			{
				if((edge[i][0] == edge[j][0] && edge[i][1] == edge[j][1]) || (edge[i][0] == edge[j][1] && edge[i][1] == edge[j][0]))
					i--;
			}
		}
		i++;
	}
 
	// Print the random graph.
	cout<<"\nThe generated random random graph is: ";
	for(i = 0; i < NOV; i++)
	{
		count = 0;
		cout<<"\n\t"<<i+1<<"-> { ";
		for(j = 0; j < NOE; j++)
		{
			if(edge[j][0] == i+1)
			{
				cout<<edge[j][1]<<"   ";
				count++;
			}
			else if(edge[j][1] == i+1)
			{
				cout<<edge[j][0]<<"   ";
				count++;
			}
			else if(j == NOE-1 && count == 0)
				cout<<"Isolated Vertex!";
		}
		cout<<" }";
	}	
}
 
 
int main()
{
	int n, i, e, v;
 
	cout<<"Random graph generation: ";
 
	// Take the input of the vertex and edges.
	cout<<"\nEnter the number of vertexes the graph have: ";
	cin>>v;
	cout<<"\nEnter the number of edges the graph have: ";
	cin>>e;
 
	// A function to generate a random undirected graph with e edges and v vertexes.
	GenerateRandGraphs(e, v);
}
Program Explanation

1. Take the input of the number of edges and number of vertex of the graph.
2. Call GenerateRandGraphs(), with ‘e’ as the number of edges and ‘v’ as the number of vertexes, in the argument list.
3. Inside GenerateRandGraphs(), generate a connection between two random numbers.
4. Check for the self-edge and multiple edges between two vertexes.
5. Print all the connection of each vertex, irrespective of the direction.
6. Print “Isolated vertex” for the vertex having zero degrees.
7. Exit.

Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
advertisement
Runtime Test Cases
Case 1:
Random graph generation:
Enter the number of vertexes the graph have: 20
 
Enter the number of edges the graph have: 50
 
The generated random random graph is:
        1-> { 15   3   17    }
        2-> { 8   12   17   4   7   10   6    }
        3-> { 5   16   14   13   18   11   1   19    }
        4-> { 12   2   10   7    }
        5-> { 10   3   12   14   8   9   15   20   11   13    }
        6-> { 7   2    }
        7-> { 8   9   6   2   17   4   18   14    }
        8-> { 2   17   7   20   5    }
        9-> { 14   7   5   12    }
        10-> { 5   13   19   11   4   2    }
        11-> { 3   10   5    }
        12-> { 2   5   19   4   9    }
        13-> { 3   10   5    }
        14-> { 3   5   9   16   7    }
        15-> { 1   16   5    }
        16-> { 3   19   15   17   14    }
        17-> { 8   2   16   1   7    }
        18-> { 3   20   19   7    }
        19-> { 16   12   10   18   3   20    }
        20-> { 8   18   5   19    }

Sanfoundry Global Education & Learning Series – C++ Algorithms.
To practice all C++ Algorithms, here is complete set of 1000 C++ Algorithms.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.