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:
Hướng dẫn Java Design Pattern – Builder
Java Program to Implement Vector API
OAuth2.0 and Dynamic Client Registration
Java Program to Implement Sorting of Less than 100 Numbers in O(n) Complexity
Java Web Services – JAX-WS – SOAP
Kết hợp Java Reflection và Java Annotations
Receive email using POP3
Comparing Arrays in Java
Hướng dẫn sử dụng lớp Console trong java
Configuring a DataSource Programmatically in Spring Boot
Guide to PriorityBlockingQueue in Java
Spring Boot - Batch Service
Java Program to Implement Attribute API
Java Program to Implement Kosaraju Algorithm
Jackson vs Gson
Luồng Daemon (Daemon Thread) trong Java
Giới thiệu Google Guice – Aspect Oriented Programming (AOP)
Java Program to Implement LinkedBlockingDeque API
Constructor Dependency Injection in Spring
Collect a Java Stream to an Immutable Collection
Generic Constructors in Java
HandlerAdapters in Spring MVC
Abstract class và Interface trong Java
Simple Single Sign-On with Spring Security OAuth2
Java Program to Perform Naive String Matching
Jackson – Marshall String to JsonNode
Custom Error Pages with Spring MVC
Guide to BufferedReader
Java Program to Implement WeakHashMap API
HashSet trong Java hoạt động như thế nào?
Connect through a Proxy
A Guide to Java 9 Modularity