Java - Vertex Cover

What is a Vertex Cover?

A vertex cover is a set of vertices such that every edge in the graph has at least one endpoint in this set.

This greedy algorithm gives a solution that is at most twice the size of the minimum vertex cover.

Java Implementation

import java.util.*;

class Graph {

    private int V;

    private ArrayList<ArrayList> adj;

    Graph(int V) {

        this.V = V;

        adj = new ArrayList<>();

        for (int i = 0; i < V; i++)

            adj.add(new ArrayList<>());

    }

    void addEdge(int u, int v) {

        adj.get(u).add(v);

        adj.get(v).add(u); // Undirected graph

    }

    void vertexCover() {

        boolean[] visited = new boolean[V];

        HashSet cover = new HashSet<>();

        for (int u = 0; u < V; u++) {

            if (!visited[u]) {

                for (int v : adj.get(u)) {

                    if (!visited[v]) {

                        visited[u] = true;

                        visited[v] = true;

                        cover.add(u);

                        cover.add(v);

                        break;

                    }

                }

            }

        }

        System.out.println("Approximate Vertex Cover:");

        ArrayList sortedCover = new ArrayList<>(cover);

        Collections.sort(sortedCover);

        for (int node : sortedCover) {

            System.out.print(node + " ");

        }

        System.out.println();

    }

}

public class VertexCoverExample {

    public static void main(String[] args) {

        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.vertexCover();

    }

}

Output

Approximate Vertex Cover:

0 1 3 4 5 6