DFS(深度优先搜索算法)——Java实现

基本概念

深度优先搜索算法（Depth First Search，简称DFS）：一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件，搜索将回溯到发现节点v的那条边的起始节点。整个进程反复进行直到所有节点都被访问为止。属于盲目搜索,最糟糕的情况算法时间复杂度为O(!n)。

算法思想

回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

基本模板

int check(参数)
{
    if(满足条件)
        return 1;
    return 0;
}
 
void dfs(int step)
{
        判断边界
        {
            相应操作
        }
        尝试每一种可能
        {
               满足check条件
               标记
               继续下一步dfs(step+1)
               恢复初始状态（回溯的时候要用到）
        }
}   

实例问题

1.全排列

import java.util.Arrays;

public class Main {
	public static void main(String[] args) {
		int[] array = new int[] { 1, 2, 3, 3 };
		quanPai(array, 0);
	}

	public static void quanPai(int[] array, int k) {
		if (k == array.length) {
			System.out.println(Arrays.toString(array));
		}
		for (int i = k; i < array.length; i++) {
			if (isSwap(array, k, i)) {//这一步为了去重的，不懂点代码后面的链接
				swap(array, k, i);
				quanPai(array, k + 1);
				swap(array, k, i);
			}
		}
	}

	public static void swap(int[] array, int i, int j) {
		int t = array[i];
		array[i] = array[j];
		array[j] = t;
	}

	public static boolean isSwap(int[] array, int start, int end) {
		boolean sign = true;
		for (int i = start; i < end; i++) {
			if (array[i] == array[end]) {
				sign = false;
			}
		}
		return sign;
	}
}

以前总结过全排列，点开链接，看第六题：https://blog.csdn.net/qq_42570601/article/details/96748932

2.带分数

问题描述
100 可以表示为带分数的形式：100 = 3 + 69258 / 714。

还可以表示为：100 = 82 + 3546 / 197。

注意特征：带分数中，数字1~9分别出现且只出现一次（不包含0）。

类似这样的带分数，100 有 11 种表示法。

输入格式
从标准输入读入一个正整数N (N<1000*1000)

输出格式
程序输出该数字用数码1~9不重复不遗漏地组成带分数表示的全部种数。

注意：不要求输出每个表示，只统计有多少表示法！

样例输入1
100
样例输出1
11
样例输入2
105
样例输出2
6

public class DaiFenShu {
	static int n, res;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		sc.close();
		int[] data = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
		getQuanpailie(data, 0);
		System.out.println(res);
	}

	// 计算各部分结果
	private static int getNum(int[] data, int i, int j) {
		int num = 0;
		for (int k = i; k < j; k++) {
			num = num * 10 + data[k];
		}
		return num;
	}

	private static void getQuanpailie(int[] data, int k) {
		if (k == data.length) {// 判断边界
			// 将数组分为三部分
			for (int i = 1; i < data.length; i++) {
				for (int j = i + 1; j < data.length; j++) {
					int pre = getNum(data, 0, i);
					int mid = getNum(data, i, j);
					int fon = getNum(data, j, 9);

					if (mid % fon != 0)
						continue;
					if (pre + mid / fon == n)
						res++;
				}
			}
		}
		for (int j = k; j < data.length; j++) {
			{
				int t = data[k];
				data[k] = data[j];
				data[j] = t;
			}
			getQuanpailie(data, k + 1);// 回溯
			// 恢复到最初的状态
			{
				int t = data[k];
				data[k] = data[j];
				data[j] = t;
			}
		}
	}
}

3.素数环
环由N个圈组成，如图所示。将自然数1, 2、…、n分别放在每个圆中，两个相邻圆中的数字之和应该是素数。

注意：第一个圈的数字应该总是1。

输入:

n (0<n<20)

输出:

输出格式如下所示。每行代表环中的一系列圆数，从1顺时针和逆时针开始。数字的顺序必须满足上述要求。按词典顺序打印解决方案。

Sample Input:
6

Sample Output:
1 4 3 2 5 6

1 6 5 2 3 4

Sample Input:
8
Sample Output:
1 2 3 8 5 6 7 4

1 2 5 8 3 4 7 6

1 4 7 6 5 8 3 2

1 6 7 4 3 8 5 2

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class SuShuHuan {
	static int n, res;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		sc.close();
		ArrayList<Integer> list = new ArrayList<Integer>();
		for (int i = 1; i <= n; i++) {
			list.add(i);
		}
		int[] array = new int[list.size()];
		for (int i = 0; i < list.size(); i++) {
			array[i] = list.get(i);
		}
		getQuanpailie(array, 1);

	}

	// 计算各部分结果
	private static boolean isPrime(int i, int j) {
		boolean sign = false;
		int sum = i + j;
		if (sum == 2 || sum == 3 || sum == 5) {
			sign = true;
		} else if (sum % 2 != 0 && sum % 3 != 0 && sum % 5 != 0) {
			sign = true;
		}
		return sign;
	}

	private static void getQuanpailie(int[] data, int k) {
		if (k == data.length) {// 判断边界
			// 将数组分为三部分
			boolean sign = false;
			if (isPrime(1, data[data.length - 1])) {
				sign = true;
				for (int i = 1; i < data.length; i++) {// 第一个到最后一个之间的所有数
					if (!isPrime(data[i], data[i - 1])) {
						sign = false;
						break;
					}
				}
			}
			// 最后一个和第一个
			if (sign) {
				System.out.println(Arrays.toString(data));
			}
		}
		for (int j = k; j < data.length; j++) {
			// 交换
			swap(data, k, j);
			getQuanpailie(data, k + 1);// 回溯
			// 恢复到最初的状态
			swap(data, k, j);
		}
	}

	public static void swap(int[] array, int i, int j) {
		int t = array[i];
		array[i] = array[j];
		array[j] = t;
	}
}