A vertex cover of an undirected graph is a subset of its vertices such that for every edge (u, v) of the graph, either āuā or āvā is in the vertex cover. Although the name is Vertex Cover, the set covers all edges of the given graph. Given an undirected graph, the vertex cover problem is to find minimum size vertex cover.Ā
The following are some examples.Ā
Ā
Vertex Cover Problem is a known NP Complete problem, i.e., there is no polynomial-time solution for this unless P = NP. There are approximate polynomial-time algorithms to solve the problem though. Following is a simple approximate algorithm adapted from CLRS book.
Naive Approach:
Consider all the subset of vertices one by one and find out whether it covers all edges of the graph. For eg. in a graph consisting only 3 vertices the set consisting of the combination of vertices are:{0,1,2,{0,1},{0,2},{1,2},{0,1,2}} . Using each element of this set check whether these vertices cover all the edges of the graph. Hence update the optimal answer. And hence print the subset having minimum number of vertices which also covers all the edges of the graph.
Approximate Algorithm for Vertex Cover:Ā
Ā
1) Initialize the result as {}
2) Consider a set of all edges in given graph. Let the set be E.
3) Do following while E is not empty
...a) Pick an arbitrary edge (u, v) from set E and add 'u' and 'v' to result
...b) Remove all edges from E which are either incident on u or v.
4) Return result
Below diagram to show the execution of the above approximate algorithm:Ā
Ā
How well the above algorithm perform?Ā
It can be proved that the above approximate algorithm never finds a vertex cover whose size is more than twice the size of the minimum possible vertex cover (Refer this for proof)
Implementation:Ā
The following are C++ and Java implementations of the above approximate algorithm.Ā
Ā
C++
// Program to print Vertex Cover of a given undirected graph#include<iostream>#include <list>using namespace std;Ā
// This class represents a undirected graph using adjacency list class Graph{Ā Ā Ā Ā int V;Ā Ā Ā // No. of verticesĀ Ā Ā Ā list<int> *adj;Ā // Pointer to an array containing adjacency listspublic:Ā Ā Ā Ā Graph(int V);Ā // ConstructorĀ Ā Ā Ā void addEdge(int v, int w); // function to add an edge to graphĀ Ā Ā Ā void printVertexCover();Ā // prints vertex cover};Ā
Graph::Graph(int V){Ā Ā Ā Ā this->V = V;Ā Ā Ā Ā adj = new list<int>[V];}Ā
void Graph::addEdge(int v, int w){Ā Ā Ā Ā adj[v].push_back(w); // Add w to vās list.Ā Ā Ā Ā adj[w].push_back(v); // Since the graph is undirected}Ā
// The function to print vertex covervoid Graph::printVertexCover(){Ā Ā Ā Ā // Initialize all vertices as not visited.Ā Ā Ā Ā bool visited[V];Ā Ā Ā Ā for (int i=0; i<V; i++)Ā Ā Ā Ā Ā Ā Ā Ā visited[i] = false;Ā
Ā Ā Ā Ā list<int>::iterator i;Ā
Ā Ā Ā Ā // Consider all edges one by oneĀ Ā Ā Ā for (int u=0; u<V; u++)Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā // An edge is only picked when both visited[u] and visited[v]Ā Ā Ā Ā Ā Ā Ā Ā // are falseĀ Ā Ā Ā Ā Ā Ā Ā if (visited[u] == false)Ā Ā Ā Ā Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // Go through all adjacents of u and pick the first notĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // yet visited vertex (We are basically picking an edgeĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // (u, v) from remaining edges.Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā for (i= adj[u].begin(); i != adj[u].end(); ++i)Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā int v = *i;Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if (visited[v] == false)Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // Add the vertices (u, v) to the result set.Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // We make the vertex u and v visited so thatĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // all edges from/to them would be ignoredĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā visited[v] = true;Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā visited[u]Ā = true;Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā break;Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā }Ā
Ā Ā Ā Ā // Print the vertex coverĀ Ā Ā Ā for (int i=0; i<V; i++)Ā Ā Ā Ā Ā Ā Ā Ā if (visited[i])Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā cout << i << " ";}Ā
// Driver program to test methods of graph classint main(){Ā Ā Ā Ā // Create a graph given in the above diagramĀ Ā Ā Ā Graph g(7);Ā Ā Ā Ā g.addEdge(0, 1);Ā Ā Ā Ā g.addEdge(0, 2);Ā Ā Ā Ā g.addEdge(1, 3);Ā Ā Ā Ā g.addEdge(3, 4);Ā Ā Ā Ā g.addEdge(4, 5);Ā Ā Ā Ā g.addEdge(5, 6);Ā
Ā Ā Ā Ā g.printVertexCover();Ā
Ā Ā Ā Ā return 0;} |
Java
// Java Program to print Vertex// Cover of a given undirected graphimport java.io.*;import java.util.*;import java.util.LinkedList;Ā
// This class represents an undirected // graph using adjacency listclass Graph{Ā Ā Ā Ā private int V;Ā Ā // No. of verticesĀ
Ā Ā Ā Ā // ArrayĀ of lists for Adjacency List RepresentationĀ Ā Ā Ā private LinkedList<Integer> adj[];Ā
Ā Ā Ā Ā // ConstructorĀ Ā Ā Ā Graph(int v)Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā V = v;Ā Ā Ā Ā Ā Ā Ā Ā adj = new LinkedList[v];Ā Ā Ā Ā Ā Ā Ā Ā for (int i=0; i<v; ++i)Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā adj[i] = new LinkedList();Ā Ā Ā Ā }Ā
Ā Ā Ā Ā //Function to add an edge into the graphĀ Ā Ā Ā void addEdge(int v, int w)Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā adj[v].add(w);Ā // Add w to v's list.Ā Ā Ā Ā Ā Ā Ā Ā adj[w].add(v);Ā //Graph is undirectedĀ Ā Ā Ā }Ā
Ā Ā Ā Ā // The function to print vertex coverĀ Ā Ā Ā void printVertexCover()Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā // Initialize all vertices as not visited.Ā Ā Ā Ā Ā Ā Ā Ā boolean visited[] = new boolean[V];Ā Ā Ā Ā Ā Ā Ā Ā for (int i=0; i<V; i++)Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā visited[i] = false;Ā
Ā Ā Ā Ā Ā Ā Ā Ā Iterator<Integer> i;Ā
Ā Ā Ā Ā Ā Ā Ā Ā // Consider all edges one by oneĀ Ā Ā Ā Ā Ā Ā Ā for (int u=0; u<V; u++)Ā Ā Ā Ā Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // An edge is only picked when both visited[u]Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // and visited[v] are falseĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if (visited[u] == false)Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // Go through all adjacents of u and pick theĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // first not yet visited vertex (We are basicallyĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā //Ā picking an edge (u, v) from remaining edges.Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā i = adj[u].iterator();Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā while (i.hasNext())Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā int v = i.next();Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if (visited[v] == false)Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // Add the vertices (u, v) to the resultĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // set. We make the vertex u and v visitedĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // so that all edges from/to them wouldĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // be ignoredĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā visited[v] = true;Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā visited[u]Ā = true;Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā break;Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā }Ā
Ā Ā Ā Ā Ā Ā Ā Ā // Print the vertex coverĀ Ā Ā Ā Ā Ā Ā Ā for (int j=0; j<V; j++)Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if (visited[j])Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā System.out.print(j+" ");Ā Ā Ā Ā }Ā
Ā Ā Ā Ā // Driver methodĀ Ā Ā Ā public static void main(String args[])Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā // Create a graph given in the above diagramĀ Ā Ā Ā Ā Ā Ā Ā Graph g = new Graph(7);Ā Ā Ā Ā Ā Ā Ā Ā g.addEdge(0, 1);Ā Ā Ā Ā Ā Ā Ā Ā g.addEdge(0, 2);Ā Ā Ā Ā Ā Ā Ā Ā g.addEdge(1, 3);Ā Ā Ā Ā Ā Ā Ā Ā g.addEdge(3, 4);Ā Ā Ā Ā Ā Ā Ā Ā g.addEdge(4, 5);Ā Ā Ā Ā Ā Ā Ā Ā g.addEdge(5, 6);Ā
Ā Ā Ā Ā Ā Ā Ā Ā g.printVertexCover();Ā Ā Ā Ā }}Ā
// This code is contributed by Aakash Hasija |
Python3
# Python3 program to print Vertex Cover# of a given undirected graph from collections import defaultdict Ā
# This class represents a directed graph # using adjacency list representation class Graph:Ā
Ā Ā Ā Ā def __init__(self, vertices):Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā # No. of verticesĀ Ā Ā Ā Ā Ā Ā Ā self.V = vertices Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā # Default dictionary to store graphĀ Ā Ā Ā Ā Ā Ā Ā self.graph = defaultdict(list) Ā
Ā Ā Ā Ā # Function to add an edge to graphĀ Ā Ā Ā def addEdge(self, u, v):Ā Ā Ā Ā Ā Ā Ā Ā self.graph[u].append(v)Ā
Ā Ā Ā Ā # The function to print vertex cover Ā Ā Ā Ā def printVertexCover(self):Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā # Initialize all vertices as not visited. Ā Ā Ā Ā Ā Ā Ā Ā visited = [False] * (self.V)Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā # Consider all edges one by one Ā Ā Ā Ā Ā Ā Ā Ā for u in range(self.V):Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā # An edge is only picked when Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā # both visited[u] and visited[v] Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā # are falseĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if not visited[u]:Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā # Go through all adjacents of u and Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā # pick the first not yet visited Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā # vertex (We are basically pickingĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā # an edge (u, v) from remaining edges. Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā for v in self.graph[u]:Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if not visited[v]:Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā # Add the vertices (u, v) to theĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā # result set. We make the vertexĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā # u and v visited so that all Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā # edges from/to them would Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā # be ignored Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā visited[v] = TrueĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā visited[u] = TrueĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā breakĀ
Ā Ā Ā Ā Ā Ā Ā Ā # Print the vertex cover Ā Ā Ā Ā Ā Ā Ā Ā for j in range(self.V):Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if visited[j]:Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā print(j, end = ' ')Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā print()Ā
# Driver codeĀ
# Create a graph given in # the above diagram g = Graph(7)g.addEdge(0, 1)g.addEdge(0, 2) g.addEdge(1, 3) g.addEdge(3, 4) g.addEdge(4, 5) g.addEdge(5, 6) Ā
g.printVertexCover()Ā
# This code is contributed by Prateek Gupta |
C#
// C# Program to print Vertex// Cover of a given undirected// graph using System;using System.Collections.Generic;Ā
// This class represents an // undirected graph using // adjacency list class Graph{ Ā Ā Ā // No. of vertices public int V; Ā
// Array of lists for // Adjacency List Representation public List<int> []adj; Ā
// Constructor public Graph(int v) { Ā Ā V = v; Ā Ā adj = new List<int>[v]; Ā
Ā Ā for (int i = 0; i < v; ++i) Ā Ā Ā Ā adj[i] = new List<int>(); } Ā
//Function to add an edge // into the graph void addEdge(int v, int w) { Ā Ā Ā // Add w to v's list. Ā Ā adj[v].Add(w);Ā Ā Ā Ā Ā //Graph is undirected Ā Ā adj[w].Add(v); } Ā
// The function to print // vertex cover void printVertexCover() { Ā Ā // Initialize all vertices Ā Ā // as not visited. Ā Ā bool []visited = new bool[V]; Ā
Ā Ā // Consider all edges one Ā Ā // by one Ā Ā for (int u = 0; u < V; u++) Ā Ā { Ā Ā Ā Ā // An edge is only pickedĀ Ā Ā Ā // when both visited[u] Ā Ā Ā Ā // and visited[v] are false Ā Ā Ā Ā if (visited[u] == false) Ā Ā Ā Ā { Ā Ā Ā Ā Ā Ā // Go through all adjacents Ā Ā Ā Ā Ā Ā // of u and pick the first Ā Ā Ā Ā Ā Ā // not yet visited vertex Ā Ā Ā Ā Ā Ā // (We are basically picking Ā Ā Ā Ā Ā Ā // an edge (u, v) from remainingĀ Ā Ā Ā Ā Ā // edges.Ā Ā Ā Ā Ā Ā foreach(int i in adj[u])Ā Ā Ā Ā Ā Ā { Ā Ā Ā Ā Ā Ā Ā Ā int v = i; Ā Ā Ā Ā Ā Ā Ā Ā if (visited[v] == false) Ā Ā Ā Ā Ā Ā Ā Ā { Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // Add the vertices (u, v) Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // to the result set. We Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // make the vertex u and Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // v visited so that all Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // edges from/to them would Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // be ignored Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā visited[v] = true; Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā visited[u] = true; Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā break; Ā Ā Ā Ā Ā Ā Ā Ā } Ā Ā Ā Ā Ā Ā } Ā Ā Ā Ā } Ā Ā } Ā
Ā Ā // Print the vertex cover Ā Ā for (int j = 0; j < V; j++) Ā Ā Ā Ā if (visited[j]) Ā Ā Ā Ā Ā Ā Console.Write(j + " "); } Ā
// Driver method public static void Main(String []args) { Ā Ā // Create a graph given in Ā Ā // the above diagram Ā Ā Graph g = new Graph(7); Ā Ā g.addEdge(0, 1); Ā Ā g.addEdge(0, 2); Ā Ā g.addEdge(1, 3); Ā Ā g.addEdge(3, 4); Ā Ā g.addEdge(4, 5); Ā Ā g.addEdge(5, 6); Ā
Ā Ā g.printVertexCover(); } } Ā
// This code is contributed by gauravrajput1 |
Javascript
<script>// Javascript Program to print Vertex// Cover of a given undirected graphĀ
// This class represents an undirected// graph using adjacency listclass Graph{Ā Ā Ā Ā Ā Ā Ā // ConstructorĀ Ā Ā Ā constructor(v)Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā this.V=v;Ā Ā Ā Ā Ā Ā Ā Ā this.adj = new Array(v);Ā Ā Ā Ā Ā Ā Ā Ā for (let i = 0; i < v; ++i)Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā this.adj[i] = [];Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā Ā // Function to add an edge into the graphĀ Ā Ā Ā addEdge(v, w)Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā this.adj[v].push(w);Ā // Add w to v's list.Ā Ā Ā Ā Ā Ā Ā Ā this.adj[w].push(v);Ā //Graph is undirectedĀ Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // The function to print vertex coverĀ Ā Ā Ā printVertexCover()Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā // Initialize all vertices as not visited.Ā Ā Ā Ā Ā Ā Ā Ā let visited = new Array(this.V);Ā Ā Ā Ā Ā Ā Ā Ā for (let i = 0; i < this.V; i++)Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā visited[i] = false;Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // Consider all edges one by oneĀ Ā Ā Ā Ā Ā Ā Ā for (let u = 0; u < this.V; u++)Ā Ā Ā Ā Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // An edge is only picked when both visited[u]Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // and visited[v] are falseĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if (visited[u] == false)Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // Go through all adjacents of u and pick theĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // first not yet visited vertex (We are basicallyĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā //Ā picking an edge (u, v) from remaining edges.Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā for(let i = 0; i < this.adj[u].length; i++)Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā let v = this.adj[u][i];Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if (visited[v] == false)Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // Add the vertices (u, v) to the resultĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // set. We make the vertex u and v visitedĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // so that all edges from/to them wouldĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // be ignoredĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā visited[v] = true;Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā visited[u]Ā = true;Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā break;Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // Print the vertex coverĀ Ā Ā Ā Ā Ā Ā Ā for (let j = 0; j < this.V; j++)Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if (visited[j])Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā document.write(j+" ");Ā Ā Ā Ā }}Ā
// Driver method// Create a graph given in the above diagramlet g = new Graph(7);g.addEdge(0, 1);g.addEdge(0, 2);g.addEdge(1, 3);g.addEdge(3, 4);g.addEdge(4, 5);g.addEdge(5, 6);Ā
g.printVertexCover();Ā
// This code is contributed by patel2127</script> |
Output:Ā
0 1 3 4 5 6
The Time Complexity of the above algorithm is O(V + E).
The space complexity of this solution is O(V), where V is the number of vertices of the graph. This is because we are using an array of size V to store the visited vertices.
Exact Algorithms:Ā
Although the problem is NP complete, it can be solved in polynomial time for the following types of graphs.Ā
1) Bipartite GraphĀ
2) Tree Graph
The problem to check whether there is a vertex cover of size smaller than or equal to a given number k can also be solved in polynomial time if k is bounded by O(LogV) (Refer this)
We will soon be discussing exact algorithms for vertex cover.
This article is contributed by Shubham. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above
Ā
Feeling lost in the world of random DSA topics, wasting time without progress? Itās time for a change! Join our DSA course, where weāll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
