Find connected components of a graph using DFS

A graph’s connected components can be found using Depth-First-Search (DFS). This method involves starting DFS from each vertex, if it hasn’t been visited already, and grouping all vertices visited from that vertex.

As long as a component of the graph is connected, DFS will visit all its connected vertices.

• Using DFS, the following Kotlin script finds all the connected components in the graph given above.

fun main() {
    val adjacencyList = mutableListOf<List<Int>>().apply {
        add(0, listOf(1, 2))
        add(1, listOf(0, 2))
        add(2, listOf(0, 1, 3, 7))
        add(3, listOf(2))
        add(4, listOf(8, 5))
        add(5, listOf(8, 4))
        add(6, listOf(9, 10))
        add(7, listOf(2))
        add(8, listOf(4, 5))
        add(9, listOf(6, 11))
        add(10, listOf(6, 11))
        add(11, listOf(10, 9))
    }
    val components = findConnectedComponents(adjacencyList)
    components.forEach {
        println("component ${it.key} -> ${it.value}")
    }
}

//sampleStart
fun findConnectedComponents(adjacencyList: List<List<Int>>): Map<String, List<Int>> {
    // click + to see full script
    val visited = BooleanArray(adjacencyList.size)

    /**
     * componentId -> vertices map
     * contains vertices belongs to each component
     */
    val componentMap = mutableMapOf<String, MutableList<Int>>()
    var currentComponentId = 0

    fun dfs(vertex: Int, componentId: String) {
        visited[vertex] = true
        componentMap[componentId]?.add(vertex)
        adjacencyList[vertex].forEach {adjacentVertex ->
            if (visited[adjacentVertex].not()) {
                dfs(adjacentVertex, componentId)
            }
        }
    }

    // group vertices belong to each component
    for (vertex in adjacencyList.indices) {
        if (visited[vertex].not()) {
            val componentId = "${currentComponentId++}"
            componentMap[componentId] = mutableListOf()
            dfs(vertex, componentId)
        }
    }

    return componentMap
}
//sampleEnd