Java Program to Check the Connectivity of Graph Using DFS

«
»
This is a Java Program to implement graph and check the connectivity between nodes using a standard Depth First Search algorithm. Algorithm visits the node that was traversed last or last come first serve basis. We create a visited array to avoid revisiting a node. If destination node appears in visited array, source and destination nodes are connected, not otherwise.

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

  1. //This is a java program to check the connectivity of a graph using DFS
  2. import java.util.Scanner;
  3. import java.util.Stack;
  4.  
  5. public class Connectivity_DFS
  6. {
  7.     private final int      vertices;
  8.     private int[][]        adjacency_matrix;
  9.     private Stack<Integer> stack;
  10.  
  11.     public Connectivity_DFS(int v)
  12.     {
  13.         vertices = v;
  14.         adjacency_matrix = new int[vertices + 1][vertices + 1];
  15.         stack = new Stack<Integer>();
  16.     }
  17.  
  18.     public void makeEdge(int to, int from, int edge)
  19.     {
  20.         try
  21.         {
  22.             adjacency_matrix[to][from] = edge;
  23.             adjacency_matrix[from][to] = edge;
  24.         } catch (ArrayIndexOutOfBoundsException index)
  25.         {
  26.             System.out.println("The vertices does not exists");
  27.         }
  28.     }
  29.  
  30.     public int getEdge(int to, int from)
  31.     {
  32.         try
  33.         {
  34.             return adjacency_matrix[to][from];
  35.         } catch (ArrayIndexOutOfBoundsException index)
  36.         {
  37.             System.out.println("The vertices does not exists");
  38.         }
  39.         return -1;
  40.     }
  41.  
  42.     public void dfs(int source)
  43.     {
  44.         int number_of_nodes = adjacency_matrix[source].length - 1;
  45.         int[] visited = new int[number_of_nodes + 1];
  46.         int i, element;
  47.         visited[source] = 1;
  48.         stack.push(source);
  49.         while (!stack.isEmpty())
  50.         {
  51.             element = stack.pop();
  52.             i = 1;// element;
  53.             while (i <= number_of_nodes)
  54.             {
  55.                 if (adjacency_matrix[element][i] == 1 && visited[i] == 0)
  56.                 {
  57.                     stack.push(i);
  58.                     visited[i] = 1;
  59.                 }
  60.                 i++;
  61.             }
  62.         }
  63.  
  64.         System.out.print("The source node " + source + " is connected to: ");
  65.         int count = 0;
  66.         for (int v = 1; v <= number_of_nodes; v++)
  67.             if (visited[v] == 1)
  68.             {
  69.                 System.out.print(v + " ");
  70.                 count++;
  71.             }
  72.  
  73.         if (count == number_of_nodes)
  74.             System.out.print("\nThe Graph is Connected ");
  75.         else
  76.             System.out.print("\nThe Graph is Disconnected ");
  77.     }
  78.  
  79.     public static void main(String args[])
  80.     {
  81.         int v, e, count = 1, to = 0, from = 0;
  82.         Scanner sc = new Scanner(System.in);
  83.         Connectivity_DFS graph;
  84.         System.out.println("The Undirected Graph Connectivity Test");
  85.         try
  86.         {
  87.             System.out.println("Enter the number of vertices: ");
  88.             v = sc.nextInt();
  89.             System.out.println("Enter the number of edges: ");
  90.             e = sc.nextInt();
  91.  
  92.             graph = new Connectivity_DFS(v);
  93.  
  94.             System.out.println("Enter the edges: <to> <from>");
  95.             while (count <= e)
  96.             {
  97.                 to = sc.nextInt();
  98.                 from = sc.nextInt();
  99.  
  100.                 graph.makeEdge(to, from, 1);
  101.                 count++;
  102.             }
  103.  
  104.             System.out.println("The adjacency matrix for the given graph is: ");
  105.             System.out.print("  ");
  106.             for (int i = 1; i <= v; i++)
  107.                 System.out.print(i + " ");
  108.             System.out.println();
  109.  
  110.             for (int i = 1; i <= v; i++)
  111.             {
  112.                 System.out.print(i + " ");
  113.                 for (int j = 1; j <= v; j++)
  114.                     System.out.print(graph.getEdge(i, j) + " ");
  115.                 System.out.println();
  116.             }
  117.  
  118.             System.out.println("Enter the Source Node: ");
  119.             int sourceNode = sc.nextInt();
  120.             graph.dfs(sourceNode);
  121.  
  122.         } catch (Exception E)
  123.         {
  124.             System.out.println("Somthing went wrong");
  125.         }
  126.  
  127.         sc.close();
  128.     }
  129. }

Output:

$ javac Connectivity_DFS.java
$ java Connectivity_DFS
 
The Undirected Graph Connectivity Test(DFS)
Enter the number of vertices: 
4
Enter the number of edges: 
2
Enter the edges: <to> <from>
1 2
1 3
The adjacency matrix for the given graph is: 
  1 2 3 4 
1 0 1 1 0 
2 1 0 0 0 
3 1 0 0 0 
4 0 0 0 0 
Enter the Source Node: 
2
The source node 2 is connected to: 1 2 3 
The Graph is Disconnected 
 
The Undirected Graph Connectivity Test(DFS)
Enter the number of vertices: 
4
Enter the number of edges: 
4
Enter the edges: <to> <from>
1 2
1 3
1 4
2 4
The adjacency matrix for the given graph is: 
  1 2 3 4 
1 0 1 1 1 
2 1 0 0 1 
3 1 0 0 0 
4 1 1 0 0 
Enter the Source Node: 
4
The source node 4 is connected to: 1 2 3 4 
The Graph is Connected

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
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
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.