当前位置: 首页 > news >正文

CSP-J 算法基础 广度优先搜索BFS

文章目录

  • 前言
  • 广度优先搜索是什么
  • 广度优先搜索的实现
  • BFS 的具体编程实现
  • 举例:广度优先搜索的具体步骤
    • 初始状态:
    • 步骤 1:加入起点节点 1
    • 步骤 2:访问队列中的节点 1,加入其邻居节点 2 和 4
    • 步骤 3:访问队列中的节点 2,加入其未访问的邻居节点 3
    • 步骤 4:访问队列中的节点 4,发现它的邻居(节点 1 和 3)都已访问,跳过
    • 步骤 5:访问队列中的节点 3,发现它的邻居(节点 2 和 4)都已访问,跳过
  • 编程实现BFS广度优先搜索
      • C 语言代码示例
      • 代码解释
      • 总结
  • 总结


前言

广度优先搜索(Breadth-First Search,简称 BFS)是图论中的一种基础算法,用于遍历或搜索图的节点。与深度优先搜索(DFS)不同,BFS 是一种层次化的搜索方式,优先访问距离起始节点最近的节点,逐层扩展到更远的节点。由于其遍历顺序的特点,BFS 经常被用于解决最短路径问题、图的连通性检查、树的层序遍历等问题。

在算法竞赛如 CSP-J 中,掌握 BFS 能帮助我们高效地解决图论相关的题目,尤其是在寻找最短路径、求解无权图的某些属性时,BFS 是一种非常有效的工具。


广度优先搜索是什么

BFS 是一种图的遍历算法,类似于按层次的方式搜索图。它从起始节点开始,首先访问所有与该节点直接相邻的节点,然后依次访问每个已访问节点的邻接节点,直到遍历完所有节点或找到目标节点。

BFS 的特点是按最短路径进行遍历。在无权图中,BFS 可以保证从起点到某个节点的路径是最短的。它广泛应用于路径搜索、迷宫问题、连通性检查等场景。

广度优先搜索的实现

BFS 的核心思想是使用队列(FIFO,先进先出)来实现按层次的搜索。具体实现步骤如下:

  1. 初始化:选择一个起始节点,将其标记为已访问并加入队列。
  2. 遍历:从队列中取出一个节点,检查其所有未访问的邻接节点,将它们标记为已访问并加入队列。
  3. 重复:不断从队列中取出节点并访问其邻接节点,直到队列为空。

通过这种方式,BFS 能逐层遍历图的节点,确保从起点到任意节点的访问顺序是按最短路径进行的。

BFS 的具体编程实现

在编程中,BFS 通常使用以下数据结构来实现:

  • 队列:用于保存当前层次要访问的节点。
  • 访问标记数组:用于记录每个节点是否已经访问过,避免重复访问。
  • 图的表示方式:通常使用邻接表或邻接矩阵来存储图的结构信息。

BFS 的伪代码步骤如下:

  1. 将起点加入队列,并将其标记为已访问。
  2. 当队列不为空时,取出队列的第一个节点,检查该节点所有邻接节点。
  3. 对于每个未访问的邻接节点,将其标记为已访问,并加入队列。
  4. 重复该过程,直到队列为空或找到目标节点。

举例:广度优先搜索的具体步骤

我们通过一个简单的例子来演示 BFS 的具体操作步骤。假设有一个无向图,如下:

    1 —— 2|     |4 —— 3

我们从节点 1 开始进行广度优先搜索,目标是遍历所有节点。

初始状态:

  • 队列:空
  • 访问标记数组:所有节点未访问
  • 起点:1

步骤 1:加入起点节点 1

  • 队列:[1]
  • 标记:节点 1 标记为已访问

步骤 2:访问队列中的节点 1,加入其邻居节点 2 和 4

  • 队列:[2, 4]
  • 标记:节点 1、2、4 已访问

