# Java Program to Implement Gabow Algorithm

«
»
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.

1. `/**`
2. ` *     Java Program to Implement Gabow Algorithm`
3. ` **/`
4. ` `
5. `import java.util.*;`
6. ` `
7. `/** class Gabow **/`
8. `class Gabow`
9. `{`
10. `    /** number of vertices **/`
11. `    private int V;    `
12. `    /** preorder number counter **/`
13. `    private int preCount;`
14. `    private int[] preorder;`
15. `    /** to check if v is visited **/`
16. `    private boolean[] visited;  `
17. `    /** check strong componenet containing v **/`
18. `    private boolean[] chk;    `
19. `    /** to store given graph **/`
20. `    private List<Integer>[] graph;`
21. `    /** to store all scc **/`
22. `    private List<List<Integer>> sccComp;`
23. `    private Stack<Integer> stack1;`
24. `    private Stack<Integer> stack2;`
25. ` `
26. `    /** function to get all strongly connected components **/`
27. `    public List<List<Integer>> getSCComponents(List<Integer>[] graph) `
28. `    {`
29. `        V = graph.length;`
30. `        this.graph = graph;`
31. `        preorder = new int[V];`
32. `        chk = new boolean[V]; `
33. `        visited = new boolean[V];`
34. `        stack1 = new Stack<Integer>();`
35. `        stack2 = new Stack<Integer>();`
36. `        sccComp = new ArrayList<>();`
37. ` `
38. `        for (int v = 0; v < V; v++)`
39. `              if (!visited[v])`
40. `                dfs(v);`
41. ` `
42. `        return sccComp;`
43. `      }`
44. `    /** function dfs **/`
45. `    public void dfs(int v) `
46. `    {`
47. `        preorder[v] = preCount++;`
48. `        visited[v] = true;`
49. `        stack1.push(v);`
50. `        stack2.push(v);`
51. ` `
52. `        for (int w : graph[v]) `
53. `        {`
54. `            if (!visited[w])`
55. `                dfs(w);`
56. `            else if (!chk[w]) `
57. `                while (preorder[stack2.peek()] > preorder[w])`
58. `                    stack2.pop();            `
59. `        }`
60. `        if (stack2.peek() == v) `
61. `        {`
62. `            stack2.pop();`
63. `            List<Integer> component = new ArrayList<Integer>();`
64. `            int w;`
65. `            do `
66. `            {`
67. `                w = stack1.pop();`
68. `                component.add(w);`
69. `                chk[w] = true;`
70. `            } while (w != v);  `
71. `            sccComp.add(component);            `
72. `        }                       `
73. `    }    `
74. `    /** main **/`
75. `    public static void main(String[] args)`
76. `    {`
77. `        Scanner scan = new Scanner(System.in);`
78. `        System.out.println("Gabow algorithm Test\n");`
79. `        System.out.println("Enter number of Vertices");`
80. `        /** number of vertices **/`
81. `        int V = scan.nextInt();`
82. ` `
83. `        /** make graph **/`
84. `        List<Integer>[] g = new List[V];        `
85. `        for (int i = 0; i < V; i++)`
86. `            g[i] = new ArrayList<Integer>();        `
87. `        /** accpet all edges **/`
88. `        System.out.println("\nEnter number of edges");`
89. `        int E = scan.nextInt();`
90. `        /** all edges **/`
91. `        System.out.println("Enter "+ E +" x, y coordinates");`
92. `        for (int i = 0; i < E; i++)`
93. `        {`
94. `            int x = scan.nextInt();`
95. `            int y = scan.nextInt();`
96. `            g[x].add(y);`
97. `        }    `
98. ` `
99. `        Gabow gab = new Gabow();        `
100. `        System.out.println("\nSCC : ");`
101. `        /** print all strongly connected components **/`
102. `        List<List<Integer>> scComponents = gab.getSCComponents(g);`
103. `        System.out.println(scComponents);        `
104. `    }    `
105. `}`

```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]]```

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now! 