什么是深度优先搜索？

深度优先搜索（Depth-First Search，简称DFS） 是一种用于遍历或搜索树或图数据结构的算法。其核心思想是尽可能深地沿着树的分支向下探索，直到无法继续为止，然后回溯到上一节点，继续探索其他分支。

DFS 的基本思想

1. 从起始节点开始，标记为已访问
2. 尽可能深地向下访问未访问的邻接节点
3. 当到达尽头（无未访问邻接节点）时，回溯到上一个节点
4. 重复上述过程，直到所有节点都被访问

DFS 的实现方式

DFS主要有两种实现方式：

• 递归实现：利用系统栈，代码简洁
• 显式栈实现：使用手动维护的栈，更灵活

C++ 代码实现

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

// 邻接表表示的图
vector<vector<int>> adj;
vector<bool> visited;

// 递归实现 DFS
void dfs_recursive(int u) {
    visited[u] = true;
    cout << u << " ";
    
    for (int v : adj[u]) {
        if (!visited[v]) {
            dfs_recursive(v);
        }
    }
}

// 迭代实现 DFS（使用显式栈）
void dfs_iterative(int start) {
    stack<int> st;
    st.push(start);
    visited[start] = true;
    
    while (!st.empty()) {
        int u = st.top();
        st.pop();
        cout << u << " ";
        
        for (int v : adj[u]) {
            if (!visited[v]) {
                visited[v] = true;
                st.push(v);
            }
        }
    }
}

int main() {
    // 示例图：5个节点
    int n = 5;
    adj.resize(n);
    
    // 添加边 (无向图)
    adj[0].push_back(1);
    adj[1].push_back(0);
    adj[0].push_back(2);
    adj[2].push_back(0);
    adj[1].push_back(3);
    adj[3].push_back(1);
    adj[2].push_back(4);
    adj[4].push_back(2);
    
    visited.assign(n, false);
    cout << "递归 DFS (从节点0开始): ";
    dfs_recursive(0);
    cout << endl;
    
    visited.assign(n, false);
    cout << "迭代 DFS (从节点0开始): ";
    dfs_iterative(0);
    cout << endl;
    
    return 0;
}

DFS 的应用场景

1. 连通分量检测：判断图是否连通
2. 拓扑排序：解决有向无环图的依赖问题
3. 路径查找：寻找两点之间的路径
4. 迷宫求解：深度优先探索可能路径
5. 二叉树遍历：前序、中序、后序遍历

复杂度分析

• 时间复杂度：O(V + E)，V为节点数，E为边数
• 空间复杂度：O(V)，用于存储访问标记和栈

总结

深度优先搜索是一种强大而灵活的算法，掌握它是学习图论和算法的基础。递归实现简洁直观，迭代实现则更易于理解和调试。