DFS-深度优先搜索（Depth First Search）—1

傷城~ 2022-07-11 13:19 171阅读 0赞

深度优先搜索算法，作为最常用的算法之一，在很多地方都有它的身影，也被很多人称为“万能的搜索”，可能这个说话有点过了，但是由此也可以看出它有多么强大。好了，多说无益，我们一起来看看这个“万能的算法”的真面目：

先从一道题目说起：假设现在有0~9一共10个数字，每个数字只能并且一定要出现一次，求它们的全排列。
    全排列，举个例子：数字1、2、3的全排列有：123、132、213、231、312、321 一共6种。

如果不知道深度优先搜索算法，看到这道题可能第一反应可能是使用枚举，那么得使用10重循环，并且还要判断10个数字是不是有重复的，我想除非你是个代码狂魔，不然的话你肯定不会去写这个代码。那么有更好的办法吗？of course，这就是典型的深度优先搜索算法（以下简称dfs）题。  
在每次选取数字的时候，我们都有10种可能，当然不是每一种可能都能成功，因为我们不能选取重复的数字，那么怎么办呢，我们这里可以采用标记数组的思想，定义一个数组标记0~9一共10个数字的状态（是否被选取），如果当前数字已经被选取那么筛选下一个数字，否则的话就选择当前的数字，下一步仍然采取这种筛选方法（很明显是个递归的思想），那么我们脑子里就可以架构出大概的代码结构：

for(int i = 0; i < 10; i++)
    {
        if(book[i] == 0) // 假设标记数组值为0代表这个数字没有选过
        {
            book[i] == 1; // 这个数字被选了，标记
            筛选下一步的数字
        }
    }

那么我们的选择什么时候结束呢？当然是我们的数字都被选完了的时候，由此我们需要加一个变量来记录我们选择的数字个数。由此我们可以架构出大致的代码：

void dfs(int step)
    {
        /*
        * 当筛选完最后一个数字时返回,
        *（注意不是9，因为第9位数字是最后一个数字，但是此时还没筛选完第9位数字）
        */
        if(step == 10)  
        {
            输出且返回
        }
        for(int i = 0; i < 10; i++) //否则继续循环筛选
        {
            if(book[i] == 0)
            {
                book[i] = 1;
                dfs(step + 1); // 筛选的步数加一
            }
        }
    }

这样的话我们把大致的代码思想已经架构出来了，但是现在还有一个问题：上面代码的book标记数组只有将数字标记为已经被选择状态的部分（book\[i\] = 1;），但是当我们下一次要筛选的时候这个数字不是用不了了吗？如果你也想到了这个问题，那么恭喜你，你已经理解了这道题的思路，在**每一轮**筛选结束之后，我们在确实要将选中的数字取消标记，这样才能进行**下一轮**的筛选**（注意是下一轮而不是下一步）**。那么，我们再加上数字取消标记的代码：

void dfs(int step)
    {
        /*
        * 当筛选完最后一个数字时返回,
        *（注意不是9，因为第9位数字是最后一个数字，但是此时还没筛选完第9位数字）
        */
        if(step == 10)  
        {
            输出且返回
        }
        for(int i = 0; i < 10; i++) //否则继续循环筛选
        {
            if(book[i] == 0)
            {
                book[i] = 1;    // 标记数字已经被使用
                dfs(step + 1);
                book[i] = 0;    // 结束这一轮的筛选之后，对用过的数字取消标记用于下一轮筛选
            }
        }
    }

题目要求我们输出啊，那么数字的储存和结果的输出在哪里进行呢，到了这一步这些都不难了，下面给出完整的代码：

#include <iostream>
    using namespace std;
    
    const int n = 10;   // 一共10个数字
    int a[n];   // 储存数字用的数组
    int count;  // 符合条件的结果总数
    int book[10];   // 标记数组，初值全为0
    
    void dfs(int step)
    {
        if(step == n)   // 如果筛选完最后一个数字
        {
            count++;    // 结果数加一
            for(int i = 0; i < n; i++)  // 输出这个符合条件的排列
            {
                cout << a[i];
            }
            cout << endl;
            return ;    // 这句返回语句最好有，不然会增加程序执行所耗费的时间
        }
        for(int i = 0; i < n; i++)
        {
            if(book[i] == 0)
            {
                book[i] = 1;    // 标记数字已经被使用过
                a[step] = i;    // 储存数字
                dfs(step + 1);  // 筛选下一步
                book[i] = 0;    // 对使用过的数字取消标记，供下一轮筛选使用
            }
        }
    }
    
    int main()
    {
        dfs(0); // 从第0步开始筛选
        cout << count << endl;  // 输出结果总数
    }

Ok了，这就是深度优先搜索最基本的模型：

/*
    * 深度优先搜索：每一次利用递归将当前情况搜索到最深处（一条道走到黑，不撞南墙不回头），然后利用循环枚举出所有当前可能的情况
    * 递归：做好当前怎么做，下一步怎么做和当前是一样的情况
    *
    * 模型：void dfs(int step)
    *       {
    *           判断边界，是否返回
    *           for(int i = 0; i < n; i++)  尝试每一种可能（有些并不会成功）
    *           {
    *              尝试成功则继续下一步递归：dfs(step + 1);
    *           }
    *           返回
    *       }
    */

运行结果：  
![这里写图片描述][SouthEast]  
好了，大功告成。  
如果对过程仍然不是很清楚可以把1、2、3一共3个数字带入代码走一遍过程就行了。如果有不正确之处还请指正。  
谢谢观看。。。

[SouthEast]: /images/20220711/79bf4f6bd6434cd19eead539de6c81c4.png