Java数据结构与算法----搜索篇（DFS与BFS）

一.概念

DFS（Depth First Search）深度优先搜索和BFS（Breadth First Search）广度优先搜索是两种广泛应用于搜索和遍历算法中的基本技术。这两种算法都涉及到搜索数据结构中的节点。这里我们以二叉树为例，简单地图解一下两者的区别。（当然它们并不止应用于二叉树，这里仅以遍历二叉树为例来讲述两者算法上的逻辑）

1.1.DFS

DFS（Depth First Search）深度优先搜索，其算法思想是从二叉树的根结点开始向下探索，尽可能深地搜索到最底层的节点，然后回溯到上一层，依次向上搜索

这是一个二叉树，按照DFS算法的顺序，搜索的路径是1-2-4-5-3-6-7-8。可以看到，在深度优先搜索中，我们从根开始，沿着左子树一直向下搜索，直到找到叶子节点或者没有更多的未探索节点为止。一旦我们找到一个叶节点，我们会回溯到该节点的上一个节点，继续搜索它的右子树，重复这个过程，直到我们找到整个树。接下来我们用一小段代码来实现这个过程

    public void DFS(Tree tree){if(tree != null){System.out.println(tree.val);DFS(tree.left); //遍历左子树DFS(tree.right); //遍历右子树}}

1.2.BFS

BFS是广度优先搜索算法，与DFS相反，它先从根节点开始，遍历每一层的所有节点，然后逐层向下搜索，直到找到目标节点。

在上图中，我们的搜索路径从根节点开始，先访问1，然后向下一层，逐个遍历2和5，然后再向下一层，遍历4、3、7，最后遍历6、8。所以怎么实现这种遍历呢？我们一般使用队列来实现哦，我们都知道，队列是先进先出的表，bfs的步骤如下：

① 创捷一个队列 queue

② 将根节点1放入queue

③ 弹出queue的队首 tree

④ 如果左右子树非空，将tree的左右子树分别放入队列queue中

⑤ 重复③ ④ 一直到queue为空，得到的顺序就是二叉树的bfs遍历

代码实现如下：

    public static void BFS(Tree tree){Queue<Tree> queue = new LinkedList<>();queue.add(tree);while(!queue.isEmpty()){Tree now = queue.poll();System.out.println(now.val);if(now.left != null){queue.add(now.left);}if(now.right != null){queue.add(now.right);}}}

二.dfs算法例题

2.1.dfs例题1. 逗志芃的暴走

问题描述

　　逗志芃是有妹子的现充，但是有时候妹子就是烦恼。因为逗志芃太逗了，所以这段时间妹子对逗志芃发动了技能无理取闹，妹子要去玩很多的景点。由于逗志芃之前抽机花费了太多的时间，不久以后又要微积分考试了，所以现在被妹子搞成暴走状态了。但是妹子永远是上帝，所以逗志芃只能带妹子出去玩，不过为了节约时间，他希望找到一条花费时间最少的一次性游览线路。

输入格式

　　第一行1个数n，表示逗志芃所在的城市有多少个景点，接下来是一个n*n的矩阵。a(i，j)表示i号景点到j号景点的路上花费的时间是多少。

　　接下来是一个数m，表示逗志芃妹子要去去的景点数目。由于妹子在无理取闹，所以可能会有重复的景点，不过只要去一次就可以了。接下来是m个数，就是妹子要去的景点编号。

输出格式

　　一个数，最少的花费时间。

样例输入

0 1 2

1 0 3

2 3 0

2 3 1

样例输出

数据规模和约定

　　0<n<=30，0<m<=20，时间<=1000000

题解思路：这道题使用了folyd算法和dfs算法，具体看代码

package 蓝桥杯;import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;public class 逗志芃的暴走 {private static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));private static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));private static boolean is[];private static int num[] ,ans,index ,map[][],n; //要去的地点数组private static void dfs(int pi,int length,int size){if(size == index){ //如果等于个数ans = Math.min(ans, length);return;}if(length > ans){ //如果大于ans了，没必要再找了，因为再找只会更大return;}for(int i = 0;i < index;i++){if(!is[num[i]]){is[num[i]] = true;dfs(num[i],length + map[pi][num[i]],size+1 );  //加上之后递归is[num[i]] = false;}}}public static void main(String[] args) {Scanner cin = new Scanner(System.in);n = cin.nextInt();map = new int[n+1][n+1];for(int i = 1;i<=n;i++){for(int j = 1;j<=n;j++){map[i][j] = cin.nextInt();}}floyd();is = new boolean[n+1];num = new int[n+1];index = 0;int m = cin.nextInt();for(int i = 0;i<m;i++){int pi = cin.nextInt();if(!is[pi]){is[pi] = true;num[index++] = pi;}}ans = Integer.MAX_VALUE; //最短路径Arrays.fill(is,false);dfs(0,0,0);System.out.println(ans);}private static void floyd() {for(int k = 1;k <= n; k++){for(int i = 1;i<=n;i++){for(int j = 1 ;j<= n ;j++){if(map[i][j] > map[i][k] + map[k][j]){map[i][j] = map[i][k] + map[k][j];}}}}}
}

