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:
Implementing a Binary Tree in Java
Java Program to Implement Naor-Reingold Pseudo Random Function
Kết hợp Java Reflection và Java Annotations
Guide to UUID in Java
Java Program to Find All Pairs Shortest Path
Converting String to Stream of chars
Daemon Threads in Java
TreeSet và sử dụng Comparable, Comparator trong java
Introduction to Spring Boot CLI
Marker Interface trong Java
Java Program to Implement Skip List
A Guide to Iterator in Java
Java Program to Implement Hash Tables Chaining with List Heads
Java Program to Perform Postorder Recursive Traversal of a Given Binary Tree
JUnit 5 for Kotlin Developers
Spring Boot - Flyway Database
Java Program to Find the Nearest Neighbor Using K-D Tree Search
Java Program to Implement Circular Singly Linked List
Từ khóa this và super trong Java
Java 8 StringJoiner
Java Program to Find the GCD and LCM of two Numbers
A Guide to Java HashMap
Java Program to Find the Peak Element of an Array O(n) time (Naive Method)
Sử dụng CountDownLatch trong Java
Prevent Brute Force Authentication Attempts with Spring Security
Java Program to Represent Graph Using Incidence List
Java Program to Implement Graph Coloring Algorithm
How to Read HTTP Headers in Spring REST Controllers
Java Perform to a 2D FFT Inplace Given a Complex 2D Array
Composition, Aggregation, and Association in Java
Java Program to Apply DFS to Perform the Topological Sorting of a Directed Acyclic Graph
JUnit5 @RunWith