Depth First Search (DFS)

Depth-first search (DFS) algorithm is a graph search algorithm. Starting from a given vertex, it first explores an adjacent vertex of that vertex. Next, it explores an adjacent vertex of this vertex. In this way, the exploration continues until a certain vertex has no adjacent vertices, it will return to the previous vertex, and explores the next adjacent vertex of the vertex. It will continue to explore like this until it finds a result, or explores all vertices.

Recursive Version

Algorithm

The recursive version of the DFS algorithm requires a data structure called visited, which is used to record whether each vertex has been explored. The recursive version of the DFS algorithm is to do a DFS on the adjacent vertices of each vertex.

Algorithm DFS(v, visited) {
    visited[v] := true;
    for all edges (v, w) {
        if !visited[w] {
            DFS(w, visited);
        }
    }
}

Time and Space Complexity

DFS scans and explores each vertex once, and the time complexity is O(V). Then, it scans all adjacent vertices of each vertex once, and the time complexity of this is O(E). So, the total time complexity of DFS is O(V + E).

DFS needs a data structure to record whether a vertex has been explored, so the space complexity is O(V). When calling DFS() recursively, the program pushes the parameters and return address into the stack. In the worst case, that would be exploring recursively from the first vertex to the last, so the space complexity is O(V). Therefore, the total space complexity of DFS is O(V).

Non-Recursive Version

Algorithm

The non-recursive version of the DFS algorithm requires two data structures. One is called visited, which is used to record whether each vertex has been explored, and the other is a stack. When a certain vertex is explored, it pushes the adjacent vertices into the stack one by one. Then, each time, the last pushed vertex is popped from the stack to explore.

Algorithm DFS(v) {
    stack := Stack();
    stack.push(v);
    while stack.isNotEmpty {
        u := stack.pop();
        if !visited[u] {
            visited[u] := true;
            for all edges (u, w) {
                stack.push(w);
            }
        }
    }
}

Time and Space Complexity

DFS scans and explores each vertex once, and the time complexity is O(V). Then, it scans all adjacent vertices of each vertex once, and the time complexity of this is O(E). So, the total time complexity of DFS is O(V + E).

DFS needs a data structure to record whether a vertex has been explored, so the space complexity is O(V). Also, it requires a stack, and each vertex is only pushed once. In the worst case, all vertices are in the stack except the vertex currently being explored, so the space complexity is O(V). Therefore, the total space complexity of DFS is O(V).

Example

The following example is a recursive version of the DFS algorithm. It shows the changes inside visited at each step.

Reference

• Ellis Horowitz, Sartaj Sahni, Sanguthevar Rajasekaran, Computer Algorithm.
• Depth-first search, Wikipedia.