DFS (Graph Theory)

Introduction

DFS stands for Depth First Search. In Chinese, it is called depth-first search, and it is an algorithm for traversing or searching a tree or graph. “Depth first” means that at each step it attempts to move to a deeper node.

DFS is often discussed alongside BFS. Although both can traverse the connected components of a graph, their uses are completely different, and there are few situations where the two algorithms can be interchanged.

DFS is often used to refer to a search implemented with a recursive function, but the two concepts are not actually identical. For this kind of search idea, see DFS (search).

Process

The most notable feature of DFS is that it recursively calls itself. Like BFS, DFS also marks the points it has visited and skips marked points when traversing a graph, ensuring that each point is visited only once. A function satisfying these two rules is broadly considered DFS.

More specifically, the general structure of DFS is as follows:

DFS(v) // v may be a vertex in the graph or an abstract concept such as a DP state
  mark v as visited
  for each node u adjacent to v
    if u has not been visited then
      DFS(u)
    end
  end
end

The code above contains only the essential structure of DFS. An actual DFS adds other code on this basis to use DFS properties for additional operations.

Properties

The usual time complexity of this algorithm is $O(n+m)$ and the space complexity is $O(n)$, where $n$ is the number of vertices and $m$ is the number of edges. Note that the space complexity includes the stack space, whose complexity is $O(n)$. This time complexity is attainable only when an edge can be traversed in average $O(1)$ time, for example when the graph is stored as a forward-star structure or an adjacency list; an adjacency matrix does not necessarily achieve this complexity.

Note: Most current algorithm competitions, including NOIP, most provincial selections, and competitions held by CCF, support unlimited stack space: stack space is not limited separately, although total memory is still subject to the limits in the statement. Most operating systems impose additional limits on stack space, however, so local debugging requires a way to remove that limit.

• On Windows, the usual method is to add -Wl,--stack=1000000000 to the compiler options, setting the stack-space limit to 1000000000 bytes.
• On Linux, before running the program, execute ulimit -s unlimited in the terminal to make stack space unlimited. This only needs to be done once in each terminal and applies to every subsequent program run.

Implementation

Stack-Based Implementation

DFS can use a stack as a temporary container for nodes during traversal. This corresponds closely to implementing BFS with a queue.

C++

vector<vector<int>> adj;  // adjacency list
vector<bool> vis;         // records whether each node has been traversed

void dfs(int s) {
  stack<int> st;
  st.push(s);
  vis[s] = true;

  while (!st.empty()) {
    int u = st.top();
    st.pop();

    for (int v : adj[u]) {
      if (!vis[v]) {
        vis[v] = true;  // ensure that the stack contains no duplicate elements
        st.push(v);
      }
    }
  }
}

Python

# adj : List[List[int]] adjacency list
# vis : List[bool] records whether each node has been traversed

def dfs(s: int) -> None:
    stack = [s]  # simulate a stack with a list and push the start point
    vis[s] = True  # the start point has been traversed

    while stack:  # continue while the stack is nonempty
        u = (
            stack.pop()
        )  # take and discard the last element (the top of the stack), which is equivalent to moving to u

        for v in adj[u]:  # for each element v adjacent to u
            if not vis[v]:  # if v has not been visited before
                vis[v] = True  # ensure that the stack contains no duplicate elements
                stack.append(v)  # add v to the stack

Recursive Implementation

When a function is called recursively, its evaluation follows the same order as adding and removing elements from a stack, so the virtual addresses occupied by function calls are called the function call stack. DFS can therefore be implemented recursively.

Using an adjacency list as the graph representation:

C++

vector<vector<int>> adj;  // adjacency list
vector<bool> vis;         // records whether each node has been traversed

void dfs(const int u) {
  vis[u] = true;
  for (int v : adj[u])
    if (!vis[v]) dfs(v)
}

Python

# adj : List[List[int]] adjacency list
# vis : List[bool] records whether each node has been traversed

def dfs(u: int) -> None:
    vis[u] = True
    for v in adj[u]:
        if not vis[v]:
            dfs(v)

Using a forward-star representation as an example:

C++

void dfs(int u) {
  vis[u] = 1;
  for (int i = head[u]; i; i = e[i].x) {
    if (!vis[e[i].t]) {
      dfs(v);
    }
  }
}

Java

public void dfs(int u) {
    vis[u] = true;
    for (int i = head[u]; i != 0; i = e[i].x) {
        if (!vis[e[i].t]) {
            dfs(v);
        }
    }
}

Python

def dfs(u):
    vis[u] = True
    i = head[u]
    while i:
        if vis[e[i].t] == False:
            dfs(v)
        i = e[i].x

DFS Order

The DFS order is the sequence of vertex numbers visited during DFS.

We observe that every subtree corresponds to a contiguous segment (an interval) in the DFS order.

Parenthesis Sequence

When DFS enters a node, record a left parenthesis (; when it leaves a node, record a right parenthesis ).

Each node appears twice. The depths of two adjacent nodes differ by 1.

DFS on General Graphs

For a disconnected graph, only the connected component containing the starting point can be visited.

For a connected graph, the DFS order is usually not unique.

Note that the DFS order of a tree is also not unique.

During DFS, recording the point from which each node was visited produces a tree structure called the DFS tree. The DFS tree is a spanning tree of the original graph.

The DFS tree has many properties; for example, it can be used to find strongly connected components.