This is a Java Program to Implement Tarjan Algorithm. Tarjan Algorithm is used for finding all strongly connected components in a graph.
Here is the source code of the Java Program to Implement Tarjan Algorithm. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.
/** * Java Program to Implement Tarjan Algorithm **/ import java.util.*; /** class Tarjan **/ class Tarjan { /** number of vertices **/ private int V; /** preorder number counter **/ private int preCount; /** low number of v **/ private int[] low; /** to check if v is visited **/ private boolean[] visited; /** to store given graph **/ private List<Integer>[] graph; /** to store all scc **/ private List<List<Integer>> sccComp; private Stack<Integer> stack; /** function to get all strongly connected components **/ public List<List<Integer>> getSCComponents(List<Integer>[] graph) { V = graph.length; this.graph = graph; low = new int[V]; visited = new boolean[V]; stack = new Stack<Integer>(); sccComp = new ArrayList<>(); for (int v = 0; v < V; v++) if (!visited[v]) dfs(v); return sccComp; } /** function dfs **/ public void dfs(int v) { low[v] = preCount++; visited[v] = true; stack.push(v); int min = low[v]; for (int w : graph[v]) { if (!visited[w]) dfs(w); if (low[w] < min) min = low[w]; } if (min < low[v]) { low[v] = min; return; } List<Integer> component = new ArrayList<Integer>(); int w; do { w = stack.pop(); component.add(w); low[w] = V; } while (w != v); sccComp.add(component); } /** main **/ public static void main(String[] args) { Scanner scan = new Scanner(System.in); System.out.println("Tarjan algorithm Test\n"); System.out.println("Enter number of Vertices"); /** number of vertices **/ int V = scan.nextInt(); /** make graph **/ List<Integer>[] g = new List[V]; for (int i = 0; i < V; i++) g[i] = new ArrayList<Integer>(); /** accpet all edges **/ System.out.println("\nEnter number of edges"); int E = scan.nextInt(); /** all edges **/ System.out.println("Enter "+ E +" x, y coordinates"); for (int i = 0; i < E; i++) { int x = scan.nextInt(); int y = scan.nextInt(); g[x].add(y); } Tarjan t = new Tarjan(); System.out.println("\nSCC : "); /** print all strongly connected components **/ List<List<Integer>> scComponents = t.getSCComponents(g); System.out.println(scComponents); } }
Tarjan algorithm Test Enter number of Vertices 8 Enter number of edges 14 Enter 14 x, y coordinates 0 1 1 2 2 3 3 2 3 7 7 3 2 6 7 6 5 6 6 5 1 5 4 5 4 0 1 4 SCC : [[5, 6], [7, 3, 2], [4, 1, 0]]
Related posts:
Java Program to Perform the Shaker Sort
Java Program to Implement Extended Euclid Algorithm
Spring Boot: Customize Whitelabel Error Page
Java Program to Perform Encoding of a Message Using Matrix Multiplication
Guide To CompletableFuture
Java Program to Represent Graph Using Adjacency List
Java Optional as Return Type
New Features in Java 8
Java Program to Perform Addition Operation Using Bitwise Operators
Sending Emails with Java
Java Program to Implement Knapsack Algorithm
Implementing a Binary Tree in Java
Partition a List in Java
Java Program to Implement the Hungarian Algorithm for Bipartite Matching
Java NIO2 Path API
Spring RequestMapping
New Features in Java 13
Java Program to Delete a Particular Node in a Tree Without Using Recursion
Java Program to Check if it is a Sparse Matrix
wait() and notify() Methods in Java
Java 8 Streams peek() API
Guide to the Java Queue Interface
How to Find an Element in a List with Java
Exploring the New Spring Cloud Gateway
Creating a Web Application with Spring 5
Java Program to Generate a Sequence of N Characters for a Given Specific Case
Introduction to Spring Data REST
Toán tử trong java
Converting a List to String in Java
Handle EML file with JavaMail
Spring Boot - Servlet Filter
Spring Boot - Database Handling