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,先进先出)来实现按层次的搜索。具体实现步骤如下:
- 初始化:选择一个起始节点,将其标记为已访问并加入队列。
- 遍历:从队列中取出一个节点,检查其所有未访问的邻接节点,将它们标记为已访问并加入队列。
- 重复:不断从队列中取出节点并访问其邻接节点,直到队列为空。
通过这种方式,BFS 能逐层遍历图的节点,确保从起点到任意节点的访问顺序是按最短路径进行的。
BFS 的具体编程实现
在编程中,BFS 通常使用以下数据结构来实现:
- 队列:用于保存当前层次要访问的节点。
- 访问标记数组:用于记录每个节点是否已经访问过,避免重复访问。
- 图的表示方式:通常使用邻接表或邻接矩阵来存储图的结构信息。
BFS 的伪代码步骤如下:
- 将起点加入队列,并将其标记为已访问。
- 当队列不为空时,取出队列的第一个节点,检查该节点所有邻接节点。
- 对于每个未访问的邻接节点,将其标记为已访问,并加入队列。
- 重复该过程,直到队列为空或找到目标节点。
举例:广度优先搜索的具体步骤
我们通过一个简单的例子来演示 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;
}
代码解释
-
数据结构定义:
AdjListNode
:表示图中每条边的链表节点。AdjList
:表示每个顶点的邻接链表。Graph
:包含邻接表数组和顶点数的图结构。
-
图的初始化:
createNode
:创建链表节点。createGraph
:初始化图,创建邻接表数组。addEdge
:添加无向边,更新源顶点和目标顶点的邻接表。
-
BFS 实现:
- 初始化访问标记数组和队列。
- 从起始节点开始,标记为已访问并入队。
- 逐层访问图的节点,并将未访问的邻接节点入队。
- 打印每个访问到的节点。
-
主函数:
- 创建图,添加边,调用 BFS 函数,并释放内存。
总结
这段代码演示了如何用 C 语言实现广度优先搜索(BFS)算法。通过邻接表存储图,BFS 遍历每个节点,并按层次访问所有邻接节点。掌握 BFS 的实现可以帮助我们高效解决图论中的许多问题,如最短路径查找、连通性检测等。
总结
广度优先搜索(BFS)是一种重要的图遍历算法,它通过队列的方式,按层次访问图的节点,确保遍历顺序是按最短路径进行的。BFS 特别适用于无权图中的最短路径查找、图的连通性检测等问题。在实际编程中,我们利用队列、访问标记数组等简单的数据结构来实现 BFS 的逻辑,并通过例子演示了该算法的逐步执行过程。
掌握 BFS 能让我们更加高效地解决与图相关的各种问题,无论是在竞赛中,还是在实际开发中,BFS 都是一个非常有用的工具。
相关文章:
CSP-J 算法基础 广度优先搜索BFS
文章目录 前言广度优先搜索是什么广度优先搜索的实现BFS 的具体编程实现举例:广度优先搜索的具体步骤初始状态:步骤 1:加入起点节点 1步骤 2:访问队列中的节点 1,加入其邻居节点 2 和 4步骤 3:访问队列中的…...
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 (System.ValueTuple) 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漏洞
文章目录 免责申明搜索语法漏洞描述漏洞复现修复建议 免责申明 本文章仅供学习与交流,请勿用于非法用途,均由使用者本人负责,文章作者不为此承担任何责任 搜索语法 fofa title"ChatGPT个人专用版"漏洞描述 该系统是一个开源的…...

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

