Java Program to Find All Back Edges in a Graph

This Java program,performs the DFS traversal on the given graph represented by a adjacency matrix to find all the back edges in a graph.the DFS traversal makes use of an stack.

Here is the source code of the Java program to find the back Edges.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.Scanner;
  4. import java.util.Set;
  5. import java.util.Stack;
  6.  
  7. public class BackEdges
  8. {
  9.     private Stack<Integer> stack;
  10.     private HashMap<Integer, Integer> backEdges;
  11.     private int adjacencyMatrix[][];
  12.  
  13.     public BackEdges() 
  14.     {
  15.         stack = new Stack<Integer>();
  16.         backEdges = new HashMap<Integer, Integer>();
  17.     }
  18.  
  19.     public void dfs(int adjacency_matrix[][], int source)
  20.     {
  21.         int number_of_nodes = adjacency_matrix[source].length - 1;
  22.         adjacencyMatrix = new int[number_of_nodes + 1][number_of_nodes + 1];
  23.         for (int sourcevertex = 1; sourcevertex <= number_of_nodes; sourcevertex++)
  24.         {
  25.             for (int destinationvertex = 1; destinationvertex <= number_of_nodes; destinationvertex++)
  26.             {
  27.                 adjacencyMatrix[sourcevertex][destinationvertex] = 
  28.                          adjacency_matrix[sourcevertex][destinationvertex];
  29.             }
  30.         }
  31.  
  32.         int visited[] = new int[number_of_nodes + 1];		
  33.         int element = source;		
  34.         int destination = source;			
  35.         visited[source] = 1;		
  36.         stack.push(source);
  37.  
  38.         while (!stack.isEmpty())
  39.         {
  40.             element = stack.peek();
  41.             destination = element;	
  42. 	    while (destination <= number_of_nodes)
  43. 	    {
  44.                 if (adjacencyMatrix[element][destination] == 1 && visited[destination] == 1)
  45.                 {
  46.                     if (stack.contains(destination))
  47.                     {	
  48.                         backEdges.put(element, destination);
  49.                         adjacencyMatrix[element][destination]= 0;	
  50.                     }
  51.                 }
  52.  
  53.      	        if (adjacencyMatrix[element][destination] == 1 && visited[destination] == 0)
  54. 	        {
  55.                     stack.push(destination);
  56.                     visited[destination] = 1;
  57.                     adjacencyMatrix[element][destination] = 0;
  58.                     element = destination;
  59.                     destination = 1;
  60. 	            continue;
  61.                 }  
  62.                 destination++;
  63. 	    }
  64.             stack.pop();	
  65.         }	
  66.     }
  67.  
  68.     public void printBackEdges()
  69.     {
  70.         System.out.println("\nSOURCE  : DESTINATION");
  71.         Set<Integer> source = backEdges.keySet();
  72.         for (Integer sourcevertex : source)
  73.         {
  74.             System.out.println(sourcevertex + "\t:\t"+ backEdges.get(sourcevertex));
  75.         }
  76.     }
  77.  
  78.     public static void main(String...arg)
  79.     {
  80.         int number_of_nodes, source;
  81.         Scanner scanner = null;
  82.  	try
  83.         {
  84. 	    System.out.println("Enter the number of nodes in the graph");
  85.             scanner = new Scanner(System.in);
  86.             number_of_nodes = scanner.nextInt();
  87.  
  88. 	    int adjacency_matrix[][] = new int[number_of_nodes + 1][number_of_nodes + 1];
  89. 	    System.out.println("Enter the adjacency matrix");
  90. 	    for (int i = 1; i <= number_of_nodes; i++)
  91. 	        for (int j = 1; j <= number_of_nodes; j++)
  92.                     adjacency_matrix[i][j] = scanner.nextInt();
  93.  
  94.    	    System.out.println("Enter the source for the graph");
  95.             source = scanner.nextInt(); 
  96.  
  97.             BackEdges backEdges = new BackEdges();
  98.             backEdges.dfs(adjacency_matrix, source);
  99.             backEdges.printBackEdges();
  100.  
  101.         }catch(InputMismatchException inputMismatch)
  102.         {
  103.             System.out.println("Wrong Input format");
  104.         }	
  105.         scanner.close();	
  106.     }	
  107. }

$javac BackEdges.java
$java BackEdges
Enter the number of nodes in the graph
4
Enter the adjacency matrix
0 1 0 0 
0 0 1 0
0 0 0 1
0 1 0 0 
Enter the source for the graph
1
The Back Edges are given by
 
SOURCE  : DESTINATION
4	:	2

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.