Depth-First Search

Depth-first search follows one path until it cannot continue, then backtracks.

static void depthFirst(
        List<List<Integer>> graph, int vertex, boolean[] visited) {
    visited[vertex] = true;
    for (int neighbor : graph.get(vertex)) {
        if (!visited[neighbor]) depthFirst(graph, neighbor, visited);
    }
}

To traverse a disconnected graph, call the search from every still-unvisited vertex. An explicit stack avoids call-stack overflow on deep graphs.

Invariant and cost

Once marked, a vertex is never recursively entered again. Therefore every vertex is processed at most once, and every adjacency entry is inspected once. Time is Θ(V + E) and visited state plus stack use O(V) auxiliary space.

Applications

• connected components in undirected graphs;
• cycle detection using parent or color state;
• topological ordering using finish times;
• strongly connected components;
• articulation points and bridges.

A boolean visited flag is insufficient for every directed-cycle algorithm. Three colors—unvisited, active, finished—distinguish an edge into the current recursion stack from an edge into an already completed subtree.