2.2.dfs例题2. 低阶行列式计算

问题描述

　　给出一个n阶行列式(1<=n<=9)，求出它的值。

输入格式

　　第一行给出两个正整数n,p；

　　接下来n行，每行n个数，表示行列式，数据保证行列式中每个数绝对值不超过2*10^9。

输出格式

　　一个数表示行列式的值，答案对p取余(余数需要是非负数)。

样例输入

2 2

5 -4

2 -1

样例输出

部分数据范围

　　对于20%的数据n<=2

　　对于40%的数据n<=3

　　对于100%的数据n<=9,p<=40000。

对于行列式的计算，如果不懂得可以去看一哈线性代数，里面的行列式是这么计算的捏？

我们以这个行列式为例：

$\text{[math]}$ = a11a22a33+a12a23a31+a13a21a32−a13a22a31−a12a21a33−a11a23a32

这里的加法和减法是根据逆序对是否为偶数判断的

序号	项	排列组合	逆序对
1	+a11a22a33	1 2 3	0
2	+a12a23a31	2 3 1	2
3	+a13a21a32	3 1 2	2
4	−a13a22a31	3 2 1	3
5	−a12a21a33	2 1 3	1
6	−a11a23a32	1 3 2	1

也就是说，我们的题目变成了求n的全排列了咯。直接用dfs全排就好啦

需要注意的是，Java的% 会有负数。。。题目要正数的没所以要在最后处理一哈

package 蓝桥杯刷题;import java.util.Scanner;/*** @Author: stukk* @Description: TODO* @DateTime: 2023-03-22 19:57**/
public class 低阶行列式计算 {private static int n;private static long num[][],ans = 0L,p;private static boolean is[];public static void main(String[] args) {Scanner cin = new Scanner(System.in);n = cin.nextInt();p = cin.nextLong();num = new long[n][n];for(int i = 0;i<n;i++){for(int j = 0;j<n;j++){num[i][j] = cin.nextLong();}}is = new boolean[n];dfs(0,0,new int[n]);long answer = ans % p;if(answer >= 0){System.out.println(answer);}else{System.out.println(p + answer);}}private static void dfs(int size,int index,int number[]){if(size == n){long add = 1;for(int i = 0;i<n;i++){add = add % p * num[i][number[i]] % p;add %= p;}if(ok(number)){ans = ans % p + add % p;}else{ans = ans % p - add % p;}return ;}for(int i = 0;i<n;i++){if(!is[i]){number[index] = i;is[i] = true;dfs(size+1,index+1,number);is[i] = false;}}}private static boolean ok(int[] num) {int cnt = 0;for(int i = 0;i<n;i++){for(int j = 0;j<i;j++){if(num[j] > num[i]){cnt ++;}}}if(cnt % 2 == 0){return true; // 加法}else{return false; //减法}}
}

2.3.dfs例题3.单词接龙

问题描述

　　单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如 beast和astonish，如果接成一条龙则变为beastonish，另外相邻的两部分不能存在包含关系，例如at 和 atide 间不能相连。

输入格式

　　输入的第一行为一个单独的整数n (n<=20)表示单词数，以下n 行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在.

输出格式

　　只需输出以此字母开头的最长的“龙”的长度

样例输入

　　touch

　　cheat

　　choose

　　tact

样例输出

样例说明

　　连成的“龙”为atoucheatactactouchoose

这里需要查找两个字符串是不是有重叠的地方：

