DFS（深度优先搜索）

基本概念

深度优先搜索算法（Depth First Search，简称DFS）：一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件，搜索将回溯到发现节点v的那条边的起始节点。整个进程反复进行直到所有节点都被访问为止。属于盲目搜索,最糟糕的情况算法时间复杂度为O(!n)。

算法思想

回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

代码框架

void dfs(参数){
    if(到达边界){
        执行操作;
        return;
    }
    
    尝试每种可能{
        if(满足条件){
            标记;
            dfs(参数);
            回溯;
        }
    }
}

例题

输出自然数1到3所有不重复的排列，即3的全排列，要求所产生的任一数字序列中不允许出现重复的数字。

看到这，你可能会想：这还不简单？用枚举扫一遍不就行了？
当然，如果是输出1到3的全排列，用枚举还是可以AC的，但把题目换成输出1到n的全排列（n由用户输入），枚举就用不了了。

这时，我们的dfs同学就派上用场。

代码实现

将刚才的dfs框架套一下:

#include <iostream>
#define n 3
using namespace std;

int ans[10],book[10];
void dfs(int x){
    int i;
    if(x==n+1){
        for(i=1;i<=n;i++)
            cout << ans[i] << " ";
        cout << "\n";
        return;
    }
    for(i=1;i<=n;i++)
        if(book[i]==0){
            ans[x]=i;
            book[i]=1;
            dfs(x+1);
            book[i]=0;
        }
}
int main(){
    dfs(1);
}

DFS（深度优先搜索）

原文：https://www.cnblogs.com/Return-blog/p/12287649.html