算法——广度优先搜索（BFS）

男娘i 2024-02-05 18:23 10阅读 0赞

> 推荐资源：
> 
>  *  [OI Wiki - OI Wiki (oi-wiki.org)][OI Wiki - OI Wiki _oi-wiki.org]
>     
>      *  内容有算法、数据结构、数学知识、编程语言等等
>      *  是一个免费开放且持续更新的 编程竞赛 知识整合站点

> ## BFS(Breadth First Search) ##
> 
>  *  广度优先搜索（BFS）是一种用于图和树数据结构的搜索算法。它从图或树的根节点开始，逐层地向下搜索，并在同一层节点中完成搜索后再向下一层节点进行搜索。它通常使用队列来实现，在搜索过程中，将当前节点的邻居节点依次加入队列中，以确保按照层级顺序进行搜索。
>  *  **代码模板**
>     
>      *      //...
>                 /**
>                  * 进行广度优先搜索
>                  * @param u 起始节点
>                  */
>                 void bfs(int u) {
>                   while (!Q.empty()) Q.pop(); // 清空队列Q
>                   Q.push(u); // 将u加入队列Q
>                   visited[u] = 1; // 标记节点u已访问
>                   distance[u] = 0; // 节点u到起始节点的距离为0
>                   previous[u] = -1; // 节点u的父节点为-1
>                   while (!Q.empty()) {
>                     u = Q.front(); // 取出队首节点u
>                     Q.pop(); // 弹出队首节点u
>                     for (int i = head[u]; i; i = e[i].nxt) { // 遍历u的相邻节点
>                       if (!visited[e[i].to]) { // 如果相邻节点未被访问
>                         Q.push(e[i].to); // 将相邻节点加入队列Q
>                         visited[e[i].to] = 1; // 标记相邻节点已访问
>                         distance[e[i].to] = distance[u] + 1; // 更新相邻节点到起始节点的距离
>                         previous[e[i].to] = u; // 更新相邻节点的父节点为u
>                       }
>                     }
>                   }
>                 }
>             
>                 /**
>                  * 根据父节点数组p还原路径并输出
>                  * @param x 终点节点
>                  */
>                 void restore(int x) {
>                   vector<int> restore; // 用于存储路径节点
>                   for (int v = x; v != -1; v = previous[v]) { // 从终点节点开始回溯路径
>                 	  restore.push_back(v); // 将节点v加入路径
>                   }
>                   std::reverse(restore.begin(), restore.end()); // 反转路径节点，得到正序路径
>                   for (int i = 0; i < restore.size(); ++i) printf("%d", restore[i]); // 输出路径节点
>                   puts(""); // 输出换行符
>                 }
>                 //...
>             //我们用一个队列 Q 来记录要处理的节点，然后开一个布尔数组 visited[] 来标记是否已经访问过某个节点。
>             
>             //开始的时候，我们将所有节点的 visited 值设为 0，表示没有访问过；然后把起点 s 放入队列 Q 中并将 visited[s] 设为 1。
>             
>             //之后，我们每次从队列 Q 中取出队首的节点 u，然后把与 u 相邻的所有节点 v 标记为已访问过并放入队列 Q。
>             
>             //循环直至当队列 Q 为空，表示 BFS 结束。
>      *  
>  *  BFS 的知识点包括：
>     
>      *  **图的表示方法：**邻接表、邻接矩阵等
>      *  **队列：**BFS 使用队列来记录待访问的节点
>      *  **标记已访问节点：**防止重复访问相同节点
>      *  **图的遍历顺序：**BFS 的遍历顺序是按层次进行的
>      *  **状态搜索：**在有向无环图中，BFS 可以用于搜索从起始状态到目标状态的路径
>  *  BFS常用于寻找图中的最短路径、检查图中是否存在特定节点或寻找所有可能的路径等问题。BFS 也可以应用于解决迷宫问题、状态空间搜索等具体的应用场景中。

## 一、跳马 ##

> 一个8×8的棋盘上有一个马初始位置为(a,b)，他想跳到(c,d)，问是否可以？如果可以，最少要跳几步？
> 
> ![76e89256779f44999416a4ce03e94a73.png][]

