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.
import java.util.HashMap; import java.util.InputMismatchException; import java.util.Scanner; import java.util.Set; import java.util.Stack; public class BackEdges { private Stack<Integer> stack; private HashMap<Integer, Integer> backEdges; private int adjacencyMatrix[][]; public BackEdges() { stack = new Stack<Integer>(); backEdges = new HashMap<Integer, Integer>(); } public void dfs(int adjacency_matrix[][], int source) { int number_of_nodes = adjacency_matrix.length - 1; adjacencyMatrix = new int[number_of_nodes + 1][number_of_nodes + 1]; for (int sourcevertex = 1; sourcevertex <= number_of_nodes; sourcevertex++) { for (int destinationvertex = 1; destinationvertex <= number_of_nodes; destinationvertex++) { adjacencyMatrix[sourcevertex][destinationvertex] = adjacency_matrix[sourcevertex][destinationvertex]; } } int visited[] = new int[number_of_nodes + 1]; int element = source; int destination = source; visited = 1; stack.push(source); while (!stack.isEmpty()) { element = stack.peek(); destination = element; while (destination <= number_of_nodes) { if (adjacencyMatrix[element][destination] == 1 && visited[destination] == 1) { if (stack.contains(destination)) { backEdges.put(element, destination); adjacencyMatrix[element][destination]= 0; } } if (adjacencyMatrix[element][destination] == 1 && visited[destination] == 0) { stack.push(destination); visited[destination] = 1; adjacencyMatrix[element][destination] = 0; element = destination; destination = 1; continue; } destination++; } stack.pop(); } } public void printBackEdges() { System.out.println("\nSOURCE : DESTINATION"); Set<Integer> source = backEdges.keySet(); for (Integer sourcevertex : source) { System.out.println(sourcevertex + "\t:\t"+ backEdges.get(sourcevertex)); } } public static void main(String...arg) { int number_of_nodes, source; Scanner scanner = null; try { System.out.println("Enter the number of nodes in the graph"); scanner = new Scanner(System.in); number_of_nodes = scanner.nextInt(); int adjacency_matrix[][] = new int[number_of_nodes + 1][number_of_nodes + 1]; System.out.println("Enter the adjacency matrix"); for (int i = 1; i <= number_of_nodes; i++) for (int j = 1; j <= number_of_nodes; j++) adjacency_matrix[i][j] = scanner.nextInt(); System.out.println("Enter the source for the graph"); source = scanner.nextInt(); BackEdges backEdges = new BackEdges(); backEdges.dfs(adjacency_matrix, source); backEdges.printBackEdges(); }catch(InputMismatchException inputMismatch) { System.out.println("Wrong Input format"); } scanner.close(); } }
$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
Related posts:
Setting a Request Timeout for a Spring REST API
Count Occurrences of a Char in a String
Assertions in JUnit 4 and JUnit 5
Java Program to Implement Gaussian Elimination Algorithm
Jackson vs Gson
Java Program to Implement Knapsack Algorithm
Programmatic Transaction Management in Spring
Java Program to Implement Interpolation Search Algorithm
Autoboxing và Unboxing trong Java
Java Program to Implement Heap
Redirect to Different Pages after Login with Spring Security
The Basics of Java Security
Guide to DelayQueue
Java Program to Generate All Subsets of a Given Set in the Gray Code Order
Hướng dẫn Java Design Pattern – Chain of Responsibility
The Registration Process With Spring Security
More Jackson Annotations
HttpClient with SSL
Java – Reader to InputStream
Template Engines for Spring
How to Find an Element in a List with Java
Java Program to Generate Random Hexadecimal Byte
Java Program to Implement Brent Cycle Algorithm
StringBuilder vs StringBuffer in Java
Using a List of Values in a JdbcTemplate IN Clause
Java Program to Generate Random Numbers Using Multiply with Carry Method
A Guide to JPA with Spring
Java Program to Perform the Shaker Sort
Send email with JavaMail
Spring MVC Setup with Kotlin
Receive email using POP3
Guide to Guava Table