DFS(深度优先搜索)

DFS是一种搜索算法，在我的理解中，它是通过一种类似树状的结构来进行搜索的，运用递归算法。

例题

先来一道例题，来看一下是它试适用的情况。

输入

输入n。

输出

输出{1,2,3,4,5,......,n}的n!种排列

例如：

输入

3

输出

123
132
213
231
312
321

对于这道题，其实有别的方法来解决，但是却是很好的一个例子来讲解DFS算法的过程。

首先，我们人类来处理这个问题的时候，往往就是按顺序来进行枚举，但在这其中也有着一定的规律，我们把它用树状图进行表示就是这个样子的：

树状图 每一个节点都有新的分支，而DFS就是通过每一个分支，一直到树的底部再返回，然后再到下一个节点继续，具体可以参考下我写的二叉树里面的遍历。

解题

DFS主要运用递归进行运算，而递归的主要思路和循环类似，也是重复的做一件相同或相似的事情。

那在遍历一棵树的时候，我们可以发现他做的工作就是遍历当前节点的子节点，若遇到末端时，那就不再继续往下遍历子节点了。

通过这个思路，我们可以写出下面的大致结构(伪代码)：

void dfs(传递给下一个节点的参数)
{
    if (到末尾了) return; // 这样可是实现返回上一节点，同时让上一个函数的for循环继续遍历下一个节点
    for (int i = 0;i < 子节点个数;i ++)
    {
        处理一些参数
        dfs(处理好的参数);
    }
}

那么，我们再来看看这道题目。

观察这棵树的箭头，可以发现，第一个root节点有3个子节点，而其子节点1、2、3每个各有2个节点，再下去就变成了1个子节点了。

由此我们便可以发现规律：树每往下深入一层，子节点数便减1。

由于vector可以使用erase方法和迭代器将元素删除，因此我们可以用它来存储数字。

先来一段数据读入吧：

int main()
{
    int n;
    scanf("%d",&n);
    vector<int> nums;
    for (int i = 1; i <= n; i++)
    {
        nums.push_back(i);
    }
    dfs(nums,0);
    return 0;
}

这样，我们就用vector完成了读入。

那么我们再来看看dfs这个函数：

void dfs(vector<int> e,int num)
{
    if (e.size() == 0) // 当e的大小变为0的时候，也就是当到了树的末尾
    {
        printf("%d\n",num); // 我们就将这个数字输出
        return; // return掉
    }
    for (int i = 0; i < e.size(); i ++) // 遍历每一个子节点
    {
        vector<int> e2(e); // 复制一个vector，以便减少一个节点并递到下一个函数去
        e2.erase(e2.begin() + i); // 用迭代器删掉e中第i个元素，去重
        int n = num * 10 + e[i]; // 计算数值
        dfs(e2, n); // 传递下去，给下一个节点
    }
}

注释已经写得很详细了，看完你就能懂了。

结语

通过这个例子，大家应该对DFS深度搜索有了一个大致的概念了吧，之后再使用的时候就可以把DFS搜索当成搜索一棵树，这样就好理解很多。