跳转至

DFS（圖論）

引入

DFS 全稱是 Depth First Search，中文名是深度優先搜索，是一種用於遍歷或搜索樹或圖的算法。所謂深度優先，就是説每次都嘗試向更深的節點走。

該算法講解時常常與 BFS 並列，但兩者除了都能遍歷圖的連通塊以外，用途完全不同，很少有能混用兩種算法的情況。

DFS 常常用來指代用遞歸函數實現的搜索，但實際上兩者並不一樣。有關該類搜索思想請參閲 DFS（搜索）.

過程

DFS 最顯著的特徵在於其 遞歸調用自身。同時與 BFS 類似，DFS 會對其訪問過的點打上訪問標記，在遍歷圖時跳過已打過標記的點，以確保 每個點僅訪問一次。符合以上兩條規則的函數，便是廣義上的 DFS。

具體地説，DFS 大致結構如下：

1
2
3
4
5
6
7
8
DFS(v) // v 可以是圖中的一個頂點，也可以是抽象的概念，如 dp 狀態等。
  在 v 上打訪問標記
  for u in v 的相鄰節點
    if u 沒有打過訪問標記 then
      DFS(u)
    end
  end
end

以上代碼只包含了 DFS 必需的主要結構。實際的 DFS 會在以上代碼基礎上加入一些代碼，利用 DFS 性質進行其他操作。

性質

該算法通常的時間複雜度為 \(O(n+m)\)，空間複雜度為 \(O(n)\)，其中 \(n\) 表示點數，\(m\) 表示邊數。注意空間複雜度包含了棧空間，棧空間的空間複雜度是 \(O(n)\) 的。在平均 \(O(1)\) 遍歷一條邊的條件下才能達到此時間複雜度，例如用前向星或鄰接表存儲圖；如果用鄰接矩陣則不一定能達到此複雜度。

備註：目前大部分算法競賽（包括 NOIP、大部分省選以及 CCF 舉辦的各項賽事）都支持 無限棧空間，即：棧空間不單獨限制，但總內存空間仍然受題面限制。但大部分操作系統會對棧空間做額外的限制，因此在本地調試時需要一些方式來取消棧空間限制。

  • 在 Windows 上，通常的方法是在 編譯選項 中加入 -Wl,--stack=1000000000，表示將棧空間限制設置為 1000000000 字節。
  • 在 Linux 上，通常的方法是在運行程序前 在終端內 執行 ulimit -s unlimited，表示棧空間無限。每個終端只需執行一次，對之後每次程序運行都有效。

實現

棧實現

DFS 可以使用 棧（Stack） 為遍歷中節點的暫存容器來實現；這與用 隊列（Queue） 實現的 BFS 形成高度對應。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
vector<vector<int>> adj;  // 鄰接表
vector<bool> vis;         // 記錄節點是否已經遍歷

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;  // 確保棧裏沒有重複元素
        st.push(v);
      }
    }
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
# adj : List[List[int]] 鄰接表
# vis : List[bool] 記錄節點是否已經遍歷

def dfs(s : int) -> None:
    stack = [s] # 用列表來模擬棧，把起點加入棧中
    vis[s] = True # 起點被遍歷

    while(not stack):
        u = stack.pop() # 拿取並丟棄掉最後一個元素（棧頂的元素），可以理解為走到u這個元素

        for v in adj[u]: # 對於與u相鄰的每個元素v
            if not vis[v]: # 如果v在此前沒有走過
                vis[v] = True # 確保棧裏沒有重複元素
                stack.append(v) # 把v加入棧中

遞歸實現

函數在遞歸調用時的求值如同對棧的添加和刪除元素的順序，故函數調用所佔據的虛擬地址被稱為函數調用棧（Call Stack），DFS 可用遞歸的方式實現。

以 鄰接表（Adjacency List） 作為圖的存儲方式：

1
2
3
4
5
6
7
8
vector<vector<int>> adj;  // 鄰接表
vector<bool> vis;         // 記錄節點是否已經遍歷

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
# adj : List[List[int]] 鄰接表
# vis : List[bool] 記錄節點是否已經遍歷

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

以 鏈式前向星 為例：

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 序列

DFS 序列是指 DFS 調用過程中訪問的節點編號的序列。

我們發現，每個子樹都對應 DFS 序列中的連續一段（一段區間）。

括號序列

DFS 進入某個節點的時候記錄一個左括號 (，退出某個節點的時候記錄一個右括號 )。

每個節點會出現兩次。相鄰兩個節點的深度相差 1。

一般圖上 DFS

對於非連通圖，只能訪問到起點所在的連通分量。

對於連通圖，DFS 序列通常不唯一。

注：樹的 DFS 序列也是不唯一的。

在 DFS 過程中，通過記錄每個節點從哪個點訪問而來，可以建立一個樹結構，稱為 DFS 樹。DFS 樹是原圖的一個生成樹。

DFS 樹 有很多性質，比如可以用來求 強連通分量。

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