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

蓝桥杯省赛冲刺(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算法。

9093b12e7cb8415e83a3794f3bf907f6.jpg

相关文章:

蓝桥杯省赛冲刺(3)广度优先搜索

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

网页内容生成图片,这18般武艺你会几种呢?

前言 关于【SSD系列】&#xff1a; 前端一些有意思的内容&#xff0c;旨在3-10分钟里&#xff0c; 500-1000字&#xff0c;有所获&#xff0c;又不为所累。 网页截图&#xff0c;windows内置了快捷命令和软件&#xff0c;chrome开发者工具也能一键截图&#xff0c;html2canva…...

pytest的时候输出一个F后面跟很多绿色的点解读

使用pytest来测试pyramid和kotti项目&#xff0c;在kotti项目测试的时候&#xff0c;输出一个F后面跟很多绿色的点&#xff0c;是什么意思呢&#xff1f; 原来在使用pytest进行测试时&#xff0c;输出中的“F”代表一个失败的测试&#xff08;Failed&#xff09;&#xff0c;而…...

算法打卡day33

今日任务&#xff1a; 1&#xff09;509. 斐波那契数 2&#xff09;70. 爬楼梯 3&#xff09;746.使用最小花费爬楼梯 509. 斐波那契数 题目链接&#xff1a;509. 斐波那契数 - 力扣&#xff08;LeetCode&#xff09; 斐波那契数&#xff0c;通常用 F(n) 表示&#xff0c;形成…...

《疯狂java讲义》Java AWT图形化编程中文显示

《疯狂java讲义》第六版第十一章AWT中文没有办法显示问题解决 VM Options设置为-Dfile.encodinggbk 需要增加变量 或者这边直接设置gbk 此外如果用swing 就不会产生这个问题了。...

Python3 标准库,API文档链接

一、标准库 即当你安装python3 后就自己携带的一些已经提供好的工具模块&#xff0c;工具类&#xff0c;可以专门用来某一类相关问题&#xff0c;达到辅助日常工作或者个人想法的一些成品库 类似的 C ,Java 等等也都有自己的标准库和使用文档 常见的一些&#xff1a; os 模块…...

【Web】CTFSHOW-ThinkPHP5-6反序列化刷题记录(全)

目录 web611 web612 web613-622 web623 web624-626 纯记录exp&#xff0c;链子不作赘述 web611 具体分析&#xff1a; ThinkPHP-Vuln/ThinkPHP5/ThinkPHP5.1.X反序列化利用链.md at master Mochazz/ThinkPHP-Vuln GitHub 题目直接给了反序列化入口 exp: <?ph…...

AR智能眼镜方案_MTK平台安卓主板芯片|光学解决方案

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

Android网络抓包--Charles

一、Android抓包方式 对Https降级进行抓包&#xff0c;降级成Http使用抓包工具对Https进行抓包 二、常用的抓包工具 wireshark&#xff1a;侧重于TCP、UDP传输层&#xff0c;HTTP/HTTPS也能抓包&#xff0c;但不能解密HTTPS报文。比较复杂fiddler&#xff1a;支持HTTP/HTTPS…...

【LeetCode热题100】238. 除自身以外数组的乘积(数组)

一.题目要求 给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 **不要使用除法&#xff0c;**且在…...

《哈迪斯》自带的Lua解释器是哪个版本?

玩过《哈迪斯》&#xff08;英文名&#xff1a;Hades&#xff09;吗&#xff1f;最近在研究怎么给这款游戏做MOD&#xff0c;想把它的振动体验升级到更高品质的RichTap。N站下载了一些别人做的MOD&#xff0c;发现很多都基于相同的格式&#xff0c;均是对游戏.sjon文件或.lua文…...

Java内存泄漏内存溢出

1.定义 OOM内存溢出是指应用程序尝试使用更多内存资源&#xff0c;而系统无足够的内存&#xff0c;导致程序崩溃。 内存泄漏是指应用程序中分配的内存未能被正确释放&#xff0c;导致系统中的可用内存逐渐减少。 2.内存泄漏的原因 可能包括对象引用未被释放、缓存未被清理等。 …...

【springboot】项目启动时打印全部接口方法

方法&#xff1a;在你springboot项目的基础上&#xff0c;创建下面的类&#xff1a; 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 说明:源库已经创建数据库实例&#xff0c;并且存在用户kk和他创建的表空间…...

05—面向对象(上)

一、面向对象编程 1、类和对象 &#xff08;1&#xff09;什么是类 类是一类具有相同特性的事物的抽象描述&#xff0c;是一组相关属性和行为的集合。 属性&#xff1a;就是该事物的状态信息。行为&#xff1a;就是在你这个程序中&#xff0c;该状态信息要做什么操作&#x…...

【LeetCode热题100】【链表】两数相加

题目链接&#xff1a;2. 两数相加 - 力扣&#xff08;LeetCode&#xff09; 基本思路同&#xff1a;【leetcode】大数相加-CSDN博客 数值的位置已经倒过来了&#xff0c;用一个进位记录进位&#xff0c;用一个数记录和&#xff0c;链表到空了就当成0 class Solution { publi…...

Linux命令学习—linux 的硬件管理

1.1、linux 的硬件管理 1.1.1、计算机的硬件管理 在 linux 下&#xff0c;计算机所有设备是以文件的形势存在的。 在 linux 下查看硬件信息 ①、lspci 列出所有的 PCI 设备 ②、fdisk -l 查看存储设备信息 ③、查看/proc 目录下相应的文件来查看一些设备信息 cat /proc/cp…...

通讯录项目(用c语言实现)

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

让大模型落地有“技”可循

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

java:字符集和字符流

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

Java常见的设计模式

Java常见的设计模式 工厂模式&#xff08;Factory Pattern&#xff09;单例模式&#xff08;Singleton Pattern&#xff09;代理模式模式&#xff08;Proxy Pattern&#xff09;适配器模式&#xff08;Adapter Pattern&#xff09;观察者模式&#xff08;Observer Pattern&…...

Oracle 19c RAC集群相关日志

1.DB日志&#xff08;数据库日志&#xff09; Redo Log&#xff08;重做日志&#xff09;&#xff1a; 在Oracle数据库中&#xff0c;重做日志记录了数据库发生的所有修改操作&#xff0c;包括数据的插入&#xff0c;更新和删除。在RAC的环境中&#xff0c;每个实例都有自己的重…...

TR4 - Transformer中的多头注意力机制

目录 前言自注意力机制Self-Attention层的具体机制Self-Attention 矩阵计算 多头注意力机制例子解析 代码实现总结与心得体会 前言 多头注意力机制可以说是Transformer中最主要的模块&#xff0c;没有之一。这次我们来仔细分析一下注意力机制与多头注意力机制。 自注意力机制…...

three.js跟着教程实现VR效果(四)

参照教程&#xff1a;https://juejin.cn/post/6973865268426571784&#xff08;作者&#xff1a;大帅老猿&#xff09; 1.WebGD3D引擎 用three.js &#xff08;1&#xff09;使用立方体6面图 camera放到 立方体的中间 like “回” 让贴图向内翻转 &#xff08;2&#xff09;使…...

AI预测体彩排3第1弹【2024年4月12日预测--第1套算法开始计算第1次测试】

前面经过多个模型几十次对福彩3D的预测&#xff0c;积累了一定的经验&#xff0c;摸索了一些稳定的规律&#xff0c;有很多彩友让我也出一下排列3的预测结果&#xff0c;我认为目前时机已成熟&#xff0c;且由于福彩3D和体彩排列3的玩法完全一样&#xff0c;我认为3D的规律和模…...

spring 中的控制反转

在Spring框架中&#xff0c;控制反转&#xff08;IoC&#xff0c;Inversion of Control&#xff09;是指将对象的创建和管理交给了容器&#xff0c;而不是在应用程序代码中直接创建对象。在传统的编程模式中&#xff0c;应用程序代码通常负责创建对象并管理它们的生命周期&…...

GO并发总是更快吗?

许多开发人员的一个误解是,并发解决方案总是比串行更快,大错特错。解决方案的整体性能取决于许多因素,例如,结构的效率(并发)、可以并行处理的部分以及计算单元的竞争程度。 1. GO调度 线程是操作系统可以执行的最小单元。如果一个进程想要同时执行多个动作,它可以启动…...

echarts折线图自定义打点标记小工具

由于没研究明白echarts怎么用label和lableLine实现自定义打点标记&#xff0c;索性用markPoint把长方形压扁成线模拟了一番自定义打点标记&#xff0c;记录下来备用。&#xff08;markLine同理也能实现&#xff09; 实现代码如下&#xff1a; <!DOCTYPE html> <html…...

【图论】Leetcode 200. 岛屿数量【中等】

岛屿数量 给你一个由 ‘1’&#xff08;陆地&#xff09;和 ‘0’&#xff08;水&#xff09;组成的的二维网格&#xff0c;请你计算网格中岛屿的数量。 岛屿总是被水包围&#xff0c;并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。 此外&#xff0c;你可以…...

酒店大厅装水离子雾化壁炉前和装后对比

在酒店大厅装水离子雾化壁炉之前和之后&#xff0c;大厅的氛围和体验会有显著的对比&#xff1a; 装水离子雾化壁炉之前&#xff1a; 传统感&#xff1a;在壁炉安装之前&#xff0c;大厅可能会有传统的装饰或者简单的暖气设备&#xff0c;缺乏现代化的元素。这种传统感可能会…...