Cycle detection in a graph using DFS

Algorithms  #algorithms  #dfs  #graphs  #cycle-detection 

The depth-first search (DFS) can be used to detect cycles in a graph. The steps are as follows

1. When performing DFS from a vertex, if a new vertex is discovered (not already visited), mark the current vertex as its parent.
2. Cycles occur when a new vertex is discovered that has already been visited, but is not the parent of the current vertex.

Illustration

Cycle detection is illustrated in the following diagram

a. The DFS traversal begins at vertex 1

b. It moves to vertex 2, making vertex 1 the parent

c. Taking vertex 2 as the parent of vertex 3, it goes to vertex 3

d. In this traversal, if vertex 2 is visited again as it is the parent of vertex 3, ignore it.This is a cycle if from vertex 3, we visit vertex 1 that is not parent and has already been visited

Example (Kotlin)

• This sample code performs detects a cycle in the graph above.

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

    detectCycle(adjacencyList)
}

fun detectCycle(adjacencyList: List<List<Int>>) {
    // click + to see full script

    // keep track of visited vertices
    val visited = BooleanArray(adjacencyList.size)

    fun dfs(vertex: Int, parent: Int) {
        visited[vertex] = true
        adjacencyList[vertex].forEach { adjacentVertex ->
            if (visited[adjacentVertex].not()) {
                dfs(adjacentVertex, vertex)
            } else if (adjacentVertex != parent) {
                // if adjacent vertex is visited and not parent
                // this is forming a cycle
                throw IllegalStateException("cycle detected")
            }
        }
    }

    for (vertex in adjacencyList.indices) {
        if (visited[vertex].not()) {
            // parent of start vertex is -1
            dfs(vertex, parent =-1)
        }
    }
    println("no cycle detected")
}