当前位置: 首页 > 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…...

Prompt Tuning、P-Tuning、Prefix Tuning的区别

一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》

引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...

逻辑回归:给不确定性划界的分类大师

想象你是一名医生。面对患者的检查报告&#xff08;肿瘤大小、血液指标&#xff09;&#xff0c;你需要做出一个**决定性判断**&#xff1a;恶性还是良性&#xff1f;这种“非黑即白”的抉择&#xff0c;正是**逻辑回归&#xff08;Logistic Regression&#xff09;** 的战场&a…...

测试markdown--肇兴

day1&#xff1a; 1、去程&#xff1a;7:04 --11:32高铁 高铁右转上售票大厅2楼&#xff0c;穿过候车厅下一楼&#xff0c;上大巴车 &#xffe5;10/人 **2、到达&#xff1a;**12点多到达寨子&#xff0c;买门票&#xff0c;美团/抖音&#xff1a;&#xffe5;78人 3、中饭&a…...

【决胜公务员考试】求职OMG——见面课测验1

2025最新版&#xff01;&#xff01;&#xff01;6.8截至答题&#xff0c;大家注意呀&#xff01; 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:&#xff08; B &#xff09; A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...

Redis数据倾斜问题解决

Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中&#xff0c;部分节点存储的数据量或访问量远高于其他节点&#xff0c;导致这些节点负载过高&#xff0c;影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...

Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)

参考官方文档&#xff1a;https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java&#xff08;供 Kotlin 使用&#xff09; 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...

Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)

Aspose.PDF 限制绕过方案&#xff1a;Java 字节码技术实战分享&#xff08;仅供学习&#xff09; 一、Aspose.PDF 简介二、说明&#xff08;⚠️仅供学习与研究使用&#xff09;三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...

BLEU评分:机器翻译质量评估的黄金标准

BLEU评分&#xff1a;机器翻译质量评估的黄金标准 1. 引言 在自然语言处理(NLP)领域&#xff0c;衡量一个机器翻译模型的性能至关重要。BLEU (Bilingual Evaluation Understudy) 作为一种自动化评估指标&#xff0c;自2002年由IBM的Kishore Papineni等人提出以来&#xff0c;…...