Java Program to Find the Vertex Connectivity of a Graph

This is a java program to find the vertex connectivity of a graph. Vertex connectivity simply means number of articulations points in a graph, articulation points are vertices of a graph whem removed makes graph disconnected.

Here is the source code of the Java Program to Find the Vertex Connectivity of a Graph. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1.  
  2. // Number of articulation points in a graph
  3. package com.sanfoundry.graph;
  4.  
  5. import java.util.Iterator;
  6. import java.util.NoSuchElementException;
  7. import java.util.Scanner;
  8. import java.util.Stack;
  9.  
  10. class VCBag<Item> implements Iterable<Item>
  11. {
  12.     private int N;    // number of elements in VCBag
  13.     private Node<Item> first;    // beginning of VCBag
  14.  
  15.     // helper linked list class
  16.     private static class Node<Item>
  17.     {
  18.         private Item item;
  19.         private Node<Item> next;
  20.     }
  21.  
  22.     public VCBag()
  23.     {
  24.         first = null;
  25.         N = 0;
  26.     }
  27.  
  28.     public boolean isEmpty()
  29.     {
  30.         return first == null;
  31.     }
  32.  
  33.     public int size()
  34.     {
  35.         return N;
  36.     }
  37.  
  38.     public void add(Item item)
  39.     {
  40.         Node<Item> oldfirst = first;
  41.         first = new Node<Item>();
  42.         first.item = item;
  43.         first.next = oldfirst;
  44.         N++;
  45.     }
  46.  
  47.     public Iterator<Item> iterator()
  48.     {
  49.         return new ListIterator<Item>(first);
  50.     }
  51.  
  52.     // an iterator, doesn't implement remove() since it's optional
  53.     @SuppressWarnings("hiding")
  54.     private class ListIterator<Item> implements Iterator<Item>
  55.     {
  56.         private Node<Item> current;
  57.  
  58.         public ListIterator(Node<Item> first)
  59.         {
  60.             current = first;
  61.         }
  62.  
  63.         public boolean hasNext()
  64.         {
  65.             return current != null;
  66.         }
  67.  
  68.         public void remove()
  69.         {
  70.             throw new UnsupportedOperationException();
  71.         }
  72.  
  73.         public Item next()
  74.         {
  75.             if (!hasNext())
  76.                 throw new NoSuchElementException();
  77.             Item item = current.item;
  78.             current = current.next;
  79.             return item;
  80.         }
  81.     }
  82. }
  83.  
  84. class VCGraph
  85. {
  86.     private final int V;
  87.     private int E;
  88.     private VCBag<Integer>[] adj;
  89.  
  90.     @SuppressWarnings("unchecked")
  91.     public VCGraph(int V)
  92.     {
  93.         if (V < 0)
  94.             throw new IllegalArgumentException(
  95.                     "Number of vertices must be nonnegative");
  96.         this.V = V;
  97.         this.E = 0;
  98.         adj = (VCBag<Integer>[]) new VCBag[V];
  99.         for (int v = 0; v < V; v++)
  100.         {
  101.             adj[v] = new VCBag<Integer>();
  102.         }
  103.         System.out.println("Enter the number of edges: ");
  104.         Scanner sc = new Scanner(System.in);
  105.         int E = sc.nextInt();
  106.         if (E < 0)
  107.         {
  108.             sc.close();
  109.             throw new IllegalArgumentException(
  110.                     "Number of edges must be nonnegative");
  111.         }
  112.         System.out.println("Enter the edges: <from> <to>");
  113.         for (int i = 0; i < E; i++)
  114.         {
  115.             int v = sc.nextInt();
  116.             int w = sc.nextInt();
  117.             addEdge(v, w);
  118.         }
  119.         sc.close();
  120.     }
  121.  
  122.     public VCGraph(VCGraph G)
  123.     {
  124.         this(G.V());
  125.         this.E = G.E();
  126.         for (int v = 0; v < G.V(); v++)
  127.         {
  128.             // reverse so that adjacency list is in same order as original
  129.             Stack<Integer> reverse = new Stack<Integer>();
  130.             for (int w : G.adj[v])
  131.             {
  132.                 reverse.push(w);
  133.             }
  134.             for (int w : reverse)
  135.             {
  136.                 adj[v].add(w);
  137.             }
  138.         }
  139.     }
  140.  
  141.     public int V()
  142.     {
  143.         return V;
  144.     }
  145.  
  146.     public int E()
  147.     {
  148.         return E;
  149.     }
  150.  
  151.     public void addEdge(int v, int w)
  152.     {
  153.         if (v < 0 || v >= V)
  154.             throw new IndexOutOfBoundsException();
  155.         if (w < 0 || w >= V)
  156.             throw new IndexOutOfBoundsException();
  157.         E++;
  158.         adj[v].add(w);
  159.         adj[w].add(v);
  160.     }
  161.  
  162.     public Iterable<Integer> adj(int v)
  163.     {
  164.         if (v < 0 || v >= V)
  165.             throw new IndexOutOfBoundsException();
  166.         return adj[v];
  167.     }
  168.  
  169.     public String toString()
  170.     {
  171.         StringBuilder s = new StringBuilder();
  172.         String NEWLINE = System.getProperty("line.separator");
  173.         s.append(V + " vertices, " + E + " edges " + NEWLINE);
  174.         for (int v = 0; v < V; v++)
  175.         {
  176.             s.append(v + ": ");
  177.             for (int w : adj[v])
  178.             {
  179.                 s.append(w + " ");
  180.             }
  181.             s.append(NEWLINE);
  182.         }
  183.         return s.toString();
  184.     }
  185. }
  186.  
  187. public class VertexConnectivity
  188. {
  189.     private int[] low;
  190.     private int[] pre;
  191.     private int cnt;
  192.     private boolean[] articulation;
  193.  
  194.     public VertexConnectivity(VCGraph G)
  195.     {
  196.         low = new int[G.V()];
  197.         pre = new int[G.V()];
  198.         articulation = new boolean[G.V()];
  199.         for (int v = 0; v < G.V(); v++)
  200.             low[v] = -1;
  201.         for (int v = 0; v < G.V(); v++)
  202.             pre[v] = -1;
  203.         for (int v = 0; v < G.V(); v++)
  204.             if (pre[v] == -1)
  205.                 dfs(G, v, v);
  206.     }
  207.  
  208.     private void dfs(VCGraph G, int u, int v)
  209.     {
  210.         int children = 0;
  211.         pre[v] = cnt++;
  212.         low[v] = pre[v];
  213.         for (int w : G.adj(v))
  214.         {
  215.             if (pre[w] == -1)
  216.             {
  217.                 children++;
  218.                 dfs(G, v, w);
  219.                 // update low number
  220.                 low[v] = Math.min(low[v], low[w]);
  221.                 // non-root of DFS is an articulation point if low[w] >= pre[v]
  222.                 if (low[w] >= pre[v] && u != v)
  223.                     articulation[v] = true;
  224.             }
  225.             // update low number - ignore reverse of edge leading to v
  226.             else if (w != u)
  227.                 low[v] = Math.min(low[v], pre[w]);
  228.         }
  229.         // root of DFS is an articulation point if it has more than 1 child
  230.         if (u == v && children > 1)
  231.             articulation[v] = true;
  232.     }
  233.  
  234.     // is vertex v an articulation point?
  235.     public boolean isArticulation(int v)
  236.     {
  237.         return articulation[v];
  238.     }
  239.  
  240.     // test client
  241.     public static void main(String[] args)
  242.     {
  243.         Scanner sc = new Scanner(System.in);
  244.         System.out.println("Enter the number of vertices: ");
  245.         VCGraph G = new VCGraph(sc.nextInt());
  246.         System.out.println(G);
  247.         VertexConnectivity bic = new VertexConnectivity(G);
  248.         int count = 0;
  249.         for (int v = 0; v < G.V(); v++)
  250.             if (bic.isArticulation(v))
  251.                 count++;
  252.         System.out.println("Vertex Connectivity: " + count);
  253.         sc.close();
  254.     }
  255. }

Output:

$ javac VertexConnectivity.java
$ java VertexConnectivity
 
Enter the number of vertices: 
6
Enter the number of edges: 
7
Enter the edges: <from> <to>
0 1
1 2
1 3
3 4
4 5
5 3
5 2
6 vertices, 7 edges 
0: 1 
1: 3 2 0 
2: 5 1 
3: 5 4 1 
4: 5 3 
5: 2 3 4 
 
Vertex Connectivity: 1

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement

Here’s the list of Best Books in Java Programming, Data Structures and Algorithms.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
I’m Manish - Founder and CTO at Sanfoundry. I’ve been working in tech for over 25 years, with deep focus on Linux kernel, SAN technologies, Advanced C, Full Stack and Scalable website designs.

You can connect with me on LinkedIn, watch my Youtube Masterclasses, or join my Telegram tech discussions.

If you’re in your 40s–60s and exploring new directions in your career, I also offer mentoring. Learn more here.