C++ Program to Implement a Heuristic to Find the Vertex Cover of a Graph

«
»

This is a C++ Program To Implement Heuristic To Find A Vertex Cover Of A Given Graph.

Problem Description

The problem takes E edges as input and outputs vertex cover of the graph, implementing the following heuristic.

Vertex Cover of a Graph is to find, a set of vertices S, such that for every edge connecting A to B in graph, either A or B (or both) are present in S.

Example:
cpp-program-check-bipartite-graph

Possible Vertex Covers are: S = {1,2} or {1,3} or {1,4} or {2,3} or {2,4} or {3,4} or {1,2,3} or {1,2,4} or {2,3,4} or {1,3,4} or {1,2,3,4}.

Example:
cpp-program-check-vertex-cover-size-k-exists

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement

Some of the possible vertex covers are: {1,2,4,7} or {1,3,5,6} and many more.

Problem Solution

There is no polynomial time algorithm invented up to date to find the minimum size vertex cover, though many approximate algorithms(heuristics) do exist. Here, implementation of one such heuristic is shown. Size of Vertex Cover obtained from this heuristic won’t be more than twice the size minimum vertex cover and can be prove using Discrete Mathematics (Graph Theory). Size of vertex cover, is the cardinality of the vertex cover.

1. Initialize a set S as empty.
2. Take an edge E of the graph connecting lets say, A and B.
3. Add both vertex to our set S.
4. Discard all edges in the graph with endpoints at A or B.
5. Go to step 2, if some edge is till left in the graph.
6. The final set S is a vertex cover of the graph.

Check this: C++ Books | Programming MCQs
Program/Source Code

Here is source code of the C++ Program to generate Vertex Cover for a given graph. The program is successfully compiled and tested under Linux platform. The program output is also shown below.

#include<bits/stdc++.h>
 
using namespace std;
 
vector<vector<int> > graph;
bool vis[100011];
int i,j; //variables for loop iteration
 
vector<int> solve_vertex(int n,int e)
{
	//we start visiting edges
	vector<int> S;
	for(i=0;i<n;i++)
	{
		if(!vis[i])
		{
			for(j=0;j<(int)graph[i].size();j++)
			{
				if(!vis[graph[i][j]]) //we only select those edges whose
								      //both vertices have not been visited yet!
				{
					vis[i]=true;
					vis[graph[i][j]]=true;
					break;
				}
			}
		}
	}
	for(i=0;i<n;i++)
		if(vis[i])
			S.push_back(i);
	return S;
}
int main()
{
	int n,e,x,y;
	cout<<"Enter number of vertices:";
	cin>>n;
	cout<<"Enter number of Edges:";
	cin>>e;
	graph.resize(n);
	memset(vis,0,sizeof(vis));
	for(i=0;i<e;i++)
	{
		cout<<"Enter the end-points of edge "<<i+1<<" : ";
		cin>>x>>y;
		x--; y--;
		graph[x].push_back(y);
		graph[y].push_back(x);
	}
	vector<int> S = solve_vertex(n,e);
	cout<<"The required vertex cover is as follows:\n";
	for(i=0;i<(int)S.size();i++)
	cout<<S[i]+1<<" ";
	return 0;
}
Program Explanation

1. User must first enter the number of vertices, N, and then number of edges, E, in the graph.
2. It should be followed by E lines, denoting A and B, if there is an edge between A and B.
3. The graph is stored as adjacency list.
4. Then the Heuristic is implemented, with our vector “S” as the final vertex cover using “solve_vertex()” function.

advertisement
Runtime Test Cases
 
Case 1:
Enter number of vertices:4
Enter number of Edges:4
Enter the end-points of edge 1:1 2
Enter the end-points of edge 2:1 3
Enter the end-points of edge 3:4 3
Enter the end-points of edge 4:4 2
The required vertex cover is as follows:
1 2 3 4
 
Case 2:
Enter number of vertices:6
Enter number of Edges:3
Enter the end-points of edge 1:1 2
Enter the end-points of edge 2:2 3
Enter the end-points of edge 3:1 3
The required vertex cover is as follows:
1 2

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

advertisement

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.