BFS(广度搜索|宽度搜索)无向图遍历(JAVA手把手深入解析)
BFS(广度搜索|宽度搜索)无向图遍历(JAVA手把手深入解析)
BFS(广度搜索|宽度搜索)无向图遍历(JAVA手把手深入解析)
目录
BFS(广度搜索|宽度搜索)无向图遍历(JAVA手把手深入解析)
前言
到了DFS与BFS这里就是一个省一的分界线了，能搞定的省一基本没有问题，当然，也有靠纯暴力进入省一的，但是几率就会小一些。这篇文章我已经将BFS拆分的很细了呢，希望能帮助大家跨过蓝桥杯的这个分水岭。 如果帮助到了你，请留下你的三连支持。
BFS广度搜索
宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。
这里与DFS就有一定的区别了，他的运转方式就是横向走遍所有的节点，虽然都是从上到下，但是横向的BFS是横向挨个找，一般会使用队列来完成BFS操作。
由于DFS的代码理解难度小一些，我先准备了DFS的文章，可以先去完成DFS学习之后咱们再来完成BFS的学习，有一个从简入繁的过程：
DFS无向图遍历(JAVA手把手深入解析)_红目香薰的博客-CSDN博客
无向图
BFS与DFS的区别通过图就很明显了，而且上面我还配了一张GIF动图，相信更容易理解了，我们通过这个图再翻译成数组。
我们用BFS输出应该是：1-2-6-3-4-7-5，我们编码完毕后测试一下。
BFS全局变量定义
1、节点
为了帮助孩子们理解，我这里使用的是拼音拼写的变量【dian】
public static String dian[] = { "1", "2", "3", "4", "5", "6", "7" };2、节点数
我们所有的操作都会依赖于这个长度来进行遍历，故而这里我单独写了一下：
public static int d_length=d.length;3、根据图创建数组
这里的创建数组图的方式与DFS是相同的，咱们图一样只是遍历的方式不同而已。我就不做其它解释了。
/**
* 图转换数组
*/
public static int[][] arr= {
{0,1,0,0,0,1,0},
{1,0,1,1,0,0,0},
{0,1,0,0,0,0,0},
{0,1,0,0,1,0,0},
{0,0,0,1,0,0,0},
{1,0,0,0,0,0,1},
{0,0,0,0,0,1,0},
};4、状态记录数组
/**
* 记录每一个节点的遍历过程，走过则记录为true
*/
public static boolean[] isfStatus;四个全局变量
这里我们共计创建了4个全局变量，依次是：
顶点、图转换数组、判断是否走过、记录每一个节点的遍历过程，走过则记录为true。
/**
* 顶点
*/
public static int d[] = { 1, 2, 3, 4, 5, 6, 7 };
/**
* 图转换数组
*/
public static int[][] arr= {
{0,1,0,0,0,1,0},
{1,0,1,1,0,0,0},
{0,1,0,0,0,0,0},
{0,1,0,0,1,0,0},
{0,0,0,1,0,0,0},
{1,0,0,0,0,0,1},
{0,0,0,0,0,1,0},
};
/**
* 顶点长度
*/
public static int d_length=d.length;
/**
* 记录每一个节点的遍历过程，走过则记录为true
*/
public static boolean[] isfStatus;这里准备的东西其实与DFS是相同的，包括图的数组绘制理论，接下来才是真正的广搜代码内容。
BFS代码
1、队列解析
这里我们要完成BFS则需要使用队列，Java中队列会使用【Queue】来完成，这个【Queue】在【LinkedList】内，我们声明的时候直接使用：
Queue<Integer> temp = new LinkedList<Integer>();来声明这个队列即可。
向队末添加元素是【offer】函数，取出第一个元素并删除是【poll】函数，我们利用队列的这两个函数就够用了。
2、广搜核心代码
广搜我们就不需要递归了，相对理解难度在于多层循环这里。我们先看一下逻辑源码：
/**
* 队列完成的广度搜索
*/
private static void BFS() {
isfStatus = new boolean[d_length];
Queue<Integer> temp = new LinkedList<Integer>();
//遍历每个节点
for (int i = 0; i < d_length; i++) {
//判断当前节点是否被访问过
if (!isfStatus[i]) {//如果没有被访问的话则将其加入队列
System.out.print(d[i] + " ");
isfStatus[i] = true;
temp.offer(i);
while (!temp.isEmpty()) {
//将最先进入队列的节点移除
int j = temp.poll();
//广度搜索子节点
for (int k = firstValue(j); k >= 0; k = nextValue(j, k)) {
if (!isfStatus[k]) {
System.out.print(d[k] + " ");
isfStatus[k] = true;
temp.offer(k);
}
}
}
}
}
}从逻辑中可以看出，首先我们还是要遍历整个节点长度，然后如果是非true就代表没有走过的路线，可以进入判断，先直接输出一下这个点，因为我们图是按照从小到大排列的故而不需要考虑点的排序。
这个需要进行队列操作了，进来循环后先排队，先一处节点后再进行广度搜索的子节点添加。当然，同时走过的路线需要修改一下状态的数组下标为true。遍历范围还是从第一个点遍历到最后一个点。
3、遍历节点
理论与DFS相同
全局控制：变量【i】，我们通过变量【i】来控制我们遍历的行数，这样就能逐一击破了。 初始点：坐标点需要从最左侧的0开始遍历，只要找到不是0的数就代表有链接点了。 下一个链接：坐标得从第N个开始遍历了，因为之前的已经遍历过了。这里的N是变量【j】。
// 返回与i相连的第一个顶点
private static int firstValue(int i) {
for (int j = 0; j < d_length; j++) {
if (arr[i][j] > 0) {
return j;
}
}
return -1;
}
// 返回与i相连的下一个顶点
private static int nextValue(int i, int j) {
for (int k = (j + 1); k < d_length; k++) {
if (arr[i][k] > 0) {
return k;
}
}
return -1;
}4、最终输出
// 测试
public static void main(String args[]) {
BFS();
}可以看到最终结果与深度搜索的目标结果是相同的，代表我们遍历是没有问题的。
完整代码对照
package com.item.action;
import java.util.LinkedList;
import java.util.Queue;
public class Demo5 {
/**
* 顶点
*/
public static int d[] = { 1, 2, 3, 4, 5, 6, 7 };
/**
* 图转换数组
*/
public static int[][] arr= {
{0,1,0,0,0,1,0},
{1,0,1,1,0,0,0},
{0,1,0,0,0,0,0},
{0,1,0,0,1,0,0},
{0,0,0,1,0,0,0},
{1,0,0,0,0,0,1},
{0,0,0,0,0,1,0},
};
/**
* 顶点长度
*/
public static int d_length=d.length;
/**
* 记录每一个节点的遍历过程，走过则记录为true
*/
public static boolean[] isfStatus;
/**
* 队列完成的广度搜索
*/
private static void BFS() {
isfStatus = new boolean[d_length];
Queue<Integer> temp = new LinkedList<Integer>();
//遍历每个节点
for (int i = 0; i < d_length; i++) {
//判断当前节点是否被访问过
if (!isfStatus[i]) {//如果没有被访问的话则将其加入队列
System.out.print(d[i] + " ");
isfStatus[i] = true;
temp.offer(i);
while (!temp.isEmpty()) {
//将最先进入队列的节点移除
int j = temp.poll();
//广度搜索子节点
for (int k = firstValue(j); k >= 0; k = nextValue(j, k)) {
if (!isfStatus[k]) {
System.out.print(d[k] + " ");
isfStatus[k] = true;
temp.offer(k);
}
}
}
}
}
}
// 返回与i相连的第一个顶点
private static int firstValue(int i) {
for (int j = 0; j < d_length; j++) {
if (arr[i][j] > 0) {
return j;
}
}
return -1;
}
// 返回与i相连的下一个顶点
private static int nextValue(int i, int j) {
for (int k = (j + 1); k < d_length; k++) {
if (arr[i][k] > 0) {
return k;
}
}
return -1;
}
// 测试
public static void main(String args[]) {
BFS();
}
}完整代码留在这里是帮助大家对照的啊，别直接复制用，这样意义就不那么高了。
总结
我们咋做蓝桥杯题的时候很多的时候都是有套路的，我们很多时候通过我们背过的一些套路去套题目也会直接出结果的，例如全排列的方法，还有很多的公式，欧几里得，欧拉等等，都是很方便的，我们其实不是算法的创造者，我们只是知识的搬运工，争取将更多的知识搬运到咱们的大脑中啊。
连续的两篇文章我们对DFS于BFS都做了一定的理解，有了这个基础我们才能更好的应对各省的省赛题目，当然，最难的题目应该还是DP类型题，所以后面我们还是需要更好的去读题，理解题，用量来积累，千万别看到难题就跑，我们可以先不搭理它，先去解决一些简单的题目，通过在简单题目中累积的解题思路来一点点摸索出解题规律，解题技巧。
3月份前没有DP分享了，3月份的时候请将各省的省赛题的前6~7题做一遍，简单的先搞定了再说难的8~10题，整个3月份就会针对8~10题进行加强训练了，那个时候简单题的意义就不大了，为了省一，加油。
腾讯云开发者
