算法之广度优先搜索算法(又称宽度优先搜索算法)
程序员文章站
2022-05-20 20:26:18
...
1.广度优先搜索算法简介
宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。
2.实现原理
- 广度优先搜索使用
队列（queue）来实现，整个过程也可以看做一个倒立的树形： - 1、把根节点放到
队列的末尾。 - 2、每次从
队列的头部取出一个元素，查看这个元素所有的下一级元素，把它们放到队列的末尾。并把这个元素记为它下一级元素的前驱。 - 3、找到所要找的元素时结束程序。
- 4、如果遍历整个树还没有找到，结束程序。
3.例题(深度优先搜索例题中的寻宝)
5,0,1,0
0,0,0,0
0,0,1,0
0,1,9,0
0,0,0,1
//5表示当前寻宝人所在的位置，9表示寻宝地点,1表示路障，0表示可走路线
4.创建实体类用来存放坐标和步数
当前的标记类
Note中的内容：
/**
* @description 标记类，用来标记当前的位置，和已走的步数
* @author hy
* @date 2019-08-19
*/
public class Note {
private int x;//横坐标
private int y;//纵坐标
private int step;//步数
public int getX() {
return x;
}
public void setX(int x) {
this.x = x;
}
public int getY() {
return y;
}
public void setY(int y) {
this.y = y;
}
public int getStep() {
return step;
}
public void setStep(int step) {
this.step = step;
}
public Note(int x, int y, int step) {
super();
this.x = x;
this.y = y;
this.step = step;
}
public Note() {
super();
// TODO Auto-generated constructor stub
}
}
5.实现一(使用数组实现)
/**
* @description 测试广度优先搜索算法(又称宽度优先搜索算法)
* @author hy
* @date 2019-08-19
*/
public class BreadthFirstSearch {
/**
* 模拟实现：地图寻宝，使用数组实现
*/
int row = 5, col = 4;//定义地图的长度和宽度
int startX = 1, startY = 1;//定义用户所在的位置
int treasureX=4, treasureY=3;//定义宝物的位置
int moveX, moveY;//定义移动的坐标
int endFlag;//定义结束的标记
int head, tail;//head表示队列的头部，tial表示队列的尾部
private Note[] que = new Note[(row+1)*(col+1)];//初始化存储当前
int[][] map = new int[row+1][col+1];// 用来存储地图
int[][] flags = new int[row+1][col+1];// 用来标记状态
// 定义走的方位
int[][] next = { { 0, 1 }, // 向右走
{ 1, 0 }, // 向下走
{ 0, -1 }, // 向左走
{ -1, 0 } // 向上走
};
{
// 队列初始化
for (int i = 0; i < que.length; i++) {
que[i] = new Note();
}
//初始化路障
map[1][3] = 1;// 0表示没有路障,1表示路障
map[3][3] = 1;
map[4][2] = 1;
map[5][4] = 1;
}
//队列初始化
public void init() {
head = 1;//队列的头
tail = 1;//队列的尾部
// 第一步将{1，1}加入队列，
que[tail].setX(startX);
que[tail].setY(startY);
que[tail].setStep(0);
tail++;
flags[startX][startY] = 1;//并标记{1，1}已经走过了
endFlag = 0;//初始化结束标记
}
public void bfs() {
init();
while (head < tail) {
Note poll = queue.poll();
for (int i = 0; i <= 3; i++) {
//设置当前的需要移动的位置
moveX = que[head].getX() + next[i][0];
moveY = que[head].getY() + next[i][1];
// 判断是否越界
if (moveX < 1 || moveX > row || moveY < 1 || moveY > col) {
continue;
}
// 再判断是否为障碍物，或者已经走过了
if (map[moveX][moveY] == 0 && flags[moveX][moveY] == 0) {
// 如果满足上面的条件，将{1，2}入队，并标记该点已经走过
flags[moveX][moveY] = 1;
// 插入新的点到队列中
que[tail].setX(moveX);
que[tail].setY(moveY);
que[tail].setStep(que[head].getStep() + 1);// 步数是前面的步数+1
System.out.println("moveX:"+moveX+",moveY:"+moveY);//输出每次搜索的下标
tail++;//这里的表示可以走在标记为0的位置，当前的尾部不停的后移
}
// 表示到达了目的地，任务结束，退出循环
if (moveX == treasureX && moveY == treasureY) {
endFlag = 1;
System.out.println(que[tail-1].getStep()); //输出所需要的步数
break;
}
}
if (endFlag == 1) {
break;
}
head++;//每一次都会将头向后部移动
}
}
@Test
public void print() {
for (int i = 1; i < map.length; i++) {
for (int j = 1; j < map[i].length; j++) {
System.out.print(map[i][j]);
if (j < map[i].length - 1) {
System.out.print(",");
}
}
System.out.println();
}
}
public static void main(String[] args) {
BreadthFirstSearch bfs=new BreadthFirstSearch();
bfs.bfs();
}
}
6.实现二(使用队列实现)
/**
* @description 测试广度优先搜索算法(又称宽度优先搜索算法)
* @author hy
* @date 2019-08-19
*/
public class BreadthFirstSearch {
/**
* 模拟实现：地图寻宝：使用队列实现
*/
int row = 5, col = 4;//定义地图的长度和宽度
int startX = 1, startY = 1;//定义用户所在的位置
int treasureX=4, treasureY=3;//定义宝物的位置
int moveX, moveY;//定义移动的坐标
int endFlag;//定义结束的标记
int head, tail;//head表示队列的头部，tial表示队列的尾部
Queue<Note> queue=new LinkedList<Note>();
int[][] map = new int[row+1][col+1];// 用来存储地图
int[][] flags = new int[row+1][col+1];// 用来标记状态
// 定义走的方位
int[][] next = { { 0, 1 }, // 向右走
{ 1, 0 }, // 向下走
{ 0, -1 }, // 向左走
{ -1, 0 } // 向上走
};
{
// 队列初始化
for (int i = 0; i < que.length; i++) {
que[i] = new Note();
}
//初始化路障
map[1][3] = 1;// 0表示没有路障,1表示路障
map[3][3] = 1;
map[4][2] = 1;
map[5][4] = 1;
}
//队列初始化
public void init() {
head = 1;//队列的头
tail = 1;//队列的尾部
// 第一步将{1，1}加入队列，
queue.add(new Note(startX, startY, 0));
tail++;
flags[startX][startY] = 1;//并标记{1，1}已经走过了
endFlag = 0;//初始化结束标记
}
public void bfs() {
init();
while (head < tail) {
Note poll = queue.poll();
for (int i = 0; i <= 3; i++) {
//设置当前的需要移动的位置
moveX = poll.getX() + next[i][0];
moveY = poll.getY() + next[i][1];
// 判断是否越界
if (moveX < 1 || moveX > row || moveY < 1 || moveY > col) {
continue;
}
// 再判断是否为障碍物，或者已经走过了
if (map[moveX][moveY] == 0 && flags[moveX][moveY] == 0) {
// 如果满足上面的条件，将{1，2}入队，并标记该点已经走过
flags[moveX][moveY] = 1;
// 插入新的点到队列中
queue.add(new Note(moveX, moveY, poll.getStep()+1));
System.out.println("moveX:"+moveX+",moveY:"+moveY);//输出每次搜索的下标
tail++;//这里的表示可以走在标记为0的位置，当前的尾部不停的后移
}
// 表示到达了目的地，任务结束，退出循环
if (moveX == treasureX && moveY == treasureY) {
endFlag = 1;
int step = poll.getStep()+1;// 步数是前面的步数+1
System.out.println(step);
break;
}
}
if (endFlag == 1) {
break;
}
head++;//每一次都会将头向后部移动
}
}
@Test
public void print() {
for (int i = 1; i < map.length; i++) {
for (int j = 1; j < map[i].length; j++) {
System.out.print(map[i][j]);
if (j < map[i].length - 1) {
System.out.print(",");
}
}
System.out.println();
}
}
public static void main(String[] args) {
BreadthFirstSearch bfs=new BreadthFirstSearch();
bfs.bfs();
}
}
7.测试
两次的结果：
moveX:1,moveY:2
moveX:2,moveY:1
moveX:2,moveY:2
moveX:3,moveY:1
moveX:2,moveY:3
moveX:3,moveY:2
moveX:4,moveY:1
moveX:2,moveY:4
moveX:5,moveY:1
moveX:3,moveY:4
moveX:1,moveY:4
moveX:5,moveY:2
moveX:4,moveY:4
moveX:5,moveY:3
moveX:4,moveY:3
7
8.总结
1.当前的广度优先搜索算法，是从一个地点中查找出许多地点，通过查出的地点再找出许多地点
2.查找的地点可以为多个，并且每个都会再标记中存放，用来判断当前的地点是否被走过
3.通过全部范围的搜索方式进行全图搜索，知道找到目标位置为止。
4.通过前后指针的方式不停的移动进行执行，每次执行的时候都以是否越界为基础，进行查找，每次的查找符合要求需要添加入队列，并添加对应的标记，看起来就像是地毯式搜索一样
5.广度优先搜索算法是一种范围式的搜索，而深度优先搜索算法是朝一个方向一直走，等到路不通的时候就执行回退上一步的操作，朝另外一个方向执行，直到找到为止
6.广度优先搜索算法学起来是有难度的需要多次练习才能体会其中的奥妙！
以上纯属个人见解，如有问题请练习本人！