**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[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;

}

**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

## No comments:

## Post a Comment