Graph Traversal: BFS and DFS

BFS layers measure unweighted distance

Breadth-first search uses a queue and discovers vertices in increasing edge distance from the source. Mark a vertex when enqueuing it so multiple incoming edges do not schedule duplicate work.

Copy codefun distances(graph: List<List<Int>>, start: Int): IntArray {
    require(start in graph.indices && graph.all { edges -> edges.all { it in graph.indices } })
    val distance = IntArray(graph.size) { -1 }
    val queue = ArrayDeque<Int>()
    distance[start] = 0
    queue.addLast(start)
    while (queue.isNotEmpty()) {
        val node = queue.removeFirst()
        for (next in graph[node]) if (distance[next] == -1) {
            distance[next] = distance[node] + 1
            queue.addLast(next)
        }
    }
    return distance
}

DFS instead explores one path before backtracking, using recursion or a stack. Both run in O(V+E) with adjacency lists. Ordinary DFS does not guarantee shortest unweighted paths.

Exercise

Test a cycle, an isolated vertex, and two routes of different lengths. Add parent pointers to reconstruct a BFS path.

Check: unreachable vertices remain -1; a disconnected graph requires additional starting points when the task is to visit every component.

Further reading: Graph traversal