c++ dfs原理 及其模板

DFS(Depth First Search，深度优先搜索)是一种用于图遍历或树遍历的算法。其基本思想是从起点开始，选择一个相邻的未访问过的节点，然后继续访问该节点的未访问过的相邻节点，直到所有的节点都被访问过为止。

DFS算法的模板如下：

1. 定义visited数组，用于记录节点是否被访问过。

2. 定义dfs函数，该函数接受一个节点作为参数。

3. 在dfs函数中，将当前节点标记为已访问。

4. 遍历当前节点的邻居节点：

1) 如果邻居节点未被访问过，则递归调用dfs函数访问该节点。

2) 如果邻居节点已被访问过，则继续遍历下一个邻居节点。

5. 在dfs函数中，对当前节点的操作（如打印节点值）。

以下是一个简单的DFS模板示例：

void dfs(int node, vector<vector<int>>& graph, vector<bool>& visited) {
    visited[node] = true;  // 标记当前节点已访问
    for (int i = 0; i < graph[node].size(); i++) {
        int neighbor = graph[node][i];  // 遍历当前节点的邻居节点
        if (!visited[neighbor]) {  // 如果邻居节点未被访问过
            dfs(neighbor, graph, visited);  // 递归访问邻居节点
        }
    }
    // 在这里可以对当前节点进行操作，如打印节点值
}

以上模板中，graph是一个二维数组，表示图的邻接表。visited是一个bool类型的数组，用于记录节点是否被访问过。在主函数中调用dfs函数即可开始搜索。