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.

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.

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.

« Prev - C++ Program to Generate a Graph for a Given Fixed Degree Sequence

» Next - C++ Program to Generate a Random UnDirected Graph for a Given Number of Edges

Related Posts:

Recommended Articles: