深度優(yōu)先搜索(depth-first search，簡稱dfs)就是遞歸地進行一系列操作，直到找到想要的結(jié)果或者搜到頭了（無路可走）。
我對深度優(yōu)先搜索的總結(jié)就是：
（1）不見南墻不回頭
（2）找到以后往回走
深度優(yōu)先搜索其實和我們大多數(shù)人小時候走迷宮時選擇的策略非常類似。
深度優(yōu)先搜索有一個很簡單的例子：求n!。
int f(int n) {
if(n == 0 || n == 1) return 1;
return f(n-1) * n;
}
我們以現(xiàn)在ACM競賽中一道簡單的競賽題 --
素數(shù)環(huán) 為例，來講解深度優(yōu)先搜索。
點此進入題目描述
這道題目的意思是，找到所有的素數(shù)環(huán)輸出。
我們可以寫下對應的偽代碼：
function dfs(深度) {
if(深度 == 1) {
第1個點確定為1;
第1個點標記訪問過了;
dfs(深度+1);
撤銷第1個點的標記;
}
else {
for(i = 1 to n) {
if(i加上第（深度-1）個點的值是素數(shù) and i沒有被訪問過) {
第（深度）個點確定為i;
第i個點標記訪問過了;
dfs(深度+1);
撤銷第i個點的標記;
}
}
}
if(深度 > n) {
if(第（深度-1）個點的值+1是素數(shù)) {
輸出這串素數(shù)環(huán);
}
return;
}
return;
}
簡單了解了深度優(yōu)先搜索，并且差不多看懂了這個偽代碼，我們就可以用代碼實現(xiàn)一下了。下面是完整的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("");
}
}
}
遞歸地一種很好玩的現(xiàn)象：德羅斯特效應
posted on 2015-03-07 20:47
marchalex 閱讀(198)
評論(0) 編輯 收藏 所屬分類:
java小程序