Kosaraju’s algorithm is a linear time algorithm for finding all strongly connected components (SCCs) in a directed graph. The algorithm was developed by S. Rao Kosaraju in 1978, and it is widely used due to its simplicity and efficiency.
The algorithm works by performing two depth-first searches (DFS) on the graph. First, it performs a DFS on the graph to compute the finishing times of all vertices. Then, it reverses the graph and performs another DFS on the reversed graph, starting from the vertex with the highest finishing time. This second DFS identifies all vertices in the same SCC as the starting vertex.
The algorithm uses two main data structures: a stack to keep track of vertices during the DFS traversal, and a boolean array to keep track of which vertices have already been visited. By performing the two DFS traversals, the algorithm efficiently finds all strongly connected components in the graph.
Overall, Kosaraju’s algorithm is an efficient and simple algorithm for finding strongly connected components in a directed graph. Its linear time complexity makes it well-suited for large graphs.
import java.util.Stack
class KosarajuSCC(private val graph: List<List<Int>>) {
fun findSCCs(): List<List<Int>> {
val n = graph.size
val visited = BooleanArray(n) { false }
val stack = Stack<Int>()
val sccs = mutableListOf<List<Int>>()
// First DFS traversal to compute finishing times
for (v in 0 until n) {
if (!visited[v]) {
dfs1(v, visited, stack)
}
}
// Reverse the graph
val reversedGraph = Array(n) { mutableListOf<Int>() }
for (v in 0 until n) {
for (w in graph[v]) {
reversedGraph[w].add(v)
}
}
// Second DFS traversal to find SCCs
visited.fill(false)
while (!stack.isEmpty()) {
val v = stack.pop()
if (!visited[v]) {
val scc = mutableListOf<Int>()
dfs2(v, visited, reversedGraph, scc)
sccs.add(scc)
}
}
return sccs
}
private fun dfs1(v: Int, visited: BooleanArray, stack: Stack<Int>) {
visited[v] = true
for (w in graph[v]) {
if (!visited[w]) {
dfs1(w, visited, stack)
}
}
stack.push(v)
}
private fun dfs2(v: Int, visited: BooleanArray, graph: Array<MutableList<Int>>, scc: MutableList<Int>) {
visited[v] = true
scc.add(v)
for (w in graph[v]) {
if (!visited[w]) {
dfs2(w, visited, graph, scc)
}
}
}
}The KosarajuSCC class takes a directed graph represented as a list of adjacency lists, where each element in the list represents a vertex and its adjacent vertices. The findSCCs() function returns a list of lists, where each inner list represents a strongly connected component in the graph.
The algorithm uses two DFS traversals. The first DFS traversal computes the finishing times of each vertex and pushes them onto a stack. The second DFS traversal starts at the vertex with the highest finishing time and identifies all vertices in the same SCC as that vertex.
The dfs1() function performs the first DFS traversal, while the dfs2() function performs the second DFS traversal. The stack is used to keep track of the vertices in the order of their finishing times. The reversedGraph is a reversed version of the original graph, which is used in the second DFS traversal. The visited array keeps track of which vertices have already been visited during the DFS traversal.
Overall, this Kotlin implementation of Kosaraju’s algorithm is an efficient way to find strongly connected components in a directed graph.
import java.util.Stack
class KosarajuSCC(private val graph: List<List<Int>>) {
fun findSCCs(): List<List<Int>> {
val n = graph.size
val visited = BooleanArray(n) { false }
val stack = Stack<Int>()
val sccs = mutableListOf<List<Int>>()
// First DFS traversal to compute finishing times
for (v in 0 until n) {
if (!visited[v]) {
dfs1(v, visited, stack)
}
}
// Reverse the graph
val reversedGraph = Array(n) { mutableListOf<Int>() }
for (v in 0 until n) {
for (w in graph[v]) {
reversedGraph[w].add(v)
}
}
// Second DFS traversal to find SCCs
visited.fill(false)
while (!stack.isEmpty()) {
val v = stack.pop()
if (!visited[v]) {
val scc = mutableListOf<Int>()
dfs2(v, visited, reversedGraph, scc)
sccs.add(scc)
}
}
return sccs
}
private fun dfs1(v: Int, visited: BooleanArray, stack: Stack<Int>) {
visited[v] = true
for (w in graph[v]) {
if (!visited[w]) {
dfs1(w, visited, stack)
}
}
stack.push(v)
}
private fun dfs2(v: Int, visited: BooleanArray, graph: Array<MutableList<Int>>, scc: MutableList<Int>) {
visited[v] = true
scc.add(v)
for (w in graph[v]) {
if (!visited[w]) {
dfs2(w, visited, graph, scc)
}
}
}
}
fun main() {
val graph = listOf(
listOf(1, 2), // vertex 0
listOf(2), // vertex 1
listOf(0, 3), // vertex 2
listOf(4), // vertex 3
listOf(3) // vertex 4
)
val kosaraju = KosarajuSCC(graph)
val sccs = kosaraju.findSCCs()
println("Strongly Connected Components:")
for (scc in sccs) {
println(scc.joinToString())
}
}In this example, we create a directed graph represented as a list of adjacency lists, where each element in the list represents a vertex and its adjacent vertices. We then create a KosarajuSCC object with the graph and use its findSCCs() function to find the strongly connected components in the graph. Finally, we print out the strongly connected components to the console.
Output :
Strongly Connected Components: 0, 2, 1 & 3, 4