Java Program to Implement Find all Cross Edges in a Graph

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 Sorted Circular Doubly Linked List
Java Program to Implement Solovay Strassen Primality Test Algorithm
Spring @RequestParam Annotation
Java Program to Compute the Volume of a Tetrahedron Using Determinants
OAuth2 for a Spring REST API – Handle the Refresh Token in Angular
Java Program to Compare Binary and Sequential Search
Merging Two Maps with Java 8
Hướng dẫn sử dụng lớp Console trong java
Spring REST API + OAuth2 + Angular
Guide to the Volatile Keyword in Java
Java Program to Perform Right Rotation on a Binary Search Tree
List Interface trong Java
Hướng dẫn sử dụng luồng vào ra ký tự trong Java
Java Program to Perform Preorder Recursive Traversal of a Given Binary Tree
Java Program to Implement Randomized Binary Search Tree
Error Handling for REST with Spring
Java Program to Implement Hash Trie
Java Program to Implement LinkedBlockingQueue API
JUnit5 @RunWith
Java Program to Implement CountMinSketch
Java Program for Topological Sorting in Graphs
Quản lý bộ nhớ trong Java với Heap Space vs Stack
Filtering a Stream of Optionals in Java
Tạo ứng dụng Java RESTful Client với thư viện OkHttp
Jackson vs Gson
CyclicBarrier in Java
Xử lý ngoại lệ đối với trường hợp ghi đè phương thức trong java
Java Program to Implement LinkedList API
Java Program to Generate All Subsets of a Given Set in the Gray Code Order
HttpClient Connection Management
The Spring @Controller and @RestController Annotations
Interface trong Java 8 – Default method và Static method