通过后续的题目希望大家明白,dfs不仅仅是对图的遍历,他还有很多用法。
DFS进阶1——回溯
先说一下回溯的板子
dfs(){
for(......){
标记信息
dfs()
撤销标记
}
}
回溯模板——递归实现排列型枚举
题目分析
其实就是对1~n的数字全排列,这里就可以用dfs去做,1~n全排列我其实是确定每一个位置我应该放哪一个数字,那么dfs的时候就是对位置dfs,dfs(1)表示我现在要选择一个数放在第一个位置,那么可以选择的范围是1~n,
for(int i = 1;i <= n;i++)
且这个数之前没有被选过,那么我们就要用一个数组book[i]标记一下,book[i]=1表示这个数已经被选走了,那么我就不能再选这个数了。
for(int i = 1;i <= n;i++){
if(book[i]==1) continue;
}
当我遍历到dfs(n+1)时说明我前n个位置都安排完了,那么我就要输出此时的一个排列,我需要知道我此时选出来的数的排列,那么也可以考虑用一个变量保存,这里我使用的是队列。
if(k==n+1) {
ArrayDeque<Integer> queueTemp = new ArrayDeque<Integer>();
queueTemp.addAll(queue);
while(!queueTemp.isEmpty()) {
System.out.print(queueTemp.pollFirst() + " ");
}
System.out.println();
return;
}
当我选择数i作为当前位置的数时,我要标记这个数已经被选择了并且把它放入队列,这个位置选好后,我要继续选择下一个位置,所以dfs(k+1)
for(int i = 1;i <= n;i++) {
if(book[i]==1) continue;
book[i]=1;
queue.addLast(i);
dfs(k+1);
}
当我从dfs退出后再次回来,说明我要尝试选择其它数了,那么我要把选这个数做的标记都撤销,包括,book数组对应位置置为0和把这个数从队列里面拿出来。
for(int i = 1;i <= n;i++) {
if(book[i]==1) continue;
book[i]=1;
queue.addLast(i);
dfs(k+1);
book[i]=0;
queue.pollLast();
}
题目代码
import java.util.ArrayDeque;
import java.util.Scanner;
public class Main{
static ArrayDeque<Integer> queue = new ArrayDeque<Integer>();
static int book[];
static int n;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
book = new int[n+1];
dfs(1);
}
private static void dfs(int k) {
if(k==n+1) {
ArrayDeque<Integer> queueTemp = new ArrayDeque<Integer>();
queueTemp.addAll(queue);
while(!queueTemp.isEmpty()) {
System.out.print(queueTemp.pollFirst() + " ");
}
System.out.println();
return;
}
for(int i = 1;i <= n;i++) {
if(book[i]==1) continue;
book[i]=1;
queue.addLast(i);
dfs(k+1);
book[i]=0;
queue.pollLast();
}
}
}
代码执行过程模拟
因为初学者对递归不理解,再加上回溯更难理解,所以这里对这个代码进行模拟。以n=3为例,也就是待排列的数字为1,2,3。
上图没有写完,只写了一部分,下图是另一种形式,全都写了完了。
标签:排列,进阶,int,dfs,queue,book,DFS,ArrayDeque,queueTemp From: https://blog.csdn.net/qq_53237241/article/details/136934338