蓝桥杯省赛冲刺(3)广度优先搜索
广度优先搜索(Breadth-First Search, BFS)是一种在图或树等非线性数据结构中遍历节点的算法,它从起始节点开始,按层级逐步向外扩展,即先访问离起始节点最近的节点,再访问这些节点的邻居,然后是邻居的邻居,以此类推。BFS利用队列数据结构来实现这种层级顺序的遍历。以下是广度优先搜索的C语言实现及应用的详细介绍:
### **算法描述**
广度优先搜索遵循以下基本步骤:
1. **初始化**:定义一个标志数组(通常为布尔数组)来记录每个节点是否已被访问。对于无向图,初始化所有节点为未访问状态。
2. **选择起始节点**:从图中选择一个起始节点作为搜索起点。通常在无指定起点时,可以选择任意未访问节点作为起始点。
3. **访问节点**:标记当前节点为已访问,并执行与节点相关操作(如输出节点信息、计算节点属性等)。
4. **入队邻居**:将当前节点的所有未访问邻居节点加入队列。队列确保了节点按照层次顺序被访问。
5. **出队节点**:从队列中取出下一个节点(即最先进入队列的节点,也就是距离起始节点最近且未访问过的节点)。重复步骤3-4,直到队列为空,表示所有与起始节点可达的节点已被访问。
### **C语言实现**
下面是一个使用C语言实现广度优先搜索算法的示例,以遍历一个无向图(用邻接矩阵表示)为例:
```c
#include <stdio.h>
#include <stdbool.h>
#include <queue>
// 定义图的最大顶点数和边的关系类型
#define MAX_VERTEX_NUM 10
typedef int VRType;
// 定义图的邻接矩阵表示
VRType graph[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
// 定义一个标志数组,记录节点是否已被访问
bool visited[MAX_VERTEX_NUM] = {false};
// 使用std::queue来存储待访问节点
std::queue<int> nodeQueue;
// 广度优先搜索函数
void bfs(int start_vertex) {
// 标记起始节点为已访问,并将其加入队列
visited[start_vertex] = true;
nodeQueue.push(start_vertex);
while (!nodeQueue.empty()) {
// 取出队列头部的节点(距离起始节点最近且未访问过的节点)
int current_vertex = nodeQueue.front();
nodeQueue.pop();
printf("Visited node: %d\n", current_vertex); // 输出节点信息
// 遍历当前节点的所有邻居
for (int i = 0; i < MAX_VERTEX_NUM; i++) {
// 如果邻居节点未被访问且与当前节点存在连接
if (!visited[i] && graph[current_vertex][i] != 0) {
// 标记邻居节点为已访问,并将其加入队列
visited[i] = true;
nodeQueue.push(i);
}
}
}
}
int main() {
// 假设已填充了图的邻接矩阵graph
// 选择一个起始节点,这里以节点0为例
bfs(0);
return 0;
}
```
在这个示例中,`bfs()` 函数接受起始节点编号作为参数,初始化队列并开始搜索过程。主函数 `main()` 调用 `bfs()` 以节点0为起始点启动搜索。
### **应用场景**
广度优先搜索在多个领域有广泛应用,包括但不限于:
- **图的连通性检测**:判断图中是否存在从一个节点到另一个节点的路径,同时可以确定两节点之间的最短路径(在所有边权重相等的情况下)。
- **社交网络中的朋友推荐**:查找与用户最近的人脉关系。
- **网络路由**:在网络中寻找最短路径(例如,IP路由表的构建)。
- **游戏AI**:在有限的行动空间内寻找最优或近似最优路径(如棋类游戏、迷宫求解等)。
- **网页抓取**:用于构建网站的目录结构或抓取特定深度的网页。
总之,广度优先搜索以其层级遍历的特性,适用于需要快速找到离起点最近节点及其路径,或解决最短路径问题(在边权相同的情况下)的情况。在C语言中,借助标准库提供的队列数据结构,可以方便地实现BFS算法。
相关文章:

蓝桥杯省赛冲刺(3)广度优先搜索
广度优先搜索(Breadth-First Search, BFS)是一种在图或树等非线性数据结构中遍历节点的算法,它从起始节点开始,按层级逐步向外扩展,即先访问离起始节点最近的节点,再访问这些节点的邻居,然后是邻…...

