搜索与图论篇——DFS和BFS
搜索与图论篇——DFS和BFS
本次我们介绍搜索与图论篇中DFS和BFS，我们会从下面几个角度来介绍：
- DFS和BFS简介
- DFS数字排序
- DFS皇后排序
- DFS树的重心
- BFS走迷宫
- BFS八数码
- BFS图层次
DFS和BFS简介
首先我们先来介绍一下DFS和BFS：
- DFS：深度优先遍历算法，我们在进行算法运算时，优先将该路径的当前路径执行完毕，执行完毕或失败后向上回溯尝试其他途径
- BFS：广度优先遍历算法，我们在进行算法运算时，优先将当前路径点的所有情况罗列出来，然后根据罗列出来的情况罗列下一层
DFS和BFS的算法依据：
- 两者均以树的形式进行展开，可以采用树的模型来进行DFS和BFS演示
DFS数字排序
我们首先给出DFS的一元问题：
- 给定一个整数n,将数字1∼n排成一排，将会有很多种排列方法。
- 现在，请你按照字典序将所有的排列方法输出。
问题解析：
/*一元问题解析*/
我们目前采用DFS算法运算，我们需要一次得到数据，然后回溯
那么我们目前的问题就是：
- 如何判断DFS算法结束：我们只需要记录遍历到第几个数字然后与之判断是否相等，若相等表示结束
- 如何得知当前数字已经使用：我们只需要单列一个数组来记录该数是否被使用即可
我们给出算法代码：
import java.util.Scanner;
public class Main {
public static final int N = 10;
// 存放数据
static int n;
static int[] arr = new int[N];
static int[] res = new int[N];
// 判断是否被使用
static boolean[] isUsed = new boolean[N];
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
for (int i = 0; i DFS皇后排序
我们首先给出DFS的二元问题：
- n−皇后问题是指将n个皇后放在n×n的国际象棋棋盘上，使得皇后不能相互攻击到
- 即任意两个皇后都不能处于同一行、同一列或同一斜线上。
- 现在给定整数 nn，请你输出所有的满足条件的棋子摆法。
问题解析：
/*原始方法*/
首先我们采用最基本的思想，我们采用一元思想，针对n*n的棋盘上的每个位置都进行DFS操作，并对其判断是否满足条件
在满足条件的位置上我们放上皇后并记录数目，如果到最后皇后的数量足够，那么我们就将他输出
/*升级方法*/
我们已经知道他们不能放在同一行和同一列，我们直接采用for将一行中的一个位置选出来，然后对每行DFS操作并判断是否满足条件
在满足条件的位置上我们放上皇后并记录数目，如果到最后皇后的数量足够，那么我们就将他输出
/*注意点*/
我们的n-皇后问题还需要保证对角线上不具有相同棋子
我们采用二元函数的函数y=x以及y=n-x来给出对角线的位置
我们给出算法代码：
/*原始方法*/
import java.util.Scanner;
public class dfsDouble {
static final int N = 20;
// 记录数据
static int n;
static char[][] arr = new char[N][N];
// 记录行，列，对角线，反对角线
static boolean[] row = new boolean[N];
static boolean[] col = new boolean[N];
static boolean[] dg = new boolean[2*N-1];
static boolean[] udg = new boolean[2*N-1];
// 主函数
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
for (int i = 0;i DFS树的重心
我们这里利用DFS来求解一道难题：
- 给定一颗树，树中包含 nn 个结点（编号 1∼n1∼n）和 n−1n−1 条无向边。
- 请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。
- 重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。
我们给出一个简单示例来表明重心：
我们来简单介绍一下：
/*输入数据*/
// 第一个是操作次数，然后后面成对书写，表示两者相连
9
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6
/*重心介绍*/
我们上图中的黑笔书写部分是由上述数据所搭建出来的无向图，我们上面用树的形式写出
我们的棕笔部分是指去掉该点之后，剩余的联通点分块的个数中的最大块，我们要测试全部的点位，并给出这些最大块的最小快
思路分析：
/*思路分析*/
首先我们要遍历所有的点，一一求解该点删除后的最大块
我们删除该点后，其连通区域主要分为两部分：该点的子点，该点的上一个点的个数去除该点以及该点子类的个数
我们给出相关代码：
import java.util.Scanner;
public class Main {
final static int N = 100010;
// 首先我们用单链表模拟图
static int n;
static int idx;
static int[] h = new int[N];
static int[] e = new int[N*2];
static int[] ne = new int[N*2];
// 判定是否已经经过
static boolean[] isPassed = new boolean[N*2];
// 最大值
static int ans = N;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
// 将头节点设为-1，方便判断
for (int i = 1; i BFS走迷宫
我们给出BFS走迷宫题目：
- 给定一个n×m的二维整数数组，用来表示一个迷宫，数组中只包含0或1，其中0表示可以走的路，1表示不可通过的墙壁。
- 最初，有一个人位于左上角 (1,1)处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。
- 请问，该人从左上角移动至右下角 (n,m)处，至少需要移动多少次。
- 数据保证 (1,1)处和 (n,m)处的数字为0，且一定至少存在一条通路。
问题解析：
/*BFS运作*/
首先我们要知道BFS的运作形式
首先我们BFS是根据距离或长度来进行分类递增
那么在走迷宫时，我们距离为n+1的位置肯定是由距离为n的位置的上下左右方向的位置
那么我们就可以采用一个队列来进行装配，我们将获得的可走的点位和距离保存进去，然后根据这个点位和距离推算下一个点位和距离
我们给出算法代码：
import java.util.Scanner;
public class bfs {
static final int N = 100;
// 存放数据，存放是否使用
static int n,m,hh,tt;
static int[][] arr = new int[N][N];// 地图
static int[][] isPassed = new int[N][N];// 是否经过,若经过修改为距离
static PII[] queue = new PII[N*N];// 队列
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
m = scanner.nextInt();
for (int i=1;i 0 && x 0 && y BFS八数码
我们给出BFS八数码题目：
- 在一个3×3的网格中，1∼8这 88 个数字和一个
x恰好不重不漏地分布在这 3×3的网格中。 - 在游戏过程中，可以把
x与其上、下、左、右四个方向之一的数字交换（如果存在）。
我们需要将八数码从下列形式变成顺序形式：
/*原八数码*/
1 2 3
x 4 6
7 5 8
/*完善八数码*/
1 2 3
4 5 6
7 8 x
/*变化顺序*/
1 2 3 1 2 3 1 2 3 1 2 3
x 4 6 4 x 6 4 5 6 4 5 6
7 5 8 7 5 8 7 x 8 7 8 x
问题解析：
/*八数码问题解析*/
我们这里要计算最小的移动步数，那么我们就需要采用BFS来计算最近的
其实和之前的走迷宫非常相似，我们将x与上下左右四个方向的数进行对换，然后比较是否为最终结果即可
我们给出算法代码：
import java.util.*;
public class bfs {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 开始状况
String start = "";
for(int i = 0 ; i hashMap = new HashMap();
// 队列存放字符串
Queue queue = new LinkedList();
// 存放第一个点(还未开始，启动步数为0)
hashMap.put(start,0);
queue.add(start);
while (!queue.isEmpty()){
// 将head数据拿出来
String s = queue.poll();
// 首先判断是否符合条件
if (s.equals(end)) return hashMap.get(s);
// 找到x坐标
int index = s.indexOf("x");
// 计算对应位置
int x = index/3;
int y = index%3;
// 然后上下左右移动判断
int[] xmove = {1,0,-1,0};
int[] ymove = {0,1,0,-1};
for (int i=0;i= 0 && a = 0 && b BFS图层次
我们这里利用BFS来求解一道难题：
- 给定一个n个点m条边的有向图，图中可能存在重边和自环。
- 所有边的长度都是1，点的编号为1∼n。
- 请你求出1号点到n号点的最短距离，如果从1号点无法走到n号点，输出 −1。
我们采用BFS来逐层递进，其原理其实和前面两道题相同：
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class bfsssss {
final static int N = 100010;
// 单链表模拟图
static int n,m;
static int hh,tt;
static int idx;
static int[] h = new int[N];
static int[] e = new int[N];
static int[] ne = new int[N];
// 距离存储以及队列
static int[] distance = new int[N];
static int[] queue = new int[N];
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
m = scanner.nextInt();
// 初始化
for (int i = 1; i 结束语
好的，关于搜索与图论篇的DFS和BFS算法就介绍到这里，希望能为你带来帮助~
文章来源于互联网：搜索与图论篇——DFS和BFS
THE END
二维码