搜索与图论篇——DFS和BFS
搜索与图论篇——DFS和BFS
本次我们介绍搜索与图论篇中DFS和BFS，我们会从下面几个角度来介绍：
- DFS和BFS简介
- DFS数字排序
- DFS皇后排序
- DFS树的重心
- BFS走迷宫
- BFS八数码
- BFS图层次
首先我们先来介绍一下DFS和BFS：
- DFS：深度优先遍历算法，我们在进行算法运算时，优先将该路径的当前路径执行完毕，执行完毕或失败后向上回溯尝试其他途径
- BFS：广度优先遍历算法，我们在进行算法运算时，优先将当前路径点的所有情况罗列出来，然后根据罗列出来的情况罗列下一层
DFS和BFS的算法依据：
- 两者均以树的形式进行展开，可以采用树的模型来进行DFS和BFS演示
我们首先给出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 < n; i++) {
arr[i] = i+1;
}
dfs(0);
}
public static void dfs(int x){
// 首先判断是否可以输出
if (x == n){
for (int i=0;i < n;i++){
System.out.print(res[i]+ " ");
}
System.out.println();
}
// 开始dfs
for (int i = 0; i < n; i++) {
// 判断是否被使用，若被使用，则不能使用；若未被使用，使用并进入下一层
if (!isUsed[i]){
// 未被使用，使用并进入下一层
res[x] = arr[i];
isUsed[i] = true;
dfs(x+1);
// 下面属于回溯部分，我们需要恢复原样，这里的x已经回溯，不需要覆盖res的值
isUsed[i] = false;
}
}
}
}我们首先给出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 < n;i++){
for (int j = 0; j < n; j++) {
arr[i][j] = '.';
}
}
dfs(0,0,0);
}
// DFS
private static void dfs(int x,int y,int u) {
// y到头，换行
if(y == n){
y = 0;
x++;
}
// 老规矩判断输出条件
if (x == n){
if (u == n){
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.print(arr[i][j]);
}
System.out.println();
}
System.out.println();
}
return;
}
// 进行dfs（不选的情况，选该行的其他点位）
dfs(x, y + 1, u);
// 判断是否符合条件
if (!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n])
{
arr[x][y] = 'Q';
row[x] = col[y] = dg[x + y] = udg[x - y + n] = true;
// 进行dfs(符合条件选，继续下一步)
dfs(x, y + 1, u + 1);
row[x] = col[y] = dg[x + y] = udg[x - y + n] = false;
arr[x][y] = '.';
}
}
}
/*升级方法*/
import java.util.Scanner;
public class dfsDouble {
static final int N = 20;
// 记录数据
static int n;
static char[][] arr = new char[N][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 < n;i++){
for (int j = 0; j < n; j++) {
arr[i][j] = '.';
}
}
dfs(0);
}
// DFS
private static void dfs(int u) {
// 我们采用每行取一个的策略，这里的u就是x
if (u == n){
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.print(arr[i][j]);
}
System.out.println();
}
System.out.println();
return;
}
// 我们取满足条件的位置
for (int j = 0; j < n; j++) {
if (!col[j] && !dg[u+j] && !udg[u - j + n]){
arr[u][j] = 'Q';
col[j] = dg[u+j] = udg[u-j+n] = true;
dfs(u+1);
col[j] = dg[u+j] = udg[u-j+n] = false;
arr[u][j] = '.';
}
}
}
}我们这里利用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 < N; i++) {
h[i] = -1;
}
// 进行连接
for (int i = 0; i < n-1; i++) {
int a = scanner.nextInt();
int b = scanner.nextInt();
// 注意是无向边，我们需要双向连接
add(a,b);
add(b,a);
}
// 开始遍历
dfsMethod(1);
// 最后输出结果
System.out.println(ans);
}
// dfs操作
private static int dfsMethod(int u) {
// 连通块的最大值
int res = 0;
// 首先将自己设置为已经过点
isPassed[u] = true;
// 该点以及子类的点数(目前已包含自己点)
int sum = 1;
// 开始遍历子点
for (int i = h[u];i != -1;i = ne[i]){
// 将每个点用变量表示出来
int j = e[i];
// 如果该点没有经过,对其dfs遍历
if (!isPassed[j]){
// 遍历时需要返回sum来获得下列点的大小，为了得到ans做准备
int s = dfsMethod(j);
// 和res比较，获得连通块最大值
res = Math.max(res,s);
// 将子类点添加到sum中
sum += s;
}
}
// 我们还需要与抛弃该点后上面的点所产生的res作比较
res = Math.max(res,n-sum);
// 返回最小的ans
ans = Math.min(ans,res);
return sum;
}
// 我们需要一个单链表连接的函数
public static void add(int a,int b){
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
}我们给出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 <= n;i++){
for (int j=1;j <= m;j++){
// 输入0/1
arr[i][j] = scanner.nextInt();
// 全部设置为未pass
isPassed[i][j] = -1;
}
}
int res = bfsMethod();
System.out.println(res);
}
private static int bfsMethod() {
// 初始设置
hh = 0 ; tt = -1; //队列的头节点=0，尾节点 = 0；
isPassed[1][1] = 0; // 我们首先站在的是第一个点，所以值距离设置为0
queue[++tt] = new PII(1,1); //然后将第一个点下标存入q队列中
// 提前设置好移动方向(分别对应方向)
int[] xmove = {-1,0,1,0};
int[] ymove = {0,1,0,-1};
// 遍历queue
while (hh <= tt){
PII t = queue[hh++]; //每一次将头结点拿出来
for(int i = 0 ; i < 4 ; i ++ ) {//然后进行下一步要往哪里走，这里可能有多重选择可走
int x = t.x + xmove[i]; //这里进行x轴向量判断
int y = t.y + ymove[i];//这里进行y轴向量的判断
//如果x，y满足在地图中不会越界，然后地图上的点g是0(表示可以走)，
//然后这里是没走过的距离d是-1；
if (x > 0 && x <= n && y > 0 && y <= m && arr[x][y] == 0 && isPassed[x][y] == -1) {
//将现在可以走的点(x,y)加上上一个点计数距离的点加上一，就是现在走到的点的距离
isPassed[x][y] = isPassed[t.x][t.y] + 1;
queue[++tt] = new PII(x, y);//然后将这一个可以走的点存入队列尾
}
}
}
return isPassed[n][m]; //最后返回的是地图走到尽头最后一个位置的位置统计的距离
}
//这是一个用来存储两个坐标的类Pair
static class PII{
int x,y;
public PII(int x,int y){
this.x = x;
this.y = y;
}
}
}我们给出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 < 9 ; i ++ ){
String s = scanner.next();
start += s;
}
// 结束状况
String end = "12345678x";
// bfs循环
System.out.println(bfsMethod(start,end));
}
public static int bfsMethod(String start,String end){
// 哈希表存放字符串和对应的移动步数
HashMap<String,Integer> hashMap = new HashMap<String, Integer>();
// 队列存放字符串
Queue<String> 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<4;i++){
int a = x + xmove[i];
int b = y + ymove[i];
//如果这种情况没有超出边界
if(a >= 0 && a < 3 && b >= 0 && b < 3){
//将这种情况的字符串转化成字符数组，能够有下标进行交换
char[] arr = s.toCharArray();
//然后交换x跟没有超出边界的值进行交换，二维转成一维下标x*3+y;
swap(arr, index, a * 3 + b);
//然后将字符数组转化成字符串
String str = new String(arr);
//如果这种情况对应的value值是null，说明还没有走过
if(hashMap.get(str) == null){
//然后将这种情况对应进行上一步的距离加上1
hashMap.put(str,hashMap.get(s) + 1);
//然后将新的情况插入到队尾中
queue.offer(str);
}
}
}
}
return -1;
}
// 交换算法
public static void swap(char[] arr,int x,int y){
char temp = arr[x];
arr[x] = arr[y];
arr[y] = temp;
}
}我们这里利用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 < N; i++) {
h[i] = -1;
distance[i] = -1;
}
// 赋值
for (int i = 0;i < m;i++ ){
int a = scanner.nextInt();
int b = scanner.nextInt();
add(a,b);
}
// BFS操作
int res = bfsFind();
// 输出
System.out.println(res);
}
// bfs操作
public static int bfsFind(){
// 设置hh，tt
hh = 0;
tt = -1;
// 第一个点距离为0
distance[1] = 0;
// 将第一个点加入队列
queue[++tt] = 1;
// 开始队列循环
while (hh <= tt){
int t = queue[hh++];
// 取得该点，对其ne进行处理
for (int i = h[t]; i != -1; i = ne[i]) {
// 得到该子点，进行处理
int s = e[i];
if (distance[s] == -1){
// 如果没有经过就设置dis,并且加入队列
distance[s] = distance[t] + 1;
queue[++tt] = s;
}
}
}
return distance[n];
}
// 经典单链表添加方法
public static void add(int a,int b){
e[idx] = b;
ne[idx] = h[a];
h[a] = idx;
idx++;
}
}结束语
好的，关于搜索与图论篇的DFS和BFS算法就介绍到这里，希望能为你带来帮助~
手机扫一扫
移动阅读更方便
你可能感兴趣的文章