DFS简介

什么是DFS

DFS算法，全称为深度优先搜索算法，是一种用于图和树遍历的算法。它的应用范围非常广，比如词语互换游戏、迷宫问题等。

首先，我们来看一下什么是图和树。图就是由节点和边组成的集合，每一个节点表示图中的一个物体，每一条边表示物体之间的联系。树是一种特殊的图，它是由n个节点和n-1条边组成的，其中一个节点没有父节点，其他节点都只有一个父节点。

DFS算法的思想很简单，它就是从一个起点开始，不停地向下遍历，直到找到终点或者无法继续向下遍历为止。换言之，它是一种尽可能深地遍历图或树的算法。

在实现DFS算法时，我们需要使用一个栈来保存当前节点的信息，然后在访问完当前节点后，将下一个需要访问的节点入栈，然后继续遍历下去。

下面我们来看一下DFS算法的C++代码实现：

代码实现

#include <bits/stdc++.h>
using namespace std;

void dfs(int node, vector<int> adj[], bool visited[]) {
    // 标记当前节点已访问
    visited[node] = true;
    cout << node << " ";

    // 遍历当前节点的所有邻居节点
    for (int i = 0; i < adj[node].size(); i++) {
        int neighbor = adj[node][i];

        // 如果邻居节点没有被访问过，则继续遍历
        if (!visited[neighbor]) {
            dfs(neighbor, adj, visited);
        }
    }
}

int main() {
    // 定义节点数和边数
    int n, m;
    cin >> n >> m;

    // 定义邻接表
    vector<int> adj[n+1];

    // 定义每个节点是否被访问过
    bool visited[n+1] = {false};

    // 读入每条边
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;

        // 添加邻居节点
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // 从节点1开始进行DFS遍历
    dfs(1, adj, visited);

    return 0;
}

上面的代码实现了从节点1开始遍历图或树的DFS算法，其中adj数组是邻接表，visited数组是记录每个节点是否被访问过的数组。

总结

DFS算法是一种非常基础的算法，它可以解决很多图和树的遍历问题。在实现DFS算法时，需要使用一个栈来保存当前节点信息，然后不停地向下遍历，直到找到终点或者无法继续向下遍历为止。

抽象出DFS的一个通用模板

int check(参数)
{
    if(满足条件)
        return 1;
    return 0;
}
 
void dfs(int step)
{
        判断边界
        {
            相应操作
        }
        尝试每一种可能//如for(i=1;i<=n;i++)
        {
               满足check条件//如if(vis[i]==0)
               标记//如vis[i]=1;
               继续下一步dfs(step+1)
               恢复初始状态（回溯的时候要用到）//如vis[i]=0;
        }
}