网页内容生成图片,这18般武艺你会几种呢?
前言 关于【SSD系列】: 前端一些有意思的内容,旨在3-10分钟里, 500-1000字,有所获,又不为所累。 网页截图,windows内置了快捷命令和软件,chrome开发者工具也能一键截图,html2canva…...

pytest的时候输出一个F后面跟很多绿色的点解读
使用pytest来测试pyramid和kotti项目,在kotti项目测试的时候,输出一个F后面跟很多绿色的点,是什么意思呢? 原来在使用pytest进行测试时,输出中的“F”代表一个失败的测试(Failed),而…...

算法打卡day33
今日任务: 1)509. 斐波那契数 2)70. 爬楼梯 3)746.使用最小花费爬楼梯 509. 斐波那契数 题目链接:509. 斐波那契数 - 力扣(LeetCode) 斐波那契数,通常用 F(n) 表示,形成…...

《疯狂java讲义》Java AWT图形化编程中文显示
《疯狂java讲义》第六版第十一章AWT中文没有办法显示问题解决 VM Options设置为-Dfile.encodinggbk 需要增加变量 或者这边直接设置gbk 此外如果用swing 就不会产生这个问题了。...
Python3 标准库,API文档链接
一、标准库 即当你安装python3 后就自己携带的一些已经提供好的工具模块,工具类,可以专门用来某一类相关问题,达到辅助日常工作或者个人想法的一些成品库 类似的 C ,Java 等等也都有自己的标准库和使用文档 常见的一些: os 模块…...

【Web】CTFSHOW-ThinkPHP5-6反序列化刷题记录(全)
目录 web611 web612 web613-622 web623 web624-626 纯记录exp,链子不作赘述 web611 具体分析: ThinkPHP-Vuln/ThinkPHP5/ThinkPHP5.1.X反序列化利用链.md at master Mochazz/ThinkPHP-Vuln GitHub 题目直接给了反序列化入口 exp: <?ph…...

AR智能眼镜方案_MTK平台安卓主板芯片|光学解决方案
AR眼镜作为一种引人注目的创新产品,其芯片、显示屏和光学方案是决定整机成本和性能的关键因素。在这篇文章中,我们将探讨AR眼镜的关键技术,并介绍一种高性能的AR眼镜方案,旨在为用户带来卓越的体验。 AR眼镜的芯片选型至关重要。一…...

Android网络抓包--Charles
一、Android抓包方式 对Https降级进行抓包,降级成Http使用抓包工具对Https进行抓包 二、常用的抓包工具 wireshark:侧重于TCP、UDP传输层,HTTP/HTTPS也能抓包,但不能解密HTTPS报文。比较复杂fiddler:支持HTTP/HTTPS…...
【LeetCode热题100】238. 除自身以外数组的乘积(数组)
一.题目要求 给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 **不要使用除法,**且在…...

《哈迪斯》自带的Lua解释器是哪个版本?
玩过《哈迪斯》(英文名:Hades)吗?最近在研究怎么给这款游戏做MOD,想把它的振动体验升级到更高品质的RichTap。N站下载了一些别人做的MOD,发现很多都基于相同的格式,均是对游戏.sjon文件或.lua文…...
Java内存泄漏内存溢出
1.定义 OOM内存溢出是指应用程序尝试使用更多内存资源,而系统无足够的内存,导致程序崩溃。 内存泄漏是指应用程序中分配的内存未能被正确释放,导致系统中的可用内存逐渐减少。 2.内存泄漏的原因 可能包括对象引用未被释放、缓存未被清理等。 …...
【springboot】项目启动时打印全部接口方法
方法:在你springboot项目的基础上,创建下面的类: package com.llq.wahaha.listener;import org.springframework.beans.factory.annotation.Autowired; import org.springframework.context.ApplicationContext; import org.springframework…...

单例19c RMAN数据迁移方案
一、环境说明 源库 目标库 IP 192.168.37.200 192.168.37.202 系统版本 RedHat 7.9 RedHat 7.9 数据库版本 19.3.0.0.0 19.3.0.0.0 SID beg beg hostname beg rman 数据量 1353M 说明:源库已经创建数据库实例,并且存在用户kk和他创建的表空间…...

05—面向对象(上)
一、面向对象编程 1、类和对象 (1)什么是类 类是一类具有相同特性的事物的抽象描述,是一组相关属性和行为的集合。 属性:就是该事物的状态信息。行为:就是在你这个程序中,该状态信息要做什么操作&#x…...
【LeetCode热题100】【链表】两数相加
题目链接:2. 两数相加 - 力扣(LeetCode) 基本思路同:【leetcode】大数相加-CSDN博客 数值的位置已经倒过来了,用一个进位记录进位,用一个数记录和,链表到空了就当成0 class Solution { publi…...
Linux命令学习—linux 的硬件管理
1.1、linux 的硬件管理 1.1.1、计算机的硬件管理 在 linux 下,计算机所有设备是以文件的形势存在的。 在 linux 下查看硬件信息 ①、lspci 列出所有的 PCI 设备 ②、fdisk -l 查看存储设备信息 ③、查看/proc 目录下相应的文件来查看一些设备信息 cat /proc/cp…...

通讯录项目(用c语言实现)
一.什么是通讯录 通讯录是一种用于存储联系人信息的工具或应用程序。它是一种电子化的地址簿,用于记录和管理个人、机构或组织的联系方式,如姓名、电话号码、电子邮件地址和邮寄地址等。通讯录的目的是方便用户在需要时查找和联系他人。 通讯录通常以列…...

让大模型落地有“技”可循
“2018年,随着Transformer预训练模型的兴起,自然语言处理(NLP)学术圈中形成了一个主流观点——NLP领域的不同技术方向,如文本分类、文本匹配、序列标注等,最终都会被归结到文本生成这一核心任务之下。”这是…...

java:字符集和字符流
字符集 规定了字符和二进制之间对应关系的一张表 字节是计算机最基本的存储单位 字符则是通过字符组成和编码而成的文本 常见字符集 1,ASCII字符集 基础字符编码标准,包含128个字符,只包括英文字母,数字和一些常见的符号 一个字节表示一个字符 所有的字符集均兼容ASCII…...

Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误
HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误,它们的含义、原因和解决方法都有显著区别。以下是详细对比: 1. HTTP 406 (Not Acceptable) 含义: 客户端请求的内容类型与服务器支持的内容类型不匹…...

微信小程序之bind和catch
这两个呢,都是绑定事件用的,具体使用有些小区别。 官方文档: 事件冒泡处理不同 bind:绑定的事件会向上冒泡,即触发当前组件的事件后,还会继续触发父组件的相同事件。例如,有一个子视图绑定了b…...

CTF show Web 红包题第六弹
提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框,很难让人不联想到SQL注入,但提示都说了不是SQL注入,所以就不往这方面想了 先查看一下网页源码,发现一段JavaScript代码,有一个关键类ctfs…...
java 实现excel文件转pdf | 无水印 | 无限制
文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...
FastAPI 教程:从入门到实践
FastAPI 是一个现代、快速(高性能)的 Web 框架,用于构建 API,支持 Python 3.6。它基于标准 Python 类型提示,易于学习且功能强大。以下是一个完整的 FastAPI 入门教程,涵盖从环境搭建到创建并运行一个简单的…...

【网络安全产品大调研系列】2. 体验漏洞扫描
前言 2023 年漏洞扫描服务市场规模预计为 3.06(十亿美元)。漏洞扫描服务市场行业预计将从 2024 年的 3.48(十亿美元)增长到 2032 年的 9.54(十亿美元)。预测期内漏洞扫描服务市场 CAGR(增长率&…...

【2025年】解决Burpsuite抓不到https包的问题
环境:windows11 burpsuite:2025.5 在抓取https网站时,burpsuite抓取不到https数据包,只显示: 解决该问题只需如下三个步骤: 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...

高危文件识别的常用算法:原理、应用与企业场景
高危文件识别的常用算法:原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件,如包含恶意代码、敏感数据或欺诈内容的文档,在企业协同办公环境中(如Teams、Google Workspace)尤为重要。结合大模型技术&…...
CMake控制VS2022项目文件分组
我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...

佰力博科技与您探讨热释电测量的几种方法
热释电的测量主要涉及热释电系数的测定,这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中,积分电荷法最为常用,其原理是通过测量在电容器上积累的热释电电荷,从而确定热释电系数…...