Tarjan's strongly connected components

Algorithms  #algorithms  #graphs 

Strongly connected components in a directed graph are self-contained cycles where every vertex in a given cycle can reach every other vertex in the same cycle.

Strongly connected components in a graph are unique.

Illustration

In the following illustration, all same color vertices are forming self-contained cycles

Low Link Value

A low link value of a node is the lowest id of a node reachable from that node (including itself) when doing a DFS.

Algorithm

1. Maintain a stack of currently visiting vertices.
2. Start depth-first-search (DFS), upon visiting a vertex, mark it as visited
3. On DFS callback, if previous vertex is on the stack, update its low-link value i.e. min(lowLink[vertex], lowLink[adjacentVertex])
4. After visiting all adjacent vertices of the current vertex, if current vertex started a connected component, pop all the vertices off the stack until current vertex is reached.

• The steps are illustrated for a sample graph below

Example

• The following script finds the strongly connected components in the graph given above

import java.util.*
import kotlin.math.min

fun main() {
    val adjacencyList = mutableListOf<List<Int>>().apply {
        add(0, listOf(2, 0))
        add(1, listOf(0))
        add(2, listOf(1))
        add(3, listOf(1, 2, 5))
        add(4, listOf(1, 3))
        add(5, listOf(4))
        add(6, listOf(4, 7))
        add(7, listOf(6, 5))
    }

    findStronglyConnectedComponents(adjacencyList).also {
        println("connected components: $it")
    }
}

//sampleStart
fun findStronglyConnectedComponents(adjacencyList: List<List<Int>>): List<List<Int>> {
    // click + to see full script
    // id value, this will be incremented for each vertex
    var id = 0
    val noOfVertices = adjacencyList.size
    val vertexIds = IntArray(noOfVertices)
    val lowLinkValues = IntArray(noOfVertices)

    // keeps tracks of a vertex either it is on stack or not
    val onStack = BooleanArray(noOfVertices)
    // stores flag for each vertex if it is visited or not
    val visited = BooleanArray(noOfVertices)

    val currentVisitingStack: Deque<Int> = LinkedList()
    val connectedComponents = mutableListOf<List<Int>>()

    fun dfs(vertex: Int, start: Int) {
        val currentId = id++
        visited[vertex] = true
        currentVisitingStack.push(vertex)
        onStack[vertex] = true

        // assign id to vertex and low-link value
        vertexIds[vertex] = currentId
        lowLinkValues[vertex] = currentId

        adjacencyList[vertex].forEach { adjacentVertex ->
            if (visited[adjacentVertex].not()) {
                dfs(adjacentVertex, start)
            }

            // if vertex is on stack, update low-link value
            if (onStack[adjacentVertex]) {
                lowLinkValues[vertex] = min(lowLinkValues[vertex], lowLinkValues[adjacentVertex])
            }

            // self-loop
            if (vertex == adjacentVertex) {
                connectedComponents.add(listOf(vertex))
            }
        }

        /**
         * If a vertex is part of strongly connected component,
         * its lowLinkValue not be same as ID except start vertex
         * for lowLinkValue == vertexId
         */
        if (vertexIds[vertex] == lowLinkValues[vertex]) {
            if (vertex == start && currentVisitingStack.size > 1) {
                // we reached the start, collect component vertices
                connectedComponents.add(currentVisitingStack.toList())
            }
            /**
             * Pop all values from stack until start vertex
             */
            while (currentVisitingStack.isNotEmpty()) {
                val node = currentVisitingStack.pop()
                onStack[node] = false
                lowLinkValues[node] = lowLinkValues[vertex]
                if (node == vertex) break
            }
        }
    }

    // start DFS from each unvisited vertex
    for (vertex in adjacencyList.indices) {
        if (visited[vertex].not()) {
            dfs(vertex, vertex)
        }
    }

    return connectedComponents
}
//sampleEnd