广度优先搜索BFS：图与迷宫

目录

一、BFS定义

二、BFS与无权图的最短路问题

三、BFS与迷宫问题

四、BFS与连通块问题

---

一、BFS定义

我们以图的搜索来引入广度优先搜索的定义。如下是一张无向图，现对其进行广度优先遍历：对于每一结点，广度优先搜索会优先遍历该结点所有可能的分支，如对于A，它的分支有B与F，则接下来就将遍历B与F，后续所有结点同理。若以A为起点，则该图一种可能的广度优先搜索结果是：A BF CIGE DH。

其具体实现可以利用队列完成：

若起点为A：

将起点A放入队列；        q：A

取出A，A能扩展出B、F，BF入队；        q：BF

        取出B，B能扩展出C、I、G，CIG入队；        q：FCIG

        取出F，F能扩展出E，E入队；         q：CIGE

                取出C，C能扩展出D，D入队；        q：IGED

                取出I，I能扩展出的结点此前已经被扩展过，无需重复入队；        q：GED

                取出G，G能扩展出H，H入队；        q：EDH

                取出E，E能扩展出的结点此前已经被扩展过，无需重复入队；        q：DH

                        取出D，D能扩展出的结点此前已经被扩展过，无需重复入队；        q：H

                        取出H，q为空，遍历完成；

遍历结果为：A BF CIGE DH。

二、BFS与无权图的最短路问题

BFS有什么优势呢？那就是将整幅图划分出了层次，第一层：A、第二层：BF、第三层：CIGE、第四层：DH，所以广搜又可以叫做层次遍历。广搜可以用来求得无权图上任意两结点间的最短路，其就等于它们分别所在的层数之差的绝对值，如结点B到H的最短路为 4-2=2。（默认无权图的所有边权都等于1，如果图并非是无权图，但其边权均相等为n，也同样能用bfs求解，最后的结果乘以n即可）

这是一个十分重要的应用，很多问题都可以转化为无权图的最短路求解，如下面两道例题：

例1：抓住那头牛

我们以农夫位于2，牛位于7为例，农夫有三种移动方式，我们将其以树的形式表示（树是一种特殊的图）如下：

可以看到，现在该问题就已经变成了在该树(图)中，2结点到7结点的最短路，使用BFS解决：

import java.util.Deque;
import java.util.LinkedList;
import java.util.Scanner;
 
public class Main {
	static class Node{
		int val;
		int step;
		public Node(int val, int step) {
			this.val=val;
			this.step=step;
		}
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int m = sc.nextInt(), n = sc.nextInt();
        //这个判断是必须的，但是可以只判断m==n，因为后续的代码中如果m==n将出现死循环，m>n虽然不会出现死循环，但是我们在这里就能直接得到答案，既然如此就顺便一起处理了
        if(m>=n){
            System.out.println(m-n);
            return;
        }
		boolean[] vis = new boolean[100005];
		Deque q = new LinkedList<>();
		q.add(new Node(m,0));
		vis[m] = true;
		while( !q.isEmpty() ) {
			Node tmp = q.poll();
			int x;
			for(int i=0; i<3; ++i) {
				if(i==0) x = tmp.val+1;
				else if(i==1) x = tmp.val-1;
				else x = tmp.val*2;
				if(x>=0 && x<=100000 && !vis[x]) {
					if(x==n) {
						System.out.println(tmp.step+1);
						return;
					}
					q.add(new Node(x,tmp.step+1));
					vis[x]=true;
				}
			}
		}
	}
}

例2：八数码

八数码是BFS的典型应用之一，其也可以转化为求图上两节点间的最短间距：每个八数码都可以将空格块与它上下左右相邻块交换，这样一个八数码可以扩展出四个新的八数码，这个扩展过程正是BFS的过程。以‘’283104765‘’为例，其BFS过程如下图所示：

同样，问题转化为无权图上求最短路，示例代码如下所示：

