This is a Java Program to Implement Gabow Algorithm. Gabow algorithm is used for finding all strongly connected components in a graph.
Here is the source code of the Java Program to Implement Gabow Algorithm. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.
/** * Java Program to Implement Gabow Algorithm **/ import java.util.*; /** class Gabow **/ class Gabow { /** number of vertices **/ private int V; /** preorder number counter **/ private int preCount; private int[] preorder; /** to check if v is visited **/ private boolean[] visited; /** check strong componenet containing v **/ private boolean[] chk; /** to store given graph **/ private List<Integer>[] graph; /** to store all scc **/ private List<List<Integer>> sccComp; private Stack<Integer> stack1; private Stack<Integer> stack2; /** function to get all strongly connected components **/ public List<List<Integer>> getSCComponents(List<Integer>[] graph) { V = graph.length; this.graph = graph; preorder = new int[V]; chk = new boolean[V]; visited = new boolean[V]; stack1 = new Stack<Integer>(); stack2 = 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) { preorder[v] = preCount++; visited[v] = true; stack1.push(v); stack2.push(v); for (int w : graph[v]) { if (!visited[w]) dfs(w); else if (!chk[w]) while (preorder[stack2.peek()] > preorder[w]) stack2.pop(); } if (stack2.peek() == v) { stack2.pop(); List<Integer> component = new ArrayList<Integer>(); int w; do { w = stack1.pop(); component.add(w); chk[w] = true; } while (w != v); sccComp.add(component); } } /** main **/ public static void main(String[] args) { Scanner scan = new Scanner(System.in); System.out.println("Gabow 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); } Gabow gab = new Gabow(); System.out.println("\nSCC : "); /** print all strongly connected components **/ List<List<Integer>> scComponents = gab.getSCComponents(g); System.out.println(scComponents); } }
Gabow 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:
Guide to the Java ArrayList
LinkedList trong java
Java Program to Find the Edge Connectivity of a Graph
Java program to Implement Tree Set
Comparing Strings in Java
Hướng dẫn Java Design Pattern – Visitor
Control Structures in Java
Lập trình đa luồng với Callable và Future trong Java
Spring 5 WebClient
Java Program to Implement Sorted Circular Doubly Linked List
Check If a File or Directory Exists in Java
Generate Spring Boot REST Client with Swagger
Java Program to Implement Sorted List
Fixing 401s with CORS Preflights and Spring Security
How to Set TLS Version in Apache HttpClient
Giới thiệu Google Guice – Aspect Oriented Programming (AOP)
Java Program to Implement Euler Circuit Problem
The Difference Between map() and flatMap()
Spring Autowiring of Generic Types
Java Program to Solve the Fractional Knapsack Problem
Java Program to Implement Adjacency Matrix
Xử lý ngoại lệ trong Java (Exception Handling)
Lập trình mạng với java
Java Program to Search Number Using Divide and Conquer with the Aid of Fibonacci Numbers
Java Program to find the maximum subarray sum using Binary Search approach
Using Spring ResponseEntity to Manipulate the HTTP Response
Serialize Only Fields that meet a Custom Criteria with Jackson
Connect through a Proxy
Reactive WebSockets with Spring 5
Java Switch Statement
Java Program to Implement Fibonacci Heap
How to Get a Name of a Method Being Executed?