DFS(深度优先搜索算法) |
您所在的位置：网站首页 › java中树的实现 › DFS(深度优先搜索算法) |
DFS(深度优先搜索算法)
|
基本概念
深度优先搜索算法（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 //这一步为了去重的，不懂点代码后面的链接 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 sign = false; } } return sign; } }
2.带分数 问题描述 100 可以表示为带分数的形式：100 = 3 + 69258 / 714。 还可以表示为：100 = 82 + 3546 / 197。 注意特征：带分数中，数字1~9分别出现且只出现一次（不包含0）。 类似这样的带分数，100 有 11 种表示法。 输入格式 从标准输入读入一个正整数N (N 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 if (k == data.length) {// 判断边界 // 将数组分为三部分 for (int i = 1; i 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 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分别放在每个圆中，两个相邻圆中的数字之和应该是素数。 输入: n (0 Scanner sc = new Scanner(System.in); n = sc.nextInt(); sc.close(); ArrayList list = new ArrayList(); for (int i = 1; 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 sign = false; break; } } } // 最后一个和第一个 if (sign) { System.out.println(Arrays.toString(data)); } } for (int j = k; j int t = array[i]; array[i] = array[j]; array[j] = t; } } |
以前总结过全排列，点开链接，看第六题：https://blog.csdn.net/qq_42570601/article/details/96748932
注意：第一个圈的数字应该总是1。【本文地址】
今日新闻 |
推荐新闻 |