首页 > 编程语言 >【c++】广度优先搜索详解

【c++】广度优先搜索详解

时间:2024-11-13 20:19:43浏览次数:3  
标签:int c++ BFS 队列 详解 front 广度 节点 dir

BFS(图论)

BFS 全称是 Breadth First Search,中文名是宽度优先搜索,也叫广度优先搜索。

是图上最基础、最重要的搜索算法之一。

所谓宽度优先。就是每次都尝试访问同一层的节点。 如果同一层都访问完了,再访问下一层。

这样做的结果是,BFS 算法找到的路径是从起点开始的 最短 合法路径。换言之,这条路径所包含的边数最小。

在 BFS 结束时,每个节点都是通过从起点到该点的最短路径访问的。

算法过程可以看做是图上火苗传播的过程:最开始只有起点着火了,在每一时刻,有火的节点都向它相邻的所有节点传播火苗。

实现

下文中 C++ 的代码实现是基于链式前向星的存图方式。

void bfs(int u) {
  while (!Q.empty()) Q.pop();
  Q.push(u);
  vis[u] = 1;
  d[u] = 0;
  p[u] = -1;
  while (!Q.empty()) {
    u = Q.front();
    Q.pop();
    for (int i = head[u]; i; i = e[i].nxt) {
      if (!vis[e[i].to]) {
        Q.push(e[i].to);
        vis[e[i].to] = 1;
        d[e[i].to] = d[u] + 1;
        p[e[i].to] = u;
      }
    }
  }
}

void restore(int x) {
  vector<int> res;
  for (int v = x; v != -1; v = p[v]) {
    res.push_back(v);
  }
  std::reverse(res.begin(), res.end());
  for (int i = 0; i < res.size(); ++i) printf("%d", res[i]);
  puts("");
}

具体来说,我们用一个队列 Q 来记录要处理的节点,然后开一个布尔数组 vis[] 来标记是否已经访问过某个节点。

开始的时候,我们将所有节点的 vis 值设为 0,表示没有访问过;然后把起点 s 放入队列 Q 中并将 vis[s] 设为 1。

之后,我们每次从队列 Q 中取出队首的节点 u,然后把与 u 相邻的所有节点 v 标记为已访问过并放入队列 Q。

循环直至当队列 Q 为空,表示 BFS 结束。

在 BFS 的过程中,也可以记录一些额外的信息。例如上述代码中,d 数组用于记录起点到某个节点的最短距离(要经过的最少边数),p 数组记录是从哪个节点走到当前节点的。

有了 d 数组,可以方便地得到起点到一个节点的距离。

有了 p 数组,可以方便地还原出起点到一个点的最短路径。上述代码中的 restore 函数使用该数组依次输出从起点到节点 x 的最短路径所经过的节点。

时间复杂度 O(n+m)

空间复杂度 O(n)(vis 数组和队列)

open-closed 表

在实现 BFS 的时候,本质上我们把未被访问过的节点放在一个称为 open 的容器中,而把已经访问过了的节点放在一个称为 closed 容器中。

在树/图上 BFS

BFS 序列

类似 DFS 序列,BFS 序列是指在 BFS 过程中访问的节点编号的序列。

一般图上 BFS

如果原图不连通,只能访问到从起点出发能够到达的点。

BFS 序列通常也不唯一。

类似的我们也可以定义 BFS 树:在 BFS 过程中,通过记录每个节点从哪个点访问而来,可以建立一个树结构,即为 BFS 树。

