DFS、递归（Acwing算法笔记）_递归和dfs

作者：羊村懒王 | 2024-04-10 02:34:59

踩

递归和dfs

用到的dfs的情况多为求某些情况的全排列的情况，其多用递归来实现。故dfs基本就是递归的思想；

基本的伪代码板子如下所示


#include<iostream>
using namespace std;
 
//定义输出数组和标级数组 
void dfs(){
	if()//截止条件
	{
		//输出 
		return ; 
	} 
	for(int i = 1;i<=n;++i)
	{
		if()//判断条件 
		{
			//将标级数组置为1 
			dfs(u+1,n);
			//与上面对称，将标级数组置为0 。还原现场
		}
	}
}
 
int main (){
	int n;cin>>n;
	 dfs(1,n);
	return 0;
}

下面附上图进行举例说明

上图中蓝色箭头表示for循环对兄弟结点进行访问。红箭头表示使用dfs(u+1,n)的递归和回溯的过程。黄箭头表示递归过程中不满足条件的。最后在u==n+1时将结果进行输出。

注意的是，在上述代码中，回溯后需要还原现场。也就是上面的对称的过程。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/羊村懒王/article/detail/396155