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.

advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

If you find any mistake above, kindly email to [email protected]

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 & discussions at Telegram SanfoundryClasses.