应用

  • 在一个无权图上求从起点到其他所有点的最短路径。
  • 在O(n+m)时间内求出所有连通块。(我们只需要从每个没有被访问过的节点开始做 BFS,显然每次 BFS 会走完一个连通块)
  • 如果把一个游戏的动作看做是状态图上的一条边(一个转移),那么 BFS 可以用来找到在游戏中从一个状态到达另一个状态所需要的最小步骤。
  • 在一个有向无权图中找最小环。(从每个点开始 BFS,在我们即将抵达一个之前访问过的点开始的时候,就知道遇到了一个环。图的最小环是每次 BFS 得到的最小环的平均值。)
  • 找到一定在(a,b)最短路上的边。(分别从 a 和 b 进行 BFS,得到两个 d 数组。之后对每一条边(u,v),如果d_{a}[u]+1+d_{b}[v]=d_{a}[b],则说明该边在最短路上)
  • 找到一定在(a,b)最短路上的点。(分别从 a 和 b 进行 BFS,得到两个 d 数组。之后对每一个点 v,如果d_{a}[u]+1+d_{b}[v]=d_{a}[b],则说明该点在某条最短路上)
  • 找到一条长度为偶数的最短路。(我们需要一个构造一个新图,把每个点拆成两个新点,原图的边(u,v) 变成((u,0),(v,1))和((u,1),(v,0))。对新图做 BFS,(s,0)和(t,0)之间的最短路即为所求)
  • 在一个边权为 0/1 的图上求最短路,见下方双端队列 BFS。

双端队列 BFS

双端队列 BFS 又称 0-1 BFS。

适用范围

边权值为可能有,也可能没有(由于 BFS 适用于权值为 1 的图,所以一般权值是 0 或 1),或者能够转化为这种边权值的最短路问题。

例如在走迷宫问题中,你可以花 1 个金币走 5 步,也可以不花金币走 1 步,这就可以用 0-1 BFS 解决。

实现

一般情况下,我们把没有权值的边扩展到的点放到队首,有权值的边扩展到的点放到队尾。这样即可保证像普通 BFS 一样整个队列队首到队尾权值单调不下降。

下面是伪代码:

while (队列不为空) {
  int u = 队首;
  弹出队首;
  for (枚举 u 的邻居) {
    更新数据
    if (...)
      添加到队首;
    else
      添加到队尾;
  }
}

例题

一个n×m的图,现在有一束激光从左上角往右边射出,每遇到 '#',你可以选择光线往四个方向射出,或者什么都不做,问最少需要多少个 '#' 往四个方向射出才能使光线在第  行往右边射出。

此题目正解不是 0-1 BFS,但是适用 0-1 BFS,减小思维强度,赛时许多大佬都是这么做的。

做法很简单,一个方向射出不需要花费(0),而往四个方向射出需要花费(1),然后直接来就可以了。

代码
#include <deque>
#include <iostream>
using namespace std;

constexpr int INF = 1 << 29;
int n, m;
char grid[1001][1001];
int dist[1001][1001][4];
int fx[] = {1, -1, 0, 0};
int fy[] = {0, 0, 1, -1};
deque<int> q;  // 双端队列

void add_front(int x, int y, int dir, int d) {  // 向前方加
  if (d < dist[x][y][dir]) {
    dist[x][y][dir] = d;
    q.push_front(dir);
    q.push_front(y);
    q.push_front(x);
  }
}

void add_back(int x, int y, int dir, int d) {  // 向后方加
  if (d < dist[x][y][dir]) {
    dist[x][y][dir] = d;
    q.push_back(x);
    q.push_back(y);
    q.push_back(dir);
  }
}

int main() {
  cin >> n >> m;
  for (int i = 0; i < n; i++) cin >> grid[i];

  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
      for (int k = 0; k < 4; k++) dist[i][j][k] = INF;

  add_front(n - 1, m - 1, 3, 0);

  while (!q.empty()) {  // 具体搜索的过程,可以参考上面写的题解
    int x = q[0], y = q[1], dir = q[2];
    q.pop_front();
    q.pop_front();
    q.pop_front();
    int d = dist[x][y][dir];
    int nx = x + fx[dir], ny = y + fy[dir];
    if (nx >= 0 && nx < n && ny >= 0 && ny < m)
      add_front(nx, ny, dir, d);  // 判断条件
    if (grid[x][y] == '#')
      for (int i = 0; i < 4; i++)
        if (i != dir) add_back(x, y, i, d + 1);
  }
  if (dist[0][0][3] == INF)
    cout << -1 << endl;
  else
    cout << dist[0][0][3] << endl;
  return 0;
}

