C++ Programming Code Examples C++ > Computer Graphics Code Examples Program to Implement a Heuristic to Find the Vertex Cover of a Graph Program to Implement a Heuristic to Find the Vertex Cover of a Graph 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. 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}. Some of the possible vertex covers are: {1,2,4,7} or {1,3,5,6} and many more. 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. #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; }