Java Program to Find Strongly Connected Components in Graphs

«
»
This Java program, displays the Strong Connected Components of graph.A directed graph is called strongly connected if there is a path from each vertex in the graph to every other vertex. In particular , this means paths in each direction; a path from a to b and also a path from b to a.

Here is the source code of the Java program to display the Strong Connected Components of a graph. The Java program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. import java.util.HashMap;
  2. import java.util.InputMismatchException;
  3. import java.util.Map;
  4. import java.util.Scanner;
  5. import java.util.Stack;
  6.  
  7. public class StrongConnectedComponents
  8. {
  9.     private int leader = 0;
  10.     private int[] leader_node;
  11.     private int explore[];
  12.     private int finishing_time_of_node[];
  13.     private int finishing_time = 1;
  14.     private int number_of_nodes;
  15.     private Stack<Integer> stack;
  16.     private Map<Integer, Integer> finishing_time_map;
  17.  
  18.     public StrongConnectedComponents(int number_of_nodes)
  19.     {
  20.         this.number_of_nodes = number_of_nodes;
  21.         leader_node = new int[number_of_nodes + 1];
  22.         explore = new int[number_of_nodes + 1];
  23.         finishing_time_of_node = new int[number_of_nodes + 1];
  24.         stack = new Stack<Integer>();
  25.         finishing_time_map = new HashMap<Integer, Integer>();
  26.     }
  27.  
  28.     public void strongConnectedComponent(int adjacency_matrix[][])
  29.     {
  30.         for (int i = number_of_nodes; i > 0; i--)
  31.         {
  32.             if (explore[i] == 0)
  33.             {
  34.                 dfs_1(adjacency_matrix, i);
  35.             }
  36.         }
  37.         int rev_matrix[][] = new int[number_of_nodes + 1][number_of_nodes + 1];
  38.         for (int i = 1; i <= number_of_nodes; i++)
  39.         {
  40.             for (int j = 1; j <= number_of_nodes; j++)
  41.             {
  42.                 if (adjacency_matrix[i][j] == 1)
  43.                     rev_matrix[finishing_time_of_node[j]][finishing_time_of_node[i]] = adjacency_matrix[i][j];
  44.             }
  45.         }
  46.  
  47.         for (int i = 1; i <= number_of_nodes; i++)
  48.         {
  49.             explore[i] = 0;
  50.             leader_node[i] = 0;
  51.         }
  52.  
  53.         for (int i = number_of_nodes; i > 0; i--)
  54.         {
  55.             if (explore[i] == 0)
  56.             {
  57.                 leader = i;
  58.                 dfs_2(rev_matrix, i);
  59.             }
  60.         }
  61.     }
  62.  
  63.     public void dfs_1(int adjacency_matrix[][], int source)
  64.     {
  65.         explore[source] = 1;
  66.         stack.push(source);
  67.         int i = 1;
  68.         int element = source;
  69.  
  70.         while (!stack.isEmpty())
  71.         {
  72.             element = stack.peek();
  73.             i = 1;
  74.             while (i <= number_of_nodes)
  75.             {
  76.                 if (adjacency_matrix[element][i] == 1 && explore[i] == 0)
  77.                 {
  78.                     stack.push(i);
  79.                     explore[i] = 1;
  80.                     element = i;
  81.                     i = 1;
  82.                     continue;
  83.                 }
  84.                 i++;
  85.             }
  86.             int poped = stack.pop();
  87.             int time = finishing_time++;
  88.             finishing_time_of_node[poped] = time;
  89.             finishing_time_map.put(time, poped);
  90.         }
  91.     }
  92.  
  93.     public void dfs_2(int rev_matrix[][], int source)
  94.     {
  95.         explore[source] = 1;
  96.         leader_node[finishing_time_map.get(source)] = leader;
  97.         stack.push(source);
  98.         int i = 1;
  99.         int element = source;
  100.         while (!stack.isEmpty())
  101.         {
  102.             element = stack.peek();
  103.             i = 1;
  104.             while (i <= number_of_nodes)
  105.             {
  106.                 if (rev_matrix[element][i] == 1 && explore[i] == 0)
  107.                 {
  108.                     if (leader_node[finishing_time_map.get(i)] == 0)
  109.                         leader_node[finishing_time_map.get(i)] = leader;
  110.                     stack.push(i);
  111.                     explore[i] = 1;
  112.                     element = i;
  113.                     i = 1;
  114.                     continue;
  115.                 }
  116.                 i++;
  117.             }
  118.             stack.pop();
  119.         }
  120.     }
  121.  
  122.     public static void main(String... arg)
  123.     { 
  124.         int number_of_nodes;
  125.         Scanner scanner = null;
  126.         try
  127.         {
  128.             System.out.println("Enter the number of nodes in the graph");
  129.             scanner = new Scanner(System.in);
  130.             number_of_nodes = scanner.nextInt();
  131.  
  132.             int adjacency_matrix[][] = new int[number_of_nodes + 1][number_of_nodes + 1];
  133.             System.out.println("Enter the adjacency matrix");
  134.             for (int i = 1; i <= number_of_nodes; i++)
  135.                 for (int j = 1; j <= number_of_nodes; j++)	
  136.                     adjacency_matrix[i][j] = scanner.nextInt();
  137.  
  138.             StrongConnectedComponents strong = new StrongConnectedComponents(number_of_nodes);
  139.             strong.strongConnectedComponent(adjacency_matrix);
  140.  
  141.             System.out.println("The Strong Connected Components are");
  142.             for (int i = 1; i < strong.leader_node.length; i++)
  143.             {
  144.                 System.out.println( "Node " + i+ "belongs to SCC" 
  145.                     + strong.finishing_time_map.get(strong.leader_node[i]));
  146.             }
  147.         } catch (InputMismatchException inputMismatch)
  148.         {	
  149.             System.out.println("Wrong Input Format");
  150.         }
  151.     }
  152. }

$javac StrongConnectedComponents.java
$java StrongConnectedComponenets
Enter the number of nodes in the graph
8
Enter the adjacency matrix
0 1 0 0 0 0 0 0 
0 0 0 0 0 0 1 0 
0 0 0 1 1 0 0 0 
0 1 0 0 0 0 1 0
0 0 0 0 0 0 0 1 
1 1 0 0 0 0 0 0
0 0 0 0 0 1 0 0 
0 0 1 1 0 0 0 0 
The Strong Connected Components are
Node 1 belongs to SCC 2 
Node 2 belongs to SCC 2 
Node 3 belongs to SCC 8 
Node 4 belongs to SCC 4 
Node 5 belongs to SCC 8 
Node 6 belongs to SCC 2 
Node 7 belongs to SCC 2 
Node 8 belongs to SCC 8

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

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.