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:
Hướng dẫn Java Design Pattern – Interpreter
Introduction to Using FreeMarker in Spring MVC
How to Replace Many if Statements in Java
Introduction to Spring Cloud OpenFeign
Java Copy Constructor
Guide to Java 8 groupingBy Collector
Guide to Java 8’s Collectors
Hướng dẫn sử dụng Java Annotation
Vòng lặp for, while, do-while trong Java
Graph Data Stucture
A Custom Media Type for a Spring REST API
The Difference Between Collection.stream().forEach() and Collection.forEach()
Java Program to Solve Travelling Salesman Problem for Unweighted Graph
Java Program to Create a Minimal Set of All Edges Whose Addition will Convert it to a Strongly Conne...
Java 8 – Powerful Comparison with Lambdas
Remove the First Element from a List
Spring Boot - Apache Kafka
Overview of the java.util.concurrent
Quick Guide to @RestClientTest in Spring Boot
Java Program to Perform String Matching Using String Library
Removing all Nulls from a List in Java
Java Program to Implement HashTable API
String Joiner trong Java 8
How to Kill a Java Thread
Enum trong java
Java Program to Perform Postorder Non-Recursive Traversal of a Given Binary Tree
New Features in Java 11
Java Program to implement Array Deque
Giới thiệu Java Service Provider Interface (SPI) – Tạo các ứng dụng Java dễ mở rộng
Spring Autowiring of Generic Types
Java Program to Implement Word Wrap Problem
Java Program to Implement Stein GCD Algorithm