public void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String s = sc.nextLine();
    if(s.equals("123804765") {
        System.out.println(0);
        return;
    }
    int[] dx = {-1,1,0 ,0};
    int[] dy = {0 ,0,-1,1};
    ArrayDeque q = new ArrayDeque<>();
    q.add(s);
    Map ans = HashMap<>();
    while(!q.isEmpty()) {
        String tmp = q.poll();
        int index = tmp.indexOf('0');
        for(int i = 0; i < 4; ++i) {
            int x = index / 3 + dx[i], y = index % 3 + dy[i];
            if((x >= 0 && x < 3) && (y >= 0 && y < 3)) {
                int target = x * 3 + y;
                String str = swap(tmp, index, target);
                if(!ans.containsKey(str)) {
                    ans.put(str, ans.getOrDefault(str, 0) + 1);
                    if(str.equals("123804765") {
                        System.out.println(ans.get(str));
                        return;
                    }
                    q.add(str);
                }
            }
        }
    }
}
private static String swap(String s, int i, int j) {
    char[] str = s.toCharArray();
    char tmp = str[i];
    str[i] = str[j];
    str[j] = tmp;
    return new String(str);
}

三、BFS与迷宫问题

迷宫问题之所以能用广搜解答，是因为我们用来表示迷宫的矩阵，实际上也能看做一张图，要求走出迷宫的最小步数，就等于图中起始结点与目标结点的最短路。

1.走迷宫

一个n*m的矩阵，'.'代表可走，'#'代表不可走，现要从左上角走到右下角（只能走上下左右），最小步数是多少？

在每个位置都能朝上下左右四个方向走，也就是这个结点能扩展出四个新的结点，这个过程就是BFS的过程（注意不要超出迷宫范围以及不要重复搜索），解决迷宫问题的模板如下：

import java.util.LinkedList;
import java.util.Scanner;
 
public class Main{
    //记录坐标
	static class Point{
		int x;
		int y;
		int step;
		public Point(int x, int y, int step) {
			this.x=x;
			this.y=y;
			this.step=step;
		}
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(), m = sc.nextInt();
		sc.nextLine(); //有一个回车
		char[][] map = new char[n][m];
		for(int i=0; i
			String s = sc.nextLine();
			for(int j=0; j
				map[i][j]=s.charAt(j);
			}
		}
        //上下左右
		int[] dx = {-1,1,0 ,0};
		int[] dy = {0,0 ,-1,1};
		LinkedList q = new LinkedList<>();
		map[0][0]='#';//起点
		Point p = new Point(0,0,1);
		q.add(p);
		while(!q.isEmpty()) {
			Point tmp = q.poll();
            //向上下左右四个方向遍历
			for(int i=0; i<4; ++i) {
				int x = tmp.x+dx[i], y = tmp.y+dy[i];
                //新坐标在迷宫内且是可走的
				if(x>=0 && x=0 && y'#') {
					Point point = new Point(x,y,tmp.step+1);
                    //如果到达终点就输出
					if(x==n-1 && y==m-1) {
						System.out.println(point.step);
						return;
					}
					q.add(point);
                    //走过的迷宫改为不可走，广搜不需要走回该位置
					map[x][y]='#';
				}
			}
		}
		System.out.println("impossible!");
	}
}

四、BFS与连通块问题

连通块问题是迷宫问题的一个扩展，此时题目要求的不再是最少步数，而是询问迷宫内有多少区域是连通的（不同题目的连通条件可能不同）。

2.细胞计数

在每个不为障碍的位置都进行一次BFS，将所有能扩展出的结点标记，后序被标记的位置不再重复BFS，下面的代码是该类型问题的模板，请读者对照自行实现：

import java.util.Deque;
import java.util.LinkedList;
import java.util.Scanner;
 
public class Main{
	static class Point{
		int x;
		int y;
		public Point(int x, int y) {
			this.x=x;
			this.y=y;
		}
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int m = sc.nextInt(), n = sc.nextInt();
		int[][] map = new int[m][n];
		for(int i=0; i
			String s = sc.next();
			for(int j=0; j
				map[i][j]=s.charAt(j)-'0';
			}
		}
        int[] dx={-1,1,0,0};
        int[] dy={0,0,-1,1};
        int ans = 0;
        for(int i=0; i
        	for(int j=0; j
        		if(map[i][j]==0) continue;
        		ans++; //计算共有多少个连通块
        		map[i][j]=0;
        		Deque q = new LinkedList<>();
        		q.add(new Point(i,j));
        		while(!q.isEmpty()) {
        			Point tmp = q.poll();
            		for(int k=0; k<4; ++k) {
            			int x=tmp.x+dx[k], y=tmp.y+dy[k];
            			if((x>=0 && x=0 && y0) {
            				q.add(new Point(x,y));
            				map[x][y]=0;
            			}
            		}
        		}
        	}
        }
        System.out.println(ans);
	}
}

3.城堡问题

本题仍然是连通问题，但是其连通方式不同于上面的习题，本题中以每个位置数字的二进制来表示是否连通，每个数字的范围限定为4位二进制（即0~15），正好代表四个方向，从高位到低位依次为南、东、北、西（下、右、上、左），而该位为0表示连通，为1则表示不连通。那么本题就需要判断每个数字其二进制每一位的值，这个问题可以通过位运算很快地解决，如我想得到数字X的二进制第3位(从低位数)上的值，通过下面的位运算即可得到：(X>>3)&1。由于本题要计算二进制上每一位的值，所以需要用到原数字，那么就需要一个新的数组来判断每一个数字是否被访问过，完整示例代码如下所示：

import java.util.Deque;
import java.util.LinkedList;
import java.util.Scanner;
 
public class Main{
	static class Point{
		int x;
		int y;
		public Point(int x, int y) {
			this.x=x;
			this.y=y;
		}
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int m = sc.nextInt(), n = sc.nextInt();
		int[][] map = new int[m][n];
        // 一个新数组判断每个数字是否被访问过
		boolean[][] vis = new boolean[m][n];
		for(int i=0; i
			for(int j=0; j
				map[i][j]=sc.nextInt();
				vis[i][j]=false;
			}
		}
		// 左，上，右，下，这个顺序不能改动，因为后面右移运算是顺序是低位到高位
        int[] dx={0,-1,0,1};
        int[] dy={-1,0,1,0};
        int ans = 0, max = 0;
        for(int i=0; i
        	for(int j=0; j
        		if(vis[i][j]) continue;
        		ans++; //计算共有多少个连通块
        		vis[i][j]=true;
        		Deque q = new LinkedList<>();
        		q.add(new Point(i,j));
        		int cnt = 0;
        		while(!q.isEmpty()) {
        			Point tmp = q.poll();
        			cnt++; //计算每个连通块有多少个数字
            		for(int k=0; k<4; ++k) {
            			int x=tmp.x+dx[k], y=tmp.y+dy[k];
            			if((x>=0 && x=0 && y>k)&1)==0) {
            				q.add(new Point(x,y));
            				vis[x][y]=true;
            			}
            		}
        		}
        		max = Math.max(max, cnt);
        	}
        }
        System.out.println(ans);
        System.out.println(max);
	}
}