深度优先搜索(depth-first search，简称dfs)就是递归地进行一系列操作，直到找到想要的结果或者搜到头了（无路可走）。
我对深度优先搜索的总结就是：
（1）不见南墙不回头
（2）找到以后往回走
深度优先搜索其实和我们大多数人小时候走迷宫时选择的策略非常类似。
深度优先搜索有一个很简单的例子：求n!。
int f(int n) {
if(n == 0 || n == 1) return 1;
return f(n-1) * n;
}
我们以现在ACM竞赛中一道简单的竞赛题 --
素数环 为例，来讲解深度优先搜索。
点此进入题目描述
这道题目的意思是，找到所有的素数环输出。
我们可以写下对应的伪代码：
function dfs(深度) {
if(深度 == 1) {
第1个点确定为1;
第1个点标记访问过了;
dfs(深度+1);
撤销第1个点的标记;
}
else {
for(i = 1 to n) {
if(i加上第（深度-1）个点的值是素数 and i没有被访问过) {
第（深度）个点确定为i;
第i个点标记访问过了;
dfs(深度+1);
撤销第i个点的标记;
}
}
}
if(深度 > n) {
if(第（深度-1）个点的值+1是素数) {
输出这串素数环;
}
return;
}
return;
}
简单了解了深度优先搜索，并且差不多看懂了这个伪代码，我们就可以用代码实现一下了。下面是完整的Java代码：
import java.util.Scanner;
public class Main {
public static boolean isprime(int n) {
if(n ==2 || n == 3 || n == 5 || n == 7 || n == 11 || n == 13 || n == 17 || n == 19 ||
n == 23 || n == 29 || n == 31 || n == 37 || n == 41)
return true;
return false;
}
private static boolean[] vis = new boolean[22];
private static int[] ans = new int[22];
private static Scanner in;
public static void dfs(int dep,int n) {
for(int i=1;i<=n;i++) {
if(vis[i] == false && isprime(ans[dep-1] + i)) {
vis[i] = true;
ans[dep] = i;
if(dep == n && isprime(1+i)) {
System.out.print(ans[1]);
for(int i1=2;i1<=n;i1++) System.out.print(" " + ans[i1]);
System.out.println("");
vis[i] = false;
return;
} else if(dep == n) {
vis[i] = false;
return;
}
dfs(dep+1, n);
vis[i] = false;
}
}
return;
}
public static void main(String[] args) {
in = new Scanner(System.in);
int cnt = 0;
while(in.hasNext()) {
int n = in.nextInt();
for(int i=1;i<=n;i++) vis[i] = false;
cnt ++;
System.out.println("Case " + cnt + ":");
vis[1] = true;
ans[1] = 1;
dfs(2, n);
System.out.println("");
}
}
}
递归地一种很好玩的现象：德罗斯特效应
posted on 2015-03-07 20:47
marchalex 阅读(184)
评论(0) 编辑 收藏 所属分类:
java小程序