Skip to content

DFS (Graph Theory)

Introduction

DFS, short for Depth First Search, is an algorithm for traversing or searching tree or graph data structures. The term "depth-first" means that it always tries to go deeper into the graph at each step.

This algorithm is often taught alongside BFS, but apart from both being able to traverse connected components of a graph, their applications are quite different, and there are few scenarios where the two algorithms can be used interchangeably.

DFS is often used to refer to searches implemented using recursive functions, but in reality, the two are not exactly the same. For the search paradigm, please refer to DFS (Search).

Process

The most distinctive feature of DFS is its recursive self-calls. Similar to BFS, DFS marks visited nodes during traversal, skipping nodes that have already been marked to ensure each node is visited only once. Any function that follows these two rules can be considered a generalized DFS.

Specifically, the general structure of DFS is as follows:

1
2
3
4
5
6
7
8
DFS(v) // v can be a vertex in a graph or an abstract concept, such as a DP state.
  Mark v as visited
  for u in adjacent nodes of v
    if u is not visited then
      DFS(u)
    end
  end
end

The above code only includes the essential structure of DFS. In practice, additional code is often added to leverage DFS properties for other operations.

Properties

The algorithm typically has a time complexity of \(O(n+m)\) and a space complexity of \(O(n)\), where \(n\) represents the number of vertices and \(m\) represents the number of edges. Note that the space complexity includes stack space, which is \(O(n)\). This time complexity is achieved under the condition of traversing each edge in \(O(1)\) on average, such as when using forward stars or adjacency lists to store the graph; using an adjacency matrix may not achieve this complexity.

Note: Currently, most programming contests (including NOIP, most provincial selections, and competitions organized by CCF) support unlimited stack space, meaning: stack space is not separately restricted, but the total memory space is still limited by the problem statement. However, most operating systems impose additional restrictions on stack space, so local debugging requires methods to lift these restrictions.

  • On Windows, the common method is to add -Wl,--stack=1000000000 to the compilation options, setting the stack space limit to 1,000,000,000 bytes.
  • On Linux, the common method is to execute ulimit -s unlimited in the terminal before running the program, indicating unlimited stack space. This only needs to be done once per terminal and is effective for each subsequent program run.

Implementation

Stack Implementation

DFS can be implemented using a Stack as a temporary container for nodes during traversal; this highly corresponds to BFS implemented with a Queue.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
vector<vector<int>> adj;  // Adjacency list
vector<bool> vis;         // Record whether nodes have been visited

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 no duplicate elements in the stack
        st.push(v);
      }
    }
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
# adj : List[List[int]] Adjacency list
# vis : List[bool] Record whether nodes have been visited


def dfs(s: int) -> None:
    stack = [s]  # Use a list to simulate a stack, add the starting point to the stack
    vis[s] = True  # Starting point is visited

    while stack:  # Continue while the stack is not empty
        u = (
            stack.pop()
        )  # Take and discard the last element (top of the stack), can be understood as moving to element 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 no duplicate elements in the stack
                stack.append(v)  # Add v to the stack

Recursive Implementation

The order of function evaluation during recursive calls resembles adding and removing elements from a stack, hence the virtual address space occupied by function calls is called the Call Stack. DFS can be implemented recursively.

Using an Adjacency List as the graph storage method:

1
2
3
4
5
6
7
8
vector<vector<int>> adj;  // Adjacency list
vector<bool> vis;         // Record whether nodes have been visited

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

1
2
3
4
5
6
7
8
9
# adj : List[List[int]] Adjacency list
# vis : List[bool] Record whether nodes have been visited


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

Using Chain Forward Star as an example:

1
2
3
4
5
6
7
8
void dfs(int u) {
  vis[u] = 1;
  for (int i = head[u]; i; i = e[i].x) {
    if (!vis[e[i].t]) {
      dfs(v);
    }
  }
}

1
2
3
4
5
6
7
8
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);
        }
    }
}

1
2
3
4
5
6
7
def dfs(u):
    vis[u] = True
    i = head[u]
    while i:
        if vis[e[i].t] == False:
            dfs(v)
        i = e[i].x

DFS Sequence

The DFS sequence refers to the sequence of node IDs visited during the DFS call process.

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

Bracket Sequence

Record a left parenthesis ( when DFS enters a node, and record a right parenthesis ) when exiting a node.

Each node appears twice. The depth difference between two adjacent nodes is 1.

DFS on General Graphs

For non-connected graphs, only the connected component containing the starting point can be visited.

For connected graphs, the DFS sequence is generally not unique.

Note: The DFS sequence of a tree is also not unique.

During DFS, by recording which node each node was visited from, a tree structure called the DFS tree can be constructed. The DFS tree is a spanning tree of the original graph.

The DFS Tree has many properties, such as being used to find Strongly Connected Components.

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用