Tarjan’s algorithm is a graph algorithm that finds strongly connected components (SCCs) in a directed graph. A strongly connected component is a subset of nodes in a graph where every node is reachable from every other node in the subset.
The algorithm works by performing a depth-first search on the graph, maintaining a stack of visited nodes and a set of nodes that have been visited but not yet added to a strongly connected component. As the algorithm traverses the graph, it assigns a unique index to each node and keeps track of the lowest index of any node that can be reached from the current node (called the “low link” value). When the algorithm finishes visiting a node and its descendants, it checks whether the node is the root of a strongly connected component by comparing its low link value to the index of the node on the top of the stack.
Tarjan’s algorithm has a time complexity of O(V+E), where V is the number of nodes in the graph and E is the number of edges. It is considered one of the most efficient algorithms for finding strongly connected components in a graph.
Tarjan’s algorithm is commonly used in applications where we need to identify groups of related nodes in a graph, such as in the analysis of social networks, compiler design, and scheduling algorithms.
import java.util.Stack
class TarjanSCC(private val adjacencyList: List<List<Int>>) {
private val stack = Stack<Int>()
private val onStack = BooleanArray(adjacencyList.size)
private val lowLinkValues = IntArray(adjacencyList.size) { -1 }
private val indexValues = IntArray(adjacencyList.size) { -1 }
private val sccs = mutableListOf<MutableList<Int>>()
private var index = 0
fun findSCCs(): List<List<Int>> {
for (v in adjacencyList.indices) {
if (indexValues[v] == -1) {
tarjan(v)
}
}
return sccs
}
private fun tarjan(v: Int) {
indexValues[v] = index
lowLinkValues[v] = index
index++
stack.push(v)
onStack[v] = true
for (w in adjacencyList[v]) {
if (indexValues[w] == -1) {
tarjan(w)
lowLinkValues[v] = Math.min(lowLinkValues[v], lowLinkValues[w])
} else if (onStack[w]) {
lowLinkValues[v] = Math.min(lowLinkValues[v], indexValues[w])
}
}
if (lowLinkValues[v] == indexValues[v]) {
val scc = mutableListOf<Int>()
var w: Int
do {
w = stack.pop()
onStack[w] = false
scc.add(w)
} while (w != v)
sccs.add(scc)
}
}
}In this code, the TarjanSCC class represents an instance of Tarjan’s algorithm. The constructor takes an adjacency list as input, which is a list of lists representing the directed edges in the graph. The findSCCs() function runs the algorithm and returns a list of strongly connected components.
findSCCs(): This is the main function that is used to find all strongly connected components in the graph. It initializes the necessary arrays and data structures, and then calls thetarjan()function for each unvisited vertex in the graph. Finally, it returns the list of strongly connected components that were found.tarjan(v: Int): This is the recursive function that implements Tarjan’s algorithm. It takes an input vertexv, and performs a depth-first search (DFS) traversal of the graph from that vertex. During the traversal, it keeps track of various properties of the vertices, such as their index value, low-link value, and whether they are on the stack. If it finds a strongly connected component, it adds it to thesccslist.stack: This is aStackobject that is used to keep track of the vertices that are currently on the DFS stack.onStack: This is aBooleanArraythat keeps track of whether a vertex is currently on the DFS stack.lowLinkValues: This is anIntArraythat stores the low-link value of each vertex. The low-link value of a vertex is the smallest index of any vertex that is reachable from that vertex (including itself) via a back edge.indexValues: This is anIntArraythat stores the index value of each vertex. The index value of a vertex is the order in which it was visited during the DFS traversal.sccs: This is aMutableListof strongly connected components that have been found so far.index: This is a counter variable that is used to assign index values to vertices during the DFS traversal.
Here is a complete code with example :
import java.util.Stack
class TarjanSCC(private val adjacencyList: List<List<Int>>) {
private val stack = Stack<Int>()
private val onStack = BooleanArray(adjacencyList.size)
private val lowLinkValues = IntArray(adjacencyList.size) { -1 }
private val indexValues = IntArray(adjacencyList.size) { -1 }
private val sccs = mutableListOf<MutableList<Int>>()
private var index = 0
fun findSCCs(): List<List<Int>> {
for (v in adjacencyList.indices) {
if (indexValues[v] == -1) {
tarjan(v)
}
}
return sccs
}
private fun tarjan(v: Int) {
indexValues[v] = index
lowLinkValues[v] = index
index++
stack.push(v)
onStack[v] = true
for (w in adjacencyList[v]) {
if (indexValues[w] == -1) {
tarjan(w)
lowLinkValues[v] = Math.min(lowLinkValues[v], lowLinkValues[w])
} else if (onStack[w]) {
lowLinkValues[v] = Math.min(lowLinkValues[v], indexValues[w])
}
}
if (lowLinkValues[v] == indexValues[v]) {
val scc = mutableListOf<Int>()
var w: Int
do {
w = stack.pop()
onStack[w] = false
scc.add(w)
} while (w != v)
sccs.add(scc)
}
}
}
fun main() {
// Example graph
val adjacencyList = listOf(
listOf(1),
listOf(2, 3),
listOf(0, 4),
listOf(4),
listOf(3),
listOf(6),
listOf(5)
)
val tarjan = TarjanSCC(adjacencyList)
val sccs = tarjan.findSCCs()
println("Strongly connected components:")
sccs.forEach { println(it) }
}In the main() function, we create an example adjacency list representing a directed graph and pass it to a TarjanSCC instance. We then call findSCCs() to find the strongly connected components in the graph and print them out.
Output :
Strongly connected components: [3, 4] [2, 1, 0] [6, 5]