深度優先搜索(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 閱讀(195)
評論(0) 編輯 收藏 所屬分類:
java小程序