TheAlgorithms · siriak · Feb 15, 2023 · Jan 17, 2023 · Feb 4, 2023 · Feb 4, 2023
@@ -0,0 +1,138 @@
+package com.thealgorithms.datastructures.graphs;
+
+import java.util.ArrayList;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Stack;
+
+/**
+ * Java program that implements Tarjan's Algorithm.
+ * @author Shivanagouda S A (https://github.com/shivu2002a)
+ * 
+ */
+
+/**
+ * Tarjan's algorithm is a linear time algorithm to find the strongly connected components of a 
+   directed graph, which, from here onwards will be referred as SCC. 
+
+ * A graph is said to be strongly connected if every vertex is reachable from every other vertex. 
+   The SCCs of a directed graph form a partition into subgraphs that are themselves strongly connected.
+   Single node is always a SCC.
+
+ * Example:
+    0 --------> 1 -------> 3 --------> 4
+    ^          /
+    |         /
+    |        /
+    |       /
+    |      /
+    |     /
+    |    /
+    |   /
+    |  /
+    | /
+    |V
+    2
+
+    For the above graph, the SCC list goes as follows:
+    1, 2, 0
+    3
+    4
+
+    We can also see that order of the nodes in an SCC doesn't matter since they are in cycle.
+
+ {@summary}
+    Tarjan's Algorithm: 
+    * DFS search produces a DFS tree 
+    * Strongly Connected Components form subtrees of the DFS tree. 
+    * If we can find the head of these subtrees, we can get all the nodes in that subtree (including the head)
+      and that will be one SCC. 
+    * There is no back edge from one SCC to another (here can be cross edges, but they will not be used).
+
+    * Kosaraju Algorithm aims at doing the same but uses two DFS traversalse whereas Tarjan’s algorithm does 
+      the same in a single DFS, which leads to much lower constant factors in the latter.
+
+ */
+public class TarjansAlgorithm {
+
+    //Timer for tracking lowtime and insertion time
+    private int Time;
+
+    private List<List<Integer>> SCClist = new ArrayList<List<Integer>>();
+
+    public List<List<Integer>> stronglyConnectedComponents(int V, List<List<Integer>> graph) {
+
+        // Initially all vertices as unvisited, insertion and low time are undefined
+
+        // insertionTime:Time when a node is visited 1st time while DFS traversal
+
+        // lowTime: indicates the earliest visited vertex (the vertex with minimum insertion time) that can 
+        // be reached from a subtree rooted with a particular node.
+        int lowTime[] = new int[V];
+        int insertionTime[] = new int[V];
+        for (int i = 0; i < V; i++) {
+            insertionTime[i] = -1;
+            lowTime[i] = -1;
+        }
+
+        // To check if element is present in stack
+        boolean isInStack[] = new boolean[V];
+
+        // Store nodes during DFS
+        Stack<Integer> st = new Stack<Integer>();
+
+        for (int i = 0; i < V; i++) {
+            if (insertionTime[i] == -1)
+                stronglyConnCompsUtil(i, lowTime, insertionTime, isInStack, st, graph);
+        }
+
+        return SCClist;
+    }
+
+    private void stronglyConnCompsUtil(int u, int lowTime[], int insertionTime[],
+            boolean isInStack[], Stack<Integer> st, List<List<Integer>> graph) {
+
+        // Initialize insertion time and lowTime value of current node
+        insertionTime[u] = Time;
+        lowTime[u] = Time;
+        Time += 1;
+
+        //Push current node into stack
+        isInStack[u] = true;
+        st.push(u);
+
+        int n;
+
+        // Go through all vertices adjacent to this
+        Iterator<Integer> i = graph.get(u).iterator();
+
+        while (i.hasNext()) {
+            n = i.next();
+
+            //If the adjacent node is unvisited, do DFS
+            if (insertionTime[n] == -1) {
+                stronglyConnCompsUtil(n, lowTime, insertionTime, isInStack, st, graph);
+                //update lowTime for the current node comparing lowtime of adj node
+                lowTime[u] = Math.min(lowTime[u], lowTime[n]);
+            } else if (isInStack[n] == true) {
+                //If adj node is in stack, update low 
+                lowTime[u] = Math.min(lowTime[u], insertionTime[n]);
+            }
+        }
+        //If lowtime and insertion time are same, current node is the head of an SCC
+        // head node found, get all the nodes in this SCC
+        if (lowTime[u] == insertionTime[u]) {
+            int w = -1;
+            var scc = new ArrayList<Integer>();
+
+            //Stack has all the nodes of the current SCC
+            while (w != u) {
+                w = st.pop();
+                scc.add(w);
+                isInStack[w] = false;
+            }
+            SCClist.add(scc);
+        }
+    }
+
+}
@@ -0,0 +1,72 @@
+package com.thealgorithms.datastructures.graphs;
+
+import static org.junit.jupiter.api.Assertions.assertTrue;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
+
+import org.junit.jupiter.api.Test;
+
+public class TarjansAlgorithmTest {
+
+    TarjansAlgorithm tarjansAlgo = new TarjansAlgorithm();
+
+    @Test
+    public void findStronglyConnectedComps(){
+        var v = 5;
+        var graph = new ArrayList<List<Integer>>();
+        for (int i = 0; i < v; i++) {
+            graph.add(new ArrayList<>());
+        }
+        graph.get(0).add(1);
+        graph.get(1).add(2);
+        graph.get(2).add(0);
+        graph.get(1).add(3);
+        graph.get(3).add(4);
+
+        var actualResult = tarjansAlgo.stronglyConnectedComponents(v, graph);
+        /*
+            Expected result: 
+            0, 1, 2
+            3
+            4 
+        */
+        List<List<Integer>> expectedResult = new ArrayList<>();
+
+        expectedResult.add(Arrays.asList(4));
+        expectedResult.add(Arrays.asList(3));
+        expectedResult.add(Arrays.asList(2, 1, 0));
+        assertTrue(expectedResult.equals(actualResult));
+    }
+
+    @Test
+    public void findStronglyConnectedCompsShouldGetSingleNodes() {
+        //Create a adjacency list of graph
+        var n = 8;
+        var adjList = new ArrayList<List<Integer>>(n);
+
+        for (int i = 0; i < n; i++) {
+            adjList.add(new ArrayList<>());
+        }
+
+        adjList.get(0).add(1);
+        adjList.get(1).add(2);
+        adjList.get(2).add(3);
+        adjList.get(3).add(4);
+        adjList.get(4).add(5);
+        adjList.get(5).add(6);
+        adjList.get(6).add(7);
+        adjList.get(7).add(0);
+
+        List<List<Integer>> actualResult = tarjansAlgo.stronglyConnectedComponents(n, adjList);
+        List<List<Integer>> expectedResult = new ArrayList<>();
+        /*
+            Expected result: 
+            7, 6, 5, 4, 3, 2, 1, 0
+        */
+        expectedResult.add(Arrays.asList(7, 6, 5, 4, 3, 2, 1, 0));
+        assertTrue(expectedResult.equals(actualResult));
+    }
+
+}