Depth-first search (DFS)

Depth-first search (DFS) explores one branch of a graph as far as the chosen traversal rules allow, then returns to other branches. It can use recursion (which stores active calls on the call stack) or an explicit LIFO stack. A visited set is important on a graph because cycles and converging routes are possible.

Explore a sample graph

Visited: –

Queue: –

PreviousNext stepReset

Neighbors are considered alphabetically. DFS pushes them in reverse order so the first alphabetical neighbor is visited next.

Choose DFS. The current implementation pushes neighbors in reverse alphabetical order so the first alphabetical neighbor is popped next. Notice that the stack records vertices scheduled for processing, not necessarily the exact recursive call stack. Another ordering of adjacency lists can produce a different, equally correct DFS order.

Implementation in C# and C++

C#

C# | DFS.cs

using System.Collections.Generic;

static List<int> Dfs(IReadOnlyList<int>[] graph, int start)
{
    if ((uint)start >= (uint)graph.Length)
        throw new ArgumentOutOfRangeException(nameof(start));
    var visited = new bool[graph.Length];
    var stack = new Stack<int>();
    var order = new List<int>();
    visited[start] = true;
    stack.Push(start);
    while (stack.Count > 0)
    {
        int current = stack.Pop();
        order.Add(current);
        for (int i = graph[current].Count - 1; i >= 0; i--)
        {
            int next = graph[current][i];
            if ((uint)next >= (uint)graph.Length)
                throw new ArgumentException("Invalid neighbor index", nameof(graph));
            if (visited[next]) continue;
            visited[next] = true;
            stack.Push(next);
        }
    }
    return order;
}

C++

C++ | DFS.cpp

#include <vector>
#include <stack>
#include <stdexcept>

std::vector<int> dfs(const std::vector<std::vector<int>>& graph, int start) {
    if (start < 0 || static_cast<std::size_t>(start) >= graph.size())
        throw std::out_of_range("start");
    std::vector<bool> visited(graph.size(), false);
    std::stack<int> stack;
    std::vector<int> order;
    visited[start] = true;
    stack.push(start);
    while (!stack.empty()) {
        int current = stack.top(); stack.pop();
        order.push_back(current);
        const auto& neighbors = graph[current];
        for (auto it = neighbors.rbegin(); it != neighbors.rend(); ++it) {
            int next = *it;
            if (next < 0 || static_cast<std::size_t>(next) >= graph.size())
                throw std::out_of_range("neighbor");
            if (visited[next]) continue;
            visited[next] = true;
            stack.push(next);
        }
    }
    return order;
}

Both examples mark vertices when pushed so the same vertex is not scheduled repeatedly. A textbook recursive DFS instead marks on entering a vertex and explores each unvisited neighbor immediately. On graphs with cross edges, the visitation order of an explicit stack that marks on push can differ from a recursive DFS, but both visit the reachable component.

What DFS is useful for

DFS supports reachability, connected-component discovery, topological sorting of directed acyclic graphs and cycle detection with appropriate additional state. In game development it can explore connected rooms or test whether a level layout contains isolated areas. DFS is not guaranteed to find a shortest path even if every edge has equal cost.

Complexity and memory

For an adjacency-list graph, the traversal needs O(V + E) time over the reachable component. A visited array and explicit stack or recursive call stack require O(V) auxiliary space in the worst case. If the code returns the visitation sequence, storing that output uses another O(V). Recursive code can overflow a limited call stack on a deep graph; iterative DFS avoids that particular constraint, though it still uses memory for its frontier.

Disconnected components and edge direction

A single start only discovers reachable vertices. To visit all components, iterate over all vertices and start DFS from each still unvisited one. In directed graphs, reachability follows the direction of edges; the reverse route may not exist.

Try it: Change the neighbor order of B on paper. Does the traversal order change? Does reachability change? Then compare BFS and DFS.

References: Codecademy DFS, GeeksforGeeks DFS, Wikipedia DFS.