广度优先搜索

前言

广度优先搜索也是图中遍历的一种，有时候我们用深度优先搜索去解蓝桥杯一些问题的时候往往会超时，还有一些问题用深度优先搜素解决起来会很麻烦，这时候就要用广度优先搜索了。下面简单介绍一下什么的广度优先搜索，例如下面这个图

1.定一个出发点：假设我们从v1出发来遍历这个图，那么广度优先遍历就是按层来遍历，
2.遍历该节点所能到达的节点：他首先遍历v1能到的俩个节点v2和v3，然后将这俩个节点存到队列里面，
3.出队列：遍历完v1所能到达的所有节点之后就开始出队列，遍历v2所能到达的所有节点了，依次这样指导把所有的节点遍历完

例题

有一天，小哈一个人去玩迷宫。但是方向感不好的小哈很快就迷路了。小哼得知后便去解救无助的小哈。此时的小哼已经弄清楚了迷宫的地图，现在小哼要以最快的速度去解救小哈。那么，问题来了…

第一行输入俩个数n,m，n表示迷宫的行，m表示迷宫的列。接下来的n行m列为迷宫，0表示空地，1表示障碍物。最后一行4个数，前俩个数为迷宫入口的x和y坐标。后俩个为小哈的x和y坐标。
样例输入：
5 4
0 0 1 0
0 0 0 0
0 0 1 0
0 1 0 0
0 0 0 1
1 1 4 3
样例输出：
7

分析

这题是求图中一个节点到另外一个节点之间的最短距离，如果我们用深搜的话我们可能会遍历完图中所有的节点才能得到结果，显然这样太耗费时间了，如果用广搜来写就会简单很多。下面看一下代码
广搜

package 解救小哈;

import java.util.Scanner;

public class Main {
	public class Node{
		int x;
		int y;
		int f;
		int step;
	}
	public static boolean[][] visited=new boolean[100][100];//每个节点只能访问一次
	public static int[][]  book=new int[100][100];//地图数组
	public static Node[] que=new Node[100];//节点
	public static void main(String[] args) {
		Scanner input=new Scanner(System.in);

		int tail,head;
		int [][]next={//方向数组
				{0,1},
				{1,0},
				{0,-1},
				{-1,0}
		};
		tail=1;
		head=1;
		int n=input.nextInt();
		int m=input.nextInt();
		for(int i=1;i<=n;++i){
			for(int j=1;j<=m;++j)
				book[i][j]=input.nextInt();
		}
		int sum=m*n;
		for(int i=1;i<=sum;++i)
			que[i]=new Main().new Node();//一定要记得再申请内存
		que[head].f=head;
		que[head].step=0;
		que[head].x=input.nextInt();
		que[head].y=input.nextInt();
		int cx=input.nextInt();
		int cy=input.nextInt();
		tail++;//队列的尾
		boolean flag=false;//设置标志位判断有没有找到
		while(tail>head){
			for(int i=0;i<4;++i){
				int tx=que[head].x+next[i][0];
				int ty=que[head].y+next[i][1];
				if(tx>n||ty>m||tx<=0||ty<=0||book[tx][ty]==1)
					continue;
				if(!visited[tx][ty]){
					visited[tx][ty]=true;
					que[tail].x=tx;
					que[tail].y=ty;
					que[tail].f=head;
					que[tail].step=que[head].step+1;
					tail++;
				}
				if(tx==cx&&tx==cy){
					flag=true;
					break;
				}
			}
			if(flag)
				break;
			head++;
		}
		System.out.println(que[tail-1].step);
	}

}

深搜

package 解救小哈深搜;

import java.util.Scanner;

public class Main {
	public static int cx,cy,rx,ry,min=100,n,m;
	public static int[][]  book=new int[100][100];//地图数组
	public static boolean[][] visited=new boolean[100][100];//每个节点只能访问一次
	public static void dfs(int x,int y,int step,int[][] nums,int flag){
		int[][] next={
				{0,1},
				{1,0},
				{0,-1},
				{-1,0}
		};
		if(x==cx&&y==cy){
			if(step<min){
				min=step;
				for(int i=0;i<flag;++i){
					for(int j=0;j<2;++j)
						System.out.print(nums[i][j]+" ");
				}
				System.out.println();
			}
			return;
		}
		for(int i=0;i<4;++i){
			int tx=x+next[i][0];
			int ty=y+next[i][1];
			if(tx<1||ty<1||tx>n||ty>m||book[tx][ty]==1)
				continue;
			if(!visited[tx][ty]){
				visited[tx][ty]=true;
				nums[flag][0]=tx;
				nums[flag][1]=ty;
				flag++;
				dfs(tx,ty,step+1,nums,flag);
				visited[tx][ty]=false;
			}
			
		}
		return;
	}
	public static void main(String[] args) {
		Scanner input=new Scanner(System.in);
		int[][] nums=new int[100][100];
		int flag=1;
		n=input.nextInt();
		m=input.nextInt();
		for(int i=1;i<=n;++i){
			for(int j=1;j<=m;++j)
				book[i][j]=input.nextInt();
		}
		rx=input.nextInt();
		ry=input.nextInt();
		cx=input.nextInt();
		cy=input.nextInt();
		visited[rx][ry]=true;
		dfs(rx,ry,0,nums,flag);
		System.out.println(min);
		input.close();
	}

}

代码分析

广搜我们可以用一个数组模仿队列（一种先进先出的数据结构），队列存放已经遍历的节点，注意java中没有结构体，所以我们要用内部类来实现，之后就是按每个节点可以有上下左右四个方向依次遍历，然后入队列出队列。
注意：声明了节点队列之后一定要再为每个节点申请内存

总结

广搜也是蓝桥杯常考考点，一般用广搜找最短路径，广搜时间复杂度也要比深搜简单很多，请大家务必掌握，题目大家可以到洛谷上刷