步骤 3:访问队列中的节点 2,加入其未访问的邻居节点 3

  • 队列:[4, 3]
  • 标记:节点 1、2、3、4 已访问

步骤 4:访问队列中的节点 4,发现它的邻居(节点 1 和 3)都已访问,跳过

  • 队列:[3]
  • 标记:不变

步骤 5:访问队列中的节点 3,发现它的邻居(节点 2 和 4)都已访问,跳过

  • 队列:空
  • 标记:不变

至此,所有节点都已访问,BFS 结束。

编程实现BFS广度优先搜索

下面是一个简单的广度优先搜索(BFS)的 C 语言代码示例。这段代码实现了一个无向图的 BFS 遍历,展示了如何使用邻接表存储图,并进行 BFS 遍历。

C 语言代码示例

#include <stdio.h>
#include <stdlib.h>// 链表节点表示边
typedef struct AdjListNode {int dest;  // 邻居顶点struct AdjListNode* next;  // 指向下一个邻接节点
} AdjListNode;// 顶点的邻接表
typedef struct AdjList {AdjListNode* head;  // 链表头指针
} AdjList;// 图结构
typedef struct {int numVertices;  // 顶点数AdjList* array;  // 邻接表数组
} Graph;// 创建链表节点
AdjListNode* createNode(int dest) {AdjListNode* newNode = (AdjListNode*)malloc(sizeof(AdjListNode));newNode->dest = dest;newNode->next = NULL;return newNode;
}// 初始化图
Graph* createGraph(int numVertices) {Graph* graph = (Graph*)malloc(sizeof(Graph));graph->numVertices = numVertices;graph->array = (AdjList*)malloc(numVertices * sizeof(AdjList));for (int i = 0; i < numVertices; i++) {graph->array[i].head = NULL;}return graph;
}// 添加无向边
void addEdge(Graph* graph, int src, int dest) {// 添加 src -> destAdjListNode* newNode = createNode(dest);newNode->next = graph->array[src].head;graph->array[src].head = newNode;// 添加 dest -> src (无向图)newNode = createNode(src);newNode->next = graph->array[dest].head;graph->array[dest].head = newNode;
}// 广度优先搜索
void BFS(Graph* graph, int startVertex) {// 创建访问标记数组int* visited = (int*)malloc(graph->numVertices * sizeof(int));for (int i = 0; i < graph->numVertices; i++) {visited[i] = 0;  // 初始化为未访问}// 创建队列int* queue = (int*)malloc(graph->numVertices * sizeof(int));int front = 0;int rear = 0;// 标记起始节点为已访问,并将其入队visited[startVertex] = 1;queue[rear++] = startVertex;while (front < rear) {// 出队int currentVertex = queue[front++];printf("访问顶点 %d\n", currentVertex);// 遍历所有邻接节点AdjListNode* adjList = graph->array[currentVertex].head;while (adjList != NULL) {int adjVertex = adjList->dest;if (!visited[adjVertex]) {visited[adjVertex] = 1;  // 标记为已访问queue[rear++] = adjVertex;  // 入队}adjList = adjList->next;}}// 释放内存free(visited);free(queue);
}// 主函数
int main() {int numVertices = 5;Graph* graph = createGraph(numVertices);// 添加边addEdge(graph, 0, 1);addEdge(graph, 0, 4);addEdge(graph, 1, 2);addEdge(graph, 1, 3);addEdge(graph, 1, 4);addEdge(graph, 2, 3);addEdge(graph, 3, 4);// 从顶点 0 开始进行 BFS 遍历printf("广度优先搜索结果:\n");BFS(graph, 0);// 释放内存for (int i = 0; i < numVertices; i++) {AdjListNode* node = graph->array[i].head;while (node) {AdjListNode* temp = node;node = node->next;free(temp);}}free(graph->array);free(graph);return 0;
}

代码解释

  1. 数据结构定义

    • AdjListNode:表示图中每条边的链表节点。
    • AdjList:表示每个顶点的邻接链表。
    • Graph:包含邻接表数组和顶点数的图结构。
  2. 图的初始化

    • createNode:创建链表节点。
    • createGraph:初始化图,创建邻接表数组。
    • addEdge:添加无向边,更新源顶点和目标顶点的邻接表。
  3. BFS 实现

    • 初始化访问标记数组和队列。
    • 从起始节点开始,标记为已访问并入队。
    • 逐层访问图的节点,并将未访问的邻接节点入队。
    • 打印每个访问到的节点。
  4. 主函数

    • 创建图,添加边,调用 BFS 函数,并释放内存。

总结

这段代码演示了如何用 C 语言实现广度优先搜索(BFS)算法。通过邻接表存储图,BFS 遍历每个节点,并按层次访问所有邻接节点。掌握 BFS 的实现可以帮助我们高效解决图论中的许多问题,如最短路径查找、连通性检测等。


总结

广度优先搜索(BFS)是一种重要的图遍历算法,它通过队列的方式,按层次访问图的节点,确保遍历顺序是按最短路径进行的。BFS 特别适用于无权图中的最短路径查找、图的连通性检测等问题。在实际编程中,我们利用队列、访问标记数组等简单的数据结构来实现 BFS 的逻辑,并通过例子演示了该算法的逐步执行过程。

掌握 BFS 能让我们更加高效地解决与图相关的各种问题,无论是在竞赛中,还是在实际开发中,BFS 都是一个非常有用的工具。

相关文章:

CSP-J 算法基础 广度优先搜索BFS

文章目录 前言广度优先搜索是什么广度优先搜索的实现BFS 的具体编程实现举例&#xff1a;广度优先搜索的具体步骤初始状态&#xff1a;步骤 1&#xff1a;加入起点节点 1步骤 2&#xff1a;访问队列中的节点 1&#xff0c;加入其邻居节点 2 和 4步骤 3&#xff1a;访问队列中的…...

What is new in C# 7,8,9,10

目录 Whats new in C# 7 C# 7 in Visual Studio 2017 Out Variables Pattern Matching Tuples &#xff08;System.ValueTuple&#xff09; Deconstruct解构 Local Functions Ref Returns and Locals Expression Bodied Members Throw Expressions Generated Async R…...

Sqlserver常用sql

1. 数据库和表操作 创建数据库 CREATE DATABASE DatabaseName; 删除数据库 DROP DATABASE DatabaseName; 创建表 CREATE TABLE TableName ( Column1 DataType1, Column2 DataType2, ... ); 删除表 DROP TABLE TableName; 2. 数据操作 插入数据 INSERT INTO TableNam…...

基于SpringBoot+Vue+MySQL的考研互助交流平台

系统展示 用户前台界面 管理员后台界面 系统背景 本文设计并实现了一个基于SpringBoot、Vue.js和MySQL的考研互助交流平台。该平台旨在为广大考研学子提供一个集资源共享、学习交流、经验分享、心理辅导等功能于一体的综合性在线社区。通过SpringBoot构建高效稳定的后端服务&am…...

chatgpt个人版ssrf漏洞

文章目录 免责申明搜索语法漏洞描述漏洞复现修复建议 免责申明 本文章仅供学习与交流&#xff0c;请勿用于非法用途&#xff0c;均由使用者本人负责&#xff0c;文章作者不为此承担任何责任 搜索语法 fofa title"ChatGPT个人专用版"漏洞描述 该系统是一个开源的…...

如何查看微信聊天记录?四种实用方法查询微信聊天记录,赶快码住!

微信作为我们日常生活中不可或缺的社交工具&#xff0c;记录了大量的聊天内容和重要信息。 当需要查看或恢复微信聊天记录时&#xff0c;很多人可能不知道如何快速、安全地进行操作。 今天&#xff0c;我们就来介绍四种实用的微信聊天记录查询方法&#xff0c;帮助你有效查看微…...

钢材表面缺陷数据集以coco格式做好了数据集的划分,1200张训练集,600张验证集,对应的json文件也在里面

钢材表面缺陷数据集 以coco格式做好了数据集的划分&#xff0c;1200张训练集&#xff0c;600张验证集&#xff0c;对应的json文件也在里面。 钢材表面缺陷检测数据集营销介绍 项目背景&#xff1a; 钢材作为工业生产的重要原材料之一&#xff0c;其表面质量直接影响到成品的性…...

【Lua坑】Lua协程coroutine无法正常完整执行问题

问题&#xff1a;发现Lua协程执行到一半&#xff0c;突然被掐断了一样等到了设定的时间没有正常执行协程后续代码&#xff01;非必现bug&#xff0c;若发生大概率在高频率使用协程时易触发。 LuaFramework或xLua uLua都自带有协程coroutine&#xff0c;而且基本都使用对象池缓…...

istio中serviceentry结合egressgateway的使用

假设有一个外部服务&#xff0c;外部服务ip为&#xff1a;10.10.102.90&#xff0c;其中32033为v1版本&#xff0c;32034为v2版本。 现在需要把这个服务引入到istio中&#xff0c;并且需要配置所有访问该服务的流量都通过egressgateway转发出去。 serviceentry apiVersion: n…...

使用 Python 实现 Windows 应用图标的便捷生成:一站式 PNG 转 ICO 工具20240918

使用 Python 实现 Windows 应用图标的便捷生成&#xff1a;一站式 PNG 转 ICO 工具 在开发 Windows 桌面应用程序时&#xff0c;图标文件&#xff08;ICO&#xff09;的生成是不可忽视的关键步骤。无论是任务栏图标、快捷方式&#xff0c;还是应用程序的主图标&#xff0c;都需…...

编程环境常用命令合集

cmd: python 进入python运行环境 exit()/quit()/ctrlZ 退出环境 rmdir /s venv 删除环境 pip命令&#xff1a; pip list 查看所有库 pip install <库> 安装库 -i <数据源>可指定安装数据源 pip install <库>x.x.x 安装指定版本的库 pip install --upgrade &…...

Qt Creator 集成开发环境 常见问题

1.QtCreator中三种不同编译版本 debug、release、profile 的区别 在 Qt Creator 中&#xff0c;Debug、Release 和 Profile 是三种不同的构建配置&#xff0c;它们主要用于在开发过程中生成不同类型的可执行文件。它们的区别如下&#xff1a; 1.1 Debug&#xff08;调试版本&…...

使用Faiss进行K-Means聚类

&#x1f4dd; 本文需要的前置知识&#xff1a;Faiss的基本使用 目录 1. 源码剖析1.1 参数解释 2. 聚类过程详解2.1 初始化聚类中心2.2 分配步骤&#xff08;Assignment&#xff09;2.3 更新步骤&#xff08;Update&#xff09;2.4 收敛与终止条件 3. GPU 加速3.1 索引结构与 G…...

通过hosts.allow和hosts.deny限制用户登录

1、Hosts.allow和host.deny说明 两个文件是控制远程访问设置的&#xff0c;通过设置这个文件可以允许或者拒绝某个ip或者ip段的客户访问linux的某项服务。如果请求访问的主机名或IP不包含在/etc/hosts.allow中&#xff0c;那么tcpd进程就检查/etc/hosts.deny。看请求访问的主机…...

PWN College 关于sql盲注

在这个场景中&#xff0c;我们需要利用SQL注入漏洞来泄露flag&#xff0c;但是应用程序并不会直接返回查询结果。相反&#xff0c;我们需要根据应用程序的行为差异&#xff08;登录成功与否&#xff09;来推断查询结果。这就是所谓的"布尔盲注"&#xff08;Boolean-b…...

【Linux篇】Http协议(1)(笔记)

目录 一、http基本认识 1. Web客户端和服务器 2. 资源 3. URI 4. URL 5. 事务 6. 方法 7. 状态码 二、HTTP报文 1. 报文的流动 &#xff08;1&#xff09;流入源端服务器 &#xff08;2&#xff09;向下游流动 2. 报文语法 三、TCP连接 1. TCP传输方式 2. TCP连…...

员工疯狂打CALL!解锁企业微信新玩法,2024年必学秘籍来啦!

现在工作离不开电脑手机&#xff0c;公司交流也得用新招。腾讯出了个企业微信&#xff0c;就是给公司用的聊天工具。它功能强大&#xff0c;操作简便&#xff0c;很多公司用它来让工作更高效&#xff0c;团队合作更紧密。接下来&#xff0c;我会简单说说怎么上手企业微信&#…...

Spring boot从0到1 - day01

前言 Spring 框架作为 Java 领域中最受欢迎的开发框架之一&#xff0c;提供了强大的支持来帮助开发者构建高性能、可维护的 Web 应用。 学习目标 Spring 基础 Spring框架是什么&#xff1f;Spring IoC与Aop怎么理解&#xff1f; Spring Boot 的快速构建 Spring 基础 学习…...

Flutter 项目结构的区别

如果需要调用原生代码&#xff0c;请创建一个plugin类型的项目开发。如果需要调用C语言&#xff0c;请参考文档&#xff1a;Flutter项目中调用C语言plugin 其实是 package 的一种&#xff0c;全称是 plugin package&#xff0c;我们简称为 plugin&#xff0c;中文叫插件。 1. A…...

EfficientFormerV2:重新思考视觉变换器以实现与MobileNet相当的尺寸和速度。

摘要 https://arxiv.org/pdf/2212.08059 随着视觉变换器&#xff08;ViTs&#xff09;在计算机视觉任务中的成功&#xff0c;近期的研究尝试优化ViTs的性能和复杂度&#xff0c;以实现在移动设备上的高效部署。提出了多种方法来加速注意力机制&#xff0c;改进低效设计&#xf…...

在软件开发中正确使用MySQL日期时间类型的深度解析

在日常软件开发场景中&#xff0c;时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志&#xff0c;到供应链系统的物流节点时间戳&#xff0c;时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库&#xff0c;其日期时间类型的…...

Cesium1.95中高性能加载1500个点

一、基本方式&#xff1a; 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...

IGP(Interior Gateway Protocol,内部网关协议)

IGP&#xff08;Interior Gateway Protocol&#xff0c;内部网关协议&#xff09; 是一种用于在一个自治系统&#xff08;AS&#xff09;内部传递路由信息的路由协议&#xff0c;主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)

CSI-2 协议详细解析 (一&#xff09; 1. CSI-2层定义&#xff08;CSI-2 Layer Definitions&#xff09; 分层结构 &#xff1a;CSI-2协议分为6层&#xff1a; 物理层&#xff08;PHY Layer&#xff09; &#xff1a; 定义电气特性、时钟机制和传输介质&#xff08;导线&#…...

连锁超市冷库节能解决方案:如何实现超市降本增效

在连锁超市冷库运营中&#xff0c;高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术&#xff0c;实现年省电费15%-60%&#xff0c;且不改动原有装备、安装快捷、…...

渲染学进阶内容——模型

最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...

将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?

Otsu 是一种自动阈值化方法&#xff0c;用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理&#xff0c;能够自动确定一个阈值&#xff0c;将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

CMake 从 GitHub 下载第三方库并使用

有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...

Java面试专项一-准备篇

一、企业简历筛选规则 一般企业的简历筛选流程&#xff1a;首先由HR先筛选一部分简历后&#xff0c;在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如&#xff1a;Boss直聘&#xff08;招聘方平台&#xff09; 直接按照条件进行筛选 例如&#xff1a…...

Android第十三次面试总结(四大 组件基础)

Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成&#xff0c;用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机&#xff1a; ​onCreate()​​ ​调用时机​&#xff1a;Activity 首次创建时调用。​…...