钢材表面缺陷数据集以coco格式做好了数据集的划分,1200张训练集,600张验证集,对应的json文件也在里面
钢材表面缺陷数据集 以coco格式做好了数据集的划分,1200张训练集,600张验证集,对应的json文件也在里面。 钢材表面缺陷检测数据集营销介绍 项目背景: 钢材作为工业生产的重要原材料之一,其表面质量直接影响到成品的性…...
【Lua坑】Lua协程coroutine无法正常完整执行问题
问题:发现Lua协程执行到一半,突然被掐断了一样等到了设定的时间没有正常执行协程后续代码!非必现bug,若发生大概率在高频率使用协程时易触发。 LuaFramework或xLua uLua都自带有协程coroutine,而且基本都使用对象池缓…...
istio中serviceentry结合egressgateway的使用
假设有一个外部服务,外部服务ip为:10.10.102.90,其中32033为v1版本,32034为v2版本。 现在需要把这个服务引入到istio中,并且需要配置所有访问该服务的流量都通过egressgateway转发出去。 serviceentry apiVersion: n…...
使用 Python 实现 Windows 应用图标的便捷生成:一站式 PNG 转 ICO 工具20240918
使用 Python 实现 Windows 应用图标的便捷生成:一站式 PNG 转 ICO 工具 在开发 Windows 桌面应用程序时,图标文件(ICO)的生成是不可忽视的关键步骤。无论是任务栏图标、快捷方式,还是应用程序的主图标,都需…...
编程环境常用命令合集
cmd: python 进入python运行环境 exit()/quit()/ctrlZ 退出环境 rmdir /s venv 删除环境 pip命令: pip list 查看所有库 pip install <库> 安装库 -i <数据源>可指定安装数据源 pip install <库>x.x.x 安装指定版本的库 pip install --upgrade &…...
Qt Creator 集成开发环境 常见问题
1.QtCreator中三种不同编译版本 debug、release、profile 的区别 在 Qt Creator 中,Debug、Release 和 Profile 是三种不同的构建配置,它们主要用于在开发过程中生成不同类型的可执行文件。它们的区别如下: 1.1 Debug(调试版本&…...
使用Faiss进行K-Means聚类
📝 本文需要的前置知识:Faiss的基本使用 目录 1. 源码剖析1.1 参数解释 2. 聚类过程详解2.1 初始化聚类中心2.2 分配步骤(Assignment)2.3 更新步骤(Update)2.4 收敛与终止条件 3. GPU 加速3.1 索引结构与 G…...

通过hosts.allow和hosts.deny限制用户登录
1、Hosts.allow和host.deny说明 两个文件是控制远程访问设置的,通过设置这个文件可以允许或者拒绝某个ip或者ip段的客户访问linux的某项服务。如果请求访问的主机名或IP不包含在/etc/hosts.allow中,那么tcpd进程就检查/etc/hosts.deny。看请求访问的主机…...
PWN College 关于sql盲注
在这个场景中,我们需要利用SQL注入漏洞来泄露flag,但是应用程序并不会直接返回查询结果。相反,我们需要根据应用程序的行为差异(登录成功与否)来推断查询结果。这就是所谓的"布尔盲注"(Boolean-b…...

【Linux篇】Http协议(1)(笔记)
目录 一、http基本认识 1. Web客户端和服务器 2. 资源 3. URI 4. URL 5. 事务 6. 方法 7. 状态码 二、HTTP报文 1. 报文的流动 (1)流入源端服务器 (2)向下游流动 2. 报文语法 三、TCP连接 1. TCP传输方式 2. TCP连…...

员工疯狂打CALL!解锁企业微信新玩法,2024年必学秘籍来啦!
现在工作离不开电脑手机,公司交流也得用新招。腾讯出了个企业微信,就是给公司用的聊天工具。它功能强大,操作简便,很多公司用它来让工作更高效,团队合作更紧密。接下来,我会简单说说怎么上手企业微信&#…...

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

Flutter 项目结构的区别
如果需要调用原生代码,请创建一个plugin类型的项目开发。如果需要调用C语言,请参考文档:Flutter项目中调用C语言plugin 其实是 package 的一种,全称是 plugin package,我们简称为 plugin,中文叫插件。 1. A…...
EfficientFormerV2:重新思考视觉变换器以实现与MobileNet相当的尺寸和速度。
摘要 https://arxiv.org/pdf/2212.08059 随着视觉变换器(ViTs)在计算机视觉任务中的成功,近期的研究尝试优化ViTs的性能和复杂度,以实现在移动设备上的高效部署。提出了多种方法来加速注意力机制,改进低效设计…...

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,开始写第二篇的内容了。这篇博客主要能写一下: 如何给一些三方库按照xmake方式进行封装,供调用如何按…...

《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》
引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...
逻辑回归:给不确定性划界的分类大师
想象你是一名医生。面对患者的检查报告(肿瘤大小、血液指标),你需要做出一个**决定性判断**:恶性还是良性?这种“非黑即白”的抉择,正是**逻辑回归(Logistic Regression)** 的战场&a…...
测试markdown--肇兴
day1: 1、去程:7:04 --11:32高铁 高铁右转上售票大厅2楼,穿过候车厅下一楼,上大巴车 ¥10/人 **2、到达:**12点多到达寨子,买门票,美团/抖音:¥78人 3、中饭&a…...
【决胜公务员考试】求职OMG——见面课测验1
2025最新版!!!6.8截至答题,大家注意呀! 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:( B ) A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...

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

Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)
参考官方文档:https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java(供 Kotlin 使用) 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...

Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)
Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习) 一、Aspose.PDF 简介二、说明(⚠️仅供学习与研究使用)三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...
BLEU评分:机器翻译质量评估的黄金标准
BLEU评分:机器翻译质量评估的黄金标准 1. 引言 在自然语言处理(NLP)领域,衡量一个机器翻译模型的性能至关重要。BLEU (Bilingual Evaluation Understudy) 作为一种自动化评估指标,自2002年由IBM的Kishore Papineni等人提出以来,…...