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 Generate Date Between Given Range
Java 8 Predicate Chain
Spring Security OAuth2 – Simple Token Revocation
Java Program to Implement Selection Sort
Java Program to Generate All Possible Combinations of a Given List of Numbers
Tránh lỗi ConcurrentModificationException trong Java như thế nào?
Spring Boot - Creating Docker Image
Hướng dẫn Java Design Pattern – Dependency Injection
Hướng dẫn kết nối cơ sở dữ liệu với Java JDBC
Checked and Unchecked Exceptions in Java
Giới thiệu Google Guice – Dependency injection (DI) framework
Build a REST API with Spring and Java Config
Jackson Exceptions – Problems and Solutions
Guide to CountDownLatch in Java
Java Program to Implement the Binary Counting Method to Generate Subsets of a Set
Java Program to Represent Graph Using Incidence List
Spring Cloud AWS – RDS
Java Program to Perform Quick Sort on Large Number of Elements
New Features in Java 15
Java Map With Case-Insensitive Keys
A Guide to Concurrent Queues in Java
Debug a JavaMail Program
Hướng dẫn Java Design Pattern – Prototype
Guide to the Volatile Keyword in Java
Simple Single Sign-On with Spring Security OAuth2
Guide To CompletableFuture
Spring MVC Content Negotiation
New Features in Java 11
Feign – Tạo ứng dụng Java RESTful Client
Java Program to Implement Sorted Doubly Linked List
Java Switch Statement
More Jackson Annotations