> 分析：
> 
>  *  ![8f15bbd8c8784c739e0e886edafa4e70.jpeg][]
>  *  ![1819fae2ecc347d5b20f62eabc91cc84.jpeg][]
>  *  ![7419f442a5c14c519485850d82959f1b.jpeg][]
>  *  ![924eed2266a94c048a0192a881d0fcd1.jpeg][]
>  *  ![534cd4a9538b4f7c83be9c46f15f577b.jpeg][]
>  *  ![f378d917190442e38db62d6255019ef5.jpeg][]
>  *  如果同一层都访问完了，再访问下一层，
>  *  在步数存储在map数组中，每处理完一层，存储在队列中的该层结点的步数 = 上层的步数 + 1
>  *  访问map数组中终点坐标的值，返回即可

package no1_1;
    import java.util.*;
    
    public class Main {
        static int dir[][]= {
       {-2,-1},{-2,1},{-1,-2},{-1,2},{1,2},{1,-2},{2,1},{2,-1}};//定义8个方向马可以走的相对坐标
        //大小设置成15*15，是为了容纳8x8的棋盘以及边界外的一圈缓冲区。这样可以确保在搜索过程中不会越界访问到数组map的位置
        static int map[][]=new int[15][15];//记录步数
        static int x,y,targetX,targetY;//定义马的起点和终点坐标
        static int vis[][]=new int[15][15];//记录走过的坐标
    
        //坐标类，用于表示马的坐标
        public static class Node{
            int x;
            int y;
            
            //构造函数
            public Node(int x,int y) {
                this.x=x;
                this.y=y;
            }
            
            //获取横坐标
            public int getX() {
                return x;
            }
            
            //获取纵坐标
            public int getY() {
                return y;
            }
        }
    
        //主函数
        public static void main(String[] args) {
            Scanner input=new Scanner(System.in);
            int a=input.nextInt();//起点横坐标
            int b=input.nextInt();//起点纵坐标
            int c=input.nextInt();//终点横坐标
            int d=input.nextInt();//终点纵坐标
            bfs(a,b);//进行广度优先搜索
            System.out.println(map[c][d]);//输出到达终点的最少步数
        }	
    
        //判断马是否在棋盘上
        public static boolean inmap(int x,int y) {
            return x>=1 && x<=8 && y>=1 && y<=8;//判断横纵坐标是否在1-8范围内
        }
    
        //广度优先搜索
        public static void bfs(int x,int y) {
            vis[x][y]=1;//标记起点已走过
            Queue<Node> queue = new LinkedList<>();//创建队列
            queue.add(new Node(x,y));//将起点加入队列
            map[x][y]=0;//起点步数为0
            while(!queue.isEmpty()) {//队列不为空时循环
                Node now=queue.poll();//获取队首元素，并移除队首元素
                for(int i=0;i<8;i++) {//遍历8个方向
                    int nextX=now.x+dir[i][0];//计算下一个横坐标
                    int nextY=now.y+dir[i][1];//计算下一个纵坐标
                    if(inmap(nextX,nextY) && vis[nextX][nextY]==0) {//判断下一个点是否在棋盘上且未走过
                        vis[nextX][nextY]=1;//标记下一个点已走过
                        map[nextX][nextY]=map[now.x][now.y]+1;//计算步数
                        queue.add(new Node(nextX,nextY));//将下一个点加入队列
                    }
                }
            }
        }
    }

[OI Wiki - OI Wiki _oi-wiki.org]: https://oi-wiki.org/
[76e89256779f44999416a4ce03e94a73.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/c9de5b7e37ad4a38adc73c0427a01ef5.png
[8f15bbd8c8784c739e0e886edafa4e70.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/5df50f212131479d9cfc7eac26c084e8.png
[1819fae2ecc347d5b20f62eabc91cc84.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/b01ee033fdde4ec5bd2c7ea119e3076a.png
[7419f442a5c14c519485850d82959f1b.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/8b7b2138a56149c5bc913e2194600552.png
[924eed2266a94c048a0192a881d0fcd1.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/5ce6a4f4df5d4ba5a20ff93ca1b61a4d.png
[534cd4a9538b4f7c83be9c46f15f577b.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/78022bd7727b48ea893ee88fdad26405.png
[f378d917190442e38db62d6255019ef5.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/94a8a4367c6e4bf0a16a8cca0ede7e98.png