Skip to content

Commit 69a4284

Browse files
shivu2002ashivu2002a
authored
Add Tarjans Algorithm (#3874)
1 parent a584ca2 commit 69a4284

File tree

2 files changed

+210
-0
lines changed

2 files changed

+210
-0
lines changed

‎src/main/java/com/thealgorithms/datastructures/graphs/TarjansAlgorithm.java

Lines changed: 138 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,138 @@
1+
package com.thealgorithms.datastructures.graphs;
2+
3+
import java.util.ArrayList;
4+
import java.util.Iterator;
5+
import java.util.List;
6+
import java.util.Stack;
7+
8+
/**
9+
* Java program that implements Tarjan's Algorithm.
10+
* @author Shivanagouda S A (https://github.com/shivu2002a)
11+
*
12+
*/
13+
14+
/**
15+
* Tarjan's algorithm is a linear time algorithm to find the strongly connected components of a
16+
directed graph, which, from here onwards will be referred as SCC.
17+
18+
* A graph is said to be strongly connected if every vertex is reachable from every other vertex.
19+
The SCCs of a directed graph form a partition into subgraphs that are themselves strongly connected.
20+
Single node is always a SCC.
21+
22+
* Example:
23+
0 --------> 1 -------> 3 --------> 4
24+
^ /
25+
| /
26+
| /
27+
| /
28+
| /
29+
| /
30+
| /
31+
| /
32+
| /
33+
| /
34+
|V
35+
2
36+
37+
For the above graph, the SCC list goes as follows:
38+
1, 2, 0
39+
3
40+
4
41+
42+
We can also see that order of the nodes in an SCC doesn't matter since they are in cycle.
43+
44+
{@summary}
45+
Tarjan's Algorithm:
46+
* DFS search produces a DFS tree
47+
* Strongly Connected Components form subtrees of the DFS tree.
48+
* If we can find the head of these subtrees, we can get all the nodes in that subtree (including the head)
49+
and that will be one SCC.
50+
* There is no back edge from one SCC to another (here can be cross edges, but they will not be used).
51+
52+
* Kosaraju Algorithm aims at doing the same but uses two DFS traversalse whereas Tarjan’s algorithm does
53+
the same in a single DFS, which leads to much lower constant factors in the latter.
54+
55+
*/
56+
public class TarjansAlgorithm {
57+
58+
//Timer for tracking lowtime and insertion time
59+
private int Time;
60+
61+
private List<List<Integer>> SCClist = new ArrayList<List<Integer>>();
62+
63+
public List<List<Integer>> stronglyConnectedComponents(int V, List<List<Integer>> graph) {
64+
65+
// Initially all vertices as unvisited, insertion and low time are undefined
66+
67+
// insertionTime:Time when a node is visited 1st time while DFS traversal
68+
69+
// lowTime: indicates the earliest visited vertex (the vertex with minimum insertion time) that can
70+
// be reached from a subtree rooted with a particular node.
71+
int lowTime[] = new int[V];
72+
int insertionTime[] = new int[V];
73+
for (int i = 0; i < V; i++) {
74+
insertionTime[i] = -1;
75+
lowTime[i] = -1;
76+
}
77+
78+
// To check if element is present in stack
79+
boolean isInStack[] = new boolean[V];
80+
81+
// Store nodes during DFS
82+
Stack<Integer> st = new Stack<Integer>();
83+
84+
for (int i = 0; i < V; i++) {
85+
if (insertionTime[i] == -1)
86+
stronglyConnCompsUtil(i, lowTime, insertionTime, isInStack, st, graph);
87+
}
88+
89+
return SCClist;
90+
}
91+
92+
private void stronglyConnCompsUtil(int u, int lowTime[], int insertionTime[],
93+
boolean isInStack[], Stack<Integer> st, List<List<Integer>> graph) {
94+
95+
// Initialize insertion time and lowTime value of current node
96+
insertionTime[u] = Time;
97+
lowTime[u] = Time;
98+
Time += 1;
99+
100+
//Push current node into stack
101+
isInStack[u] = true;
102+
st.push(u);
103+
104+
int n;
105+
106+
// Go through all vertices adjacent to this
107+
Iterator<Integer> i = graph.get(u).iterator();
108+
109+
while (i.hasNext()) {
110+
n = i.next();
111+
112+
//If the adjacent node is unvisited, do DFS
113+
if (insertionTime[n] == -1) {
114+
stronglyConnCompsUtil(n, lowTime, insertionTime, isInStack, st, graph);
115+
//update lowTime for the current node comparing lowtime of adj node
116+
lowTime[u] = Math.min(lowTime[u], lowTime[n]);
117+
} else if (isInStack[n] == true) {
118+
//If adj node is in stack, update low
119+
lowTime[u] = Math.min(lowTime[u], insertionTime[n]);
120+
}
121+
}
122+
//If lowtime and insertion time are same, current node is the head of an SCC
123+
// head node found, get all the nodes in this SCC
124+
if (lowTime[u] == insertionTime[u]) {
125+
int w = -1;
126+
var scc = new ArrayList<Integer>();
127+
128+
//Stack has all the nodes of the current SCC
129+
while (w != u) {
130+
w = st.pop();
131+
scc.add(w);
132+
isInStack[w] = false;
133+
}
134+
SCClist.add(scc);
135+
}
136+
}
137+
138+
}

‎src/test/java/com/thealgorithms/datastructures/graphs/TarjansAlgorithmTest.java

Lines changed: 72 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,72 @@
1+
package com.thealgorithms.datastructures.graphs;
2+
3+
import static org.junit.jupiter.api.Assertions.assertTrue;
4+
5+
import java.util.ArrayList;
6+
import java.util.Arrays;
7+
import java.util.List;
8+
9+
import org.junit.jupiter.api.Test;
10+
11+
public class TarjansAlgorithmTest {
12+
13+
TarjansAlgorithm tarjansAlgo = new TarjansAlgorithm();
14+
15+
@Test
16+
public void findStronglyConnectedComps(){
17+
var v = 5;
18+
var graph = new ArrayList<List<Integer>>();
19+
for (int i = 0; i < v; i++) {
20+
graph.add(new ArrayList<>());
21+
}
22+
graph.get(0).add(1);
23+
graph.get(1).add(2);
24+
graph.get(2).add(0);
25+
graph.get(1).add(3);
26+
graph.get(3).add(4);
27+
28+
var actualResult = tarjansAlgo.stronglyConnectedComponents(v, graph);
29+
/*
30+
Expected result:
31+
0, 1, 2
32+
3
33+
4
34+
*/
35+
List<List<Integer>> expectedResult = new ArrayList<>();
36+
37+
expectedResult.add(Arrays.asList(4));
38+
expectedResult.add(Arrays.asList(3));
39+
expectedResult.add(Arrays.asList(2, 1, 0));
40+
assertTrue(expectedResult.equals(actualResult));
41+
}
42+
43+
@Test
44+
public void findStronglyConnectedCompsShouldGetSingleNodes() {
45+
//Create a adjacency list of graph
46+
var n = 8;
47+
var adjList = new ArrayList<List<Integer>>(n);
48+
49+
for (int i = 0; i < n; i++) {
50+
adjList.add(new ArrayList<>());
51+
}
52+
53+
adjList.get(0).add(1);
54+
adjList.get(1).add(2);
55+
adjList.get(2).add(3);
56+
adjList.get(3).add(4);
57+
adjList.get(4).add(5);
58+
adjList.get(5).add(6);
59+
adjList.get(6).add(7);
60+
adjList.get(7).add(0);
61+
62+
List<List<Integer>> actualResult = tarjansAlgo.stronglyConnectedComponents(n, adjList);
63+
List<List<Integer>> expectedResult = new ArrayList<>();
64+
/*
65+
Expected result:
66+
7, 6, 5, 4, 3, 2, 1, 0
67+
*/
68+
expectedResult.add(Arrays.asList(7, 6, 5, 4, 3, 2, 1, 0));
69+
assertTrue(expectedResult.equals(actualResult));
70+
}
71+
72+
}

0 commit comments

Comments
 (0)