标签:int,c++,BFS,队列,详解,front,广度,节点,dir
From: https://blog.csdn.net/2401_88851881/article/details/143694731

相关文章

  • 【c++】游戏作品分享
    1.法术对战#include<iostream>usingnamespacestd;intmain(){ intyhp=444; intchp=2000; intaaa; intlan=2000; intdu=0; inttuy=0; for(inti=1;i<=9999;i++) { cout<<"你的血量:"<<yhp<<endl<<"电脑血量:&quo......
  • 【c++】游戏作品分享
     c++代码#include<bits/stdc++.h>#include<xiaohoucode.h>#include<time.h>#include<stdlib.h>#include<unistd.h>#include<termio.h>#include<ctype.h>#include<stdio.h>#include<math.h>usingnamespa......
  • Visual C++ 6.0中文版安装包下载教程及win11安装教程
    本文分享的是VisualC++6.0(简称VC++6.0)中文版安装包下载及安装教程,关于win11系统下安装和使用VC++6.0使用问题解答,大家在安装使用的过程中会遇到不同的问题,如遇到解决不了的问题请给我留言!一、安装包的下载vc6.0安装包下载连接:https://pan.quark.cn/s/979dd8ba4f35二、......
  • C++零基础入门&趣味学信息学奥赛_开发环境安装
    Arduino软件安装,安装树莓派Pico开发板及上传Pico固件目录1.安装Windows驱动程序1.1.下载安装arduino软件:1.2.安装开发板Pico1.3.上传Arduino兼容的Pico固件1.安装Windows驱动程序                                        ......
  • RabbitMQ 在 Java 和 Spring Boot 中的应用详解
    1.引言RabbitMQ是一种开源消息代理软件,广泛用于实现消息传递、队列管理和负载均衡。它通过实现AMQP(AdvancedMessageQueuingProtocol)来支持复杂的消息传递模式,是常见的消息中间件之一。本文将深入探讨如何在纯Java环境和SpringBoot项目中使用RabbitMQ,并涵盖详细......
  • C++ 移动构造和拷贝构造函数匹配
    既有拷贝构造又有移动构造这个比较好理解,普通的函数匹配规则就可以。右值移动,左值拷贝。——《C++Primer》P477我们不能隐式地将一个右值引用绑定到一个左值。有拷贝构造但没有移动构造这种情况,右值也会被拷贝。如果一个类没有移动构造函数,函数匹配规则保证该类型的对象......
  • 3大主流分布式事务框架详解(图文总结)
    3大主流分布式事务框架详解(图文总结) 1简要介绍随着微服务架构的不断发展,分布式系统逐渐普及到后端领域的每一个角落。在分布式系统中,跨多个服务的数据一致性一直是一个重大挑战,为解决这一挑战,分布式事务应运而生。作者在之前的文章《五种分布式事务解决方案》和《4大主流分......
  • C++继承和参数化类型(模板)各自的优点
    在C++中,继承和参数化类型(模板)都是强大的代码重用机制,它们各自具有独特的优点。以下是对这两种机制优点的比较和归纳:C++继承的优点代码重用:继承允许子类继承父类的属性和方法,从而避免了重复编写相同的代码。这不仅提高了开发效率,还减少了代码中的冗余。扩展性:通过继承,可以创建......
  • C++ 逆向之常用字符集互转
    在过往的编程过程中,常常会因为碰到字符集问题而头痛,而每次在进行字符集转换的时候,各种搜索网上文档,想找字符集转换的示例程序,但是都不尽人意,本篇文章的目的就是彻底解决之前编程过程中对字符集认识以及字符集转换之间似懂非懂、云里雾里的状态,并在文章结尾附上ANSI、UNICODE和U......
  • 《深度解析 C++中的弱引用(weak reference):打破循环依赖的利器》
    在C++编程的世界里,内存管理一直是一个关键且复杂的话题。而弱引用(weakreference)的出现,为我们处理一些特殊的内存相关问题提供了一种巧妙的方法。今天,我们就来深入了解一下什么是弱引用。一、从引用的基本概念说起我们都知道,在C++中,引用是一种给变量起别名的方式。正常......