This Java program,performs the DFS traversal on the given graph represented by a adjacency matrix to find all the cross edges in a graph.the DFS traversal makes use of an stack.
Here is the source code of the Java program to find the cross 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 CrossEdge { private Stack<Integer> stack; private HashMap<Integer, Integer> crossEdges; private int adjacencyMatrix[][]; public CrossEdge() { stack = new Stack<Integer>(); crossEdges = 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)) { if ( element > destination ) crossEdges.put(element, destination); } } 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 printCrossEdges() { System.out.println("\nSOURCE : DESTINATION"); Set<Integer> source = crossEdges.keySet(); for (Integer sourcevertex : source) { System.out.println(sourcevertex + "\t:\t"+ crossEdges.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(); CrossEdge crossEdge = new CrossEdge(); crossEdge.dfs(adjacency_matrix, source); crossEdge.printCrossEdges(); }catch(InputMismatchException inputMismatch) { System.out.println("Wrong Input format"); } scanner.close(); } }
$javac CrossEdge.java $java CrossEdge Enter the number of nodes in the graph 5 Enter the adjacency matrix 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 Enter the source for the graph 1 The Cross Edges are SOURCE : DESTINATION 4 : 2 5 : 3
Related posts:
Java Program to Implement Quick sort
Từ khóa static và final trong java
Introduction to Eclipse Collections
Using JWT with Spring Security OAuth
A Guide to Java HashMap
Join and Split Arrays and Collections in Java
Hướng dẫn Java Design Pattern – Memento
Java Program to Implement Network Flow Problem
Java Program to Generate All Possible Combinations Out of a, b, c, d, e
Java Program to Check the Connectivity of Graph Using BFS
Hướng dẫn sử dụng Printing Service trong Java
Guide to Java OutputStream
Java Program to Show the Duality Transformation of Line and Point
Spring 5 Functional Bean Registration
Java Program to Solve any Linear Equations
Spring Boot - Building RESTful Web Services
Vector trong Java
REST Pagination in Spring
Guide to Guava Multimap
Hướng dẫn Java Design Pattern – Abstract Factory
Spring Boot - Zuul Proxy Server and Routing
OAuth2 for a Spring REST API – Handle the Refresh Token in Angular
Java Program to Perform Inorder Non-Recursive Traversal of a Given Binary Tree
Spring Cloud Connectors and Heroku
Java Program to Compare Binary and Sequential Search
Java – Reader to InputStream
Summing Numbers with Java Streams
Java Program to Represent Linear Equations in Matrix Form
A Guide to the finalize Method in Java
Java Program to Implement LinkedHashSet API
A Guide to Queries in Spring Data MongoDB
Spring Security Form Login