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

Code:

#include    bits/stdc++.h

using namespace std;

vector > graph;
bool vis[100011];
int i,j; //variables for loop iteration

vector solve_vertex(int n,int e)
{
//we start visiting edges
vector S;
for(i=0;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
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
{
cout<<"Enter the end-points of edge "<
cin>>x>>y;
x--; y--;
graph[x].push_back(y);
graph[y].push_back(x);
}
vector S = solve_vertex(n,e);
cout<<"The required vertex cover is as follows:\n";
for(i=0;i<(int)S.size();i++)
cout<
return 0;
}


Output:

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



More C++ Programs: