首页 > 其他分享 >广度优先搜索(BFS)

广度优先搜索(BFS)

时间:2023-11-30 20:22:25浏览次数:23  
标签:优先 遍历 int next BFS 队列 广度 root 节点

一、广搜介绍

广度优先搜索是一种暴力算法,通过遍历一整张图来找寻结果。一般是使用队列来实现

1.原理

首先我们将根节点加入队列,然后遍历这个节点的全部方向,如果有满足条件的节点出现,就将其加入队列。

在全部方向遍历完之后,我们将遍历的节点出队列。然后接着重复上述的操作,直到队列为空,也就代表着图遍历完毕。

2.详解

上图为我们展示了BFS遍历的过程,接下来我们详细解释一下。

首先我们定义一个队列为q,这时队列是为空的。我们将root也就是根节点加入队列。

此时队列中的元素为:root。然后遍历与root相连的节点,发现有1和2,将其加入到队列中。遍历完之后将root出队列。

此时队列中的元素为:2,1。接下来遍历与1相连的节点,发现有3,4将其加入队列,然后1出队列。

此时队列中的元素为:4,3,2。然后遍历与2相连的节点,发现有5和6将其加入队列,然后再让2出队列。

以此类推,最后直到队列为空的时候就代表我们将图遍历了一次。

二、代码实现

举个例子,走迷宫,给一个n*m的二维数组表示迷宫,迷宫只由数字0和1组成,其中0代表可以走,而1代表墙。

现在我们要从左上角的(0,0)走到右下角的(n - 1,m - 1),其中我们每次可以在上,下,左,右四个方向中任走一步,

如果我们能到达右下角就输出能到达,不能就输出不能到达。

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// 首先我们要做一些初始化定义
int n, m;
int Map[50][50];
bool visit[50][50] = {false};
// 定义一个节点队列,里面包含两个参数x,也就是坐标
struct point
{
    int x, y;
}root;
queue<point> q;

//定义我们要走的方向上下左右四个方向。
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};


bool BFS(int x,int y){
    //初始化我们的起点
   root.x = x;
   root.y = y;
   //表示这个点是我们走过的
   visit[x][y] = true;
   q.push(root);
   while(!q.empty()){
       point node = q.front();//定义一个变量用于保存我们当前要遍历的节点
       q.pop();//将队首出队列
       //满足条件就直接返回
       if(node.x == n - 1 && node.y == m - 1)
           return true;
       for (int i = 0; i < 4;i++){
        //开始遍历我们要走的方向
           int next_x = node.x + dx[i];
           int next_y = node.y + dy[i];
        //判断一下,首先不能越界并且是可以走的,然后这个点是我们之前没有走过的,
        if(Map[next_x][next_y] == 0 && visit[next_x][next_y] == false && next_x >= 0 && next_y >=0 && next_x < n && next_y < m){
            //将这个节点设为已走过
            visit[next_x][next_y] = true;
            //更新节点值
            node.x = next_x;
            node.y = next_y;
            //将节点加入队列
            q.push(node);
        }
        
       }
   }
   return false;
}


int main(){
    cin >> n >> m;
    //建图
    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++){
            cin >> Map[i][j];
        }
    }
    if(BFS(0,0)){
        cout << "能走到";
    }
    else cout <<"不能走到";
    return 0;
}

 运行结果如下:

 

标签:优先,遍历,int,next,BFS,队列,广度,root,节点
From: https://www.cnblogs.com/linx000/p/17867680.html

相关文章

  • 【DFS深度优先遍历】给定一个数组,从第一个开始,正好走到数组最后,所使用的最少步骤数
    题目描述给定一个数组,从第一个开始,正好走到数组最后,所使用的最少步骤数。要求:第一步从第一元素开始,第一步小于<len/2(len为数组的长度)。从第二步开始,只能以所在成员的数字走相应的步数,不能多也不能少,如果目标不可达返回-1,输出最少的步骤数,不能往回走。输入759426835......
  • 【DFS深度优先算法】全排列、组合总和
    全排列题目描述:给定一个没有重复数字的序列,返回其所有可能的全排列。题目链接:46.全排列输入描述:输入:[1,2,3]输出描述:输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]思路:依次从前往后把所有数字,固定在第0个位置,此时再从前往后把剩余数字依次固定在第1个位置,如此......
  • Linux、进程优先级
    Linux、进程优先级在Linux系统中,每个进程都有一个优先级,该优先级决定了进程在系统中使用CPU资源的权重。进程的优先级通常是动态调整的,取决于多个因素。以下是一些与Linux进程优先级相关的关键概念:1. **Nice值:** 进程的Nice值是一个表示进程优先级的数值。Nice值的范围通常在-20......
  • 支持修改键值的优先队列(以C++,Java为例)
    #include<queue>#include<functional>template<typenameT1,typenameT2>classmutable_priority_queue;template<typenameT1,typenameT2>classmutable_priority_queue{private:std::function<bool(conststd::pair<T1,T......
  • java基础学习:三元运算符,运算符的优先级
    三元运算符介绍:格式:条件表达式?值1:值2;执行流程:首先计算关系表达式的值,如果值为true,返回值1,如果值为false,返回值2代码:packagecom.itheima.operator;publicclassOperator6{publicstaticvoidmain(String[]args){//目标:三元运算符的基本使用do......
  • Mysql 中运算符的优先级
    在实际运行的时候,可以参考上图的优先级,但是很少有人能将这些优先级熟练记忆,很多情况下我们都是用()将需要优先的操作括起来,这样既起到了优先的作用,又使得其它用户看起来更易于理解......
  • 线程的优先级
    Java提供一个线程调度器来监控程序中启动后进入就绪状态的所有进程,线程调度器按照优先级决定应该调度那个线程来执行线程的优先级用数字表示,范围从1-10Thread.MIN_PRIORITY=1;Thread.MAX_PRIORITY=10;Thread.NORM_PRIORITY=5;使用以下方式改变或获取优先级getPriority().setPriori......
  • 堆和优先队列(洛谷P3378)
    1.优先队列解决:优先队列:头文件和定义:#include<queue>template<classT,classContainer=vector<T>,classCompare=less<typenameContainer::value_type>>classpriority_queue;可表达为以下形式:priority_queue<Type,Container,Functional>type:即数据的类型Co......
  • AcWing 920. 最优乘车 (抽象建图 + bfs
    package算法提高课;importjava.util.Arrays;importjava.util.LinkedList;importjava.util.Queue;importjava.util.Scanner;publicclassacw920{/***本题的建图方式:*我们对于每一个巴士路线进行观察,发现从前面的站走向这一条巴士路线......
  • 数据结构之优先队列(java)
    一:概述队列的特点是:先进先出(FIFO).入队列,将元素置于队尾;出队列,队头元素最先被移出:优先队列不遵循先入先出的原则,而是分两种情况。最大优先队列,无论入队顺序如何,都是当前最大的元素优先出队最小优先队列,无论入队顺序如何,都是当前最小的元素优先出队。例如有一个最大优先队列,其中的......