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

Computer Programming

C C++ Java Python Perl Programs Examples with Output -useful for Schools & College Students

Tuesday, September 26, 2017

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

Program:
#include<bits/stdc++.h>

using namespace std;

vector<vector<int> > graph;
bool vis;
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;
}

Output:
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