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（深度优先搜索）

基本概念

算法思想

代码框架

例题

代码实现

最新文章

热门文章