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:
HttpClient Timeout
Spring Boot Tutorial – Bootstrap a Simple Application
Mix plain text and HTML content in a mail
Java – Generate Random String
Java Program to Search for an Element in a Binary Search Tree
Jackson Date
Java Program to Generate All Subsets of a Given Set in the Gray Code Order
Getting a File’s Mime Type in Java
Quick Guide to Spring MVC with Velocity
HttpClient 4 – Follow Redirects for POST
Java Program for Douglas-Peucker Algorithm Implementation
An Intro to Spring Cloud Security
Debugging Reactive Streams in Java
The DAO with JPA and Spring
Spring Boot Change Context Path
Java Program to Implement Sorted List
Java Program to Print the Kind of Rotation the AVL Tree is Undergoing
Java Program to Implement LinkedList API
Java String to InputStream
Spring Data MongoDB – Indexes, Annotations and Converters
Migrating from JUnit 4 to JUnit 5
How to Kill a Java Thread
Using Java Assertions
Converting Iterator to List
Java Program to Implement Double Ended Queue
Base64 encoding và decoding trong Java 8
Rest Web service: Filter và Interceptor với Jersey 2.x (P2)
Java Program to Implement Slicker Algorithm that avoids Triangulation to Find Area of a Polygon
A Guide to JPA with Spring
Java Program to Implement Queue using Linked List
Spring Security Authentication Provider
Convert Hex to ASCII in Java