    private static int find(String p,String s){for(int i = 1;i<s.length() && i < p.length();i++){if(p.substring(p.length()-i,p.length()).equals(s.substring(0,i))){return i;}}return -1;}

然后返回最小的相同长度，然后在dfs中，判断是不是重合，重合的话就加入递归函数中，并且保持每个单词的使用次数要小于2

package 蓝桥杯刷题;import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.PrintWriter;/*** @Author: stukk* @Description: TODO* @DateTime: 2023-03-22 21:22**/
public class 单词接龙 {private static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));private static int n,ans = 0,is[];private static String str[];public static void main(String[] args) throws Exception{String p = bf.readLine();n = Integer.parseInt(p);str = new String[n];for(int i = 0;i<n;i++){str[i] = bf.readLine();}is = new int[n];char head = bf.readLine().charAt(0);boolean ok = false;for(int i = 0;i<n;i++){if(head == str[i].charAt(0)){ok = true;break;}}if(!ok){System.out.println(0);return ;}dfs(true,head+"");System.out.println(ans);}private static int find(String p,String s){for(int i = 1;i<s.length() && i < p.length();i++){if(p.substring(p.length()-i,p.length()).equals(s.substring(0,i))){return i;}}return -1;}private static void dfs(boolean isHead,String head) {if(isHead){for(int i = 0;i<n;i++){if(head.charAt(0) == str[i].charAt(0) && is[i] < 2){is[i]++;dfs(false, str[i]);is[i]--;}}}else{for(int i = 0;i<n;i++){int pi = find(head,str[i]);if(pi == -1 || is[i] >= 2){continue;}else{is[i] ++;dfs(false,head + str[i].substring(pi));is[i] --;}}}ans = Math.max(head.length(),ans);}
}/*
5
at
touch
cheat
choose
tact
a*/

三、bfs算法例题

3.1.P1135 奇怪的电梯 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

这道题最短路径的问题可以使用bfs来解决，我们先把A楼放入队列中，然后每次从队列中取出队首节点，将它所能到达的点加入队列，并且同时更新按钮次数，如果到了B楼，我们就直接跳出循环，这时候按钮次数就是答案了。

import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;
import java.util.Scanner;/*** @Author: stukk* @Description: TODO* @DateTime: 2023-03-22 22:26**/
public class Main {private static class stu{int flour; //当前楼层int button; //按钮的次数@Overridepublic boolean equals(Object o) {if (this == o) return true;if (o == null || getClass() != o.getClass()) return false;stu stu = (stu) o;return flour == stu.flour && button == stu.button;}@Overridepublic int hashCode() {return Objects.hash(flour, button);}public stu(int flour, int button) {this.flour = flour;this.button = button;}}public static void main(String[] args) {Scanner cin  =new Scanner(System.in);int n = cin.nextInt();int a = cin.nextInt();int b=  cin.nextInt();int num[] = new int[n+1];for(int i = 1;i <= n;i++){num[i] = cin.nextInt();}Queue<stu> Q = new LinkedList<>();Q.add(new stu(a,0));int ans = -1;boolean is[] = new boolean[n+1];while(!Q.isEmpty()){stu now = Q.poll();if(now.flour == b){ans = now.button;break;}int up = now.flour + num[now.flour];if(up > 0 && up <= n && !is[up]) {is[up] = true;Q.add(new stu(up,now.button+1));}int down = now.flour - num[now.flour];if(down > 0 && down <= n && !is[down]){is[down] = true;Q.add(new stu(down,now.button+1));}}System.out.println(ans);}
}