深度优先搜索（DFS）——回溯法_dfs全排列回溯思路

1、深度优先搜索（DFS）

假设我们在一个迷宫里，以当前的位置为起点，沿着一条路向前走，但凡碰到岔道口时，选择其中的一个岔路前进。如果选择的这个岔路口存在新的岔道口，选择另一个岔路前进。如果岔路口存在心得岔道口，那么仍然按上面的方法枚举新岔道口的每一个岔道。这样，只要迷宫存在出口，那么这个方法一定能找到它。
碰到岔道口时，总是以“深度”作为前进的关键词，不碰到死胡同就不回头。这种搜索的方法被称为深度优先搜索。

示例：pandas 是基于NumPy 的一种工具，该工具是为了解决数据分析任务而创建的。

1.1DFS——回溯法

实现步骤：递归

例：全排列 以3！为例：

第一位可以先填1，继续填下一位，有两个岔路2、3，我们先选择走2这条岔路，再填下一位，只可以填3，此时三位已全部填完，返回到距离最近的上一个岔路口，选择另外的新岔路——3，以此方法继续往前走……

实现代码：

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

const int N=10;
int a[N];
int n;
bool flag[N]={0};

void dfs(int k){
	if(k>n){      //停止搜索 
		for(int i=1;i<=n;i++) cout<<a[i]<<" ";//并打印所有 
		cout<<endl;
		return ;		
	}
	for(int i=1;i<=n;i++){
		if(flag[i]==0){
			a[k]=i;
			flag[i]=1;
			dfs(k+1);//填完上一位，就填下一位 
			flag[i]=0;//k>n后即 k位全部填完，心得一轮所有数字都未使用过，表记清零 
		}
	} 
} 

int main(){
	cin>>n;
	dfs(1);
	return 0;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

运行结果