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:
HashMap trong Java hoạt động như thế nào?
Uploading MultipartFile with Spring RestTemplate
Spring Security with Maven
An Introduction to ThreadLocal in Java
Use Liquibase to Safely Evolve Your Database Schema
Entity To DTO Conversion for a Spring REST API
Java Program to Find Minimum Element in an Array using Linear Search
HttpClient 4 – Send Custom Cookie
LinkedList trong java
Hướng dẫn Java Design Pattern – Singleton
Java Program to Implement DelayQueue API
Introduction to Java Serialization
Giới thiệu SOAP UI và thực hiện test Web Service
Netflix Archaius with Various Database Configurations
New Features in Java 9
Java Program to Find MST (Minimum Spanning Tree) using Kruskal’s Algorithm
Tạo chương trình Java đầu tiên sử dụng Eclipse
HTTP Authentification and CGI/Servlet
Remove HTML tags from a file to extract only the TEXT
Implementing a Binary Tree in Java
Spring Boot - Tracing Micro Service Logs
Java Program to Implement LinkedBlockingDeque API
Java Program to do a Breadth First Search/Traversal on a graph non-recursively
Spring Cloud Series – The Gateway Pattern
Java Program to Describe the Representation of Graph using Adjacency List
Java Program to Implement Hash Tables with Double Hashing
Spring Data JPA and Null Parameters
Spring RequestMapping
A Guide to Concurrent Queues in Java
Serverless Functions with Spring Cloud Function
Java Program to Implement Coppersmith Freivald’s Algorithm
How to Read a Large File Efficiently with Java