BFS算法篇——广度优先搜索,探索未知的旅程(上)
文章目录
- 前言
- 一、BFS的思路
- 二、BFS的C语言实现
- 1. 图的表示
- 2. BFS的实现
- 三、代码解析
- 四、输出结果
- 五、总结
前言
广度优先搜索(BFS)是一种广泛应用于图论中的算法,常用于寻找最短路径、图的遍历等问题。与深度优先搜索(DFS)不同,BFS通过层级地探索节点来确保最先访问的节点距离源点较近,因此它可以用来求解最短路径问题。让我们深入了解这个算法,并通过具体的例子和代码来进一步掌握它的实现。
一、BFS的思路
BFS的主要思想是从起始节点开始,首先访问该节点的所有邻接节点,然后再访问这些邻接节点的邻接节点。BFS利用队列的先进先出(FIFO)特性保证了节点是按层次顺序被访问的。
二、BFS的C语言实现
1. 图的表示
在C语言中,我们常用邻接表来表示图。对于无向图,我们可以使用一个邻接矩阵或者邻接链表。在这里,我们采用邻接链表表示图。
2. BFS的实现
以下是C语言实现BFS算法的具体代码,图使用邻接表表示:
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>#define MAX_NODES 6 // 节点数量// 图的邻接表结构
typedef struct Node {int data;struct Node* next;
} Node;typedef struct Graph {Node* adjList[MAX_NODES];
} Graph;// 队列结构
typedef struct Queue {int items[MAX_NODES];int front, rear;
} Queue;// 创建一个新的图
Graph* createGraph() {Graph* graph = (Graph*)malloc(sizeof(Graph));for (int i = 0; i < MAX_NODES; i++) {graph->adjList[i] = NULL;}return graph;
}// 向图中添加一条边
void addEdge(Graph* graph, int src, int dest) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->data = dest;newNode->next = graph->adjList[src];graph->adjList[src] = newNode;// 因为是无向图,所以添加反向边newNode = (Node*)malloc(sizeof(Node));newNode->data = src;newNode->next = graph->adjList[dest];graph->adjList[dest] = newNode;
}// 初始化队列
void initQueue(Queue* q) {q->front = -1;q->rear = -1;
}// 入队
void enqueue(Queue* q, int value) {if (q->rear == MAX_NODES - 1) {printf("队列已满\n");return;}if (q->front == -1) {q->front = 0;}q->rear++;q->items[q->rear] = value;
}// 出队
int dequeue(Queue* q) {if (q->front == -1) {printf("队列为空\n");return -1;}int item = q->items[q->front];q->front++;if (q->front > q->rear) {q->front = q->rear = -1;}return item;
}// 判断队列是否为空
bool isQueueEmpty(Queue* q) {return q->front == -1;
}// 广度优先搜索BFS
void bfs(Graph* graph, int start) {bool visited[MAX_NODES] = {false}; // 访问标志数组Queue q;initQueue(&q);// 标记起始节点为已访问,并入队visited[start] = true;enqueue(&q, start);while (!isQueueEmpty(&q)) {// 出队并访问节点int node = dequeue(&q);printf("%c ", node + 'A'); // 输出节点(假设节点是字母A, B, C...)// 遍历当前节点的所有邻接节点Node* temp = graph->adjList[node];while (temp) {int adjNode = temp->data;if (!visited[adjNode]) {visited[adjNode] = true;enqueue(&q, adjNode);}temp = temp->next;}}
}int main() {// 创建图并添加边Graph* graph = createGraph();addEdge(graph, 0, 1); // A - BaddEdge(graph, 0, 2); // A - CaddEdge(graph, 1, 3); // B - DaddEdge(graph, 1, 4); // B - EaddEdge(graph, 2, 4); // C - EaddEdge(graph, 3, 5); // D - FaddEdge(graph, 4, 5); // E - F// 执行BFS从节点A(索引0)开始printf("BFS遍历结果: ");bfs(graph, 0);// 释放内存free(graph);return 0;
}
三、代码解析
图的表示:
- 图使用邻接表表示。每个节点用一个链表来存储与其直接相连的节点。Graph结构体中有一个数组 adjList 来保存所有节点的邻接链表。
队列的实现:
- 队列用数组来实现,包含 front 和 rear 来管理队列的操作。队列用于按顺序访问图的每个节点。
BFS的实现:
- 使用队列来管理待访问的节点。首先将起始节点标记为已访问并入队。然后逐步出队并访问节点,访问节点的邻接节点,如果邻接节点未被访问,则将其标记为已访问并入队。
- 输出遍历的节点(假设节点为字母,如 A, B, C, …)。
四、输出结果
假设图的结构如下所示:
A -- B -- D| | |C -- E -- F
输出结果将为:
BFS遍历结果: A B C D E F
这意味着从节点 A 开始,BFS按层次遍历的顺序访问了图中的所有节点。
五、总结
- BFS是一种通过逐层扩展来遍历图的算法,通常用于求解最短路径问题、图的遍历等。
- 在C语言中,BFS通常使用队列来实现,队列的先进先出特性确保了图的层次遍历。
- 本例中通过邻接表表示图,使用队列来实现BFS遍历,从而找到节点间的最短路径。
- 广度优先搜索在实际问题中具有广泛的应用,例如在社交网络分析、路径规划等方面,都可以发挥其强大的作用。
本篇关于BFS算法篇的介绍就暂告段落啦,希望能对大家的学习产生帮助,欢迎各位佬前来支持斧正!!!

相关文章:
BFS算法篇——广度优先搜索,探索未知的旅程(上)
文章目录 前言一、BFS的思路二、BFS的C语言实现1. 图的表示2. BFS的实现 三、代码解析四、输出结果五、总结 前言 广度优先搜索(BFS)是一种广泛应用于图论中的算法,常用于寻找最短路径、图的遍历等问题。与深度优先搜索(DFS&…...
mongodb 使用内存过大分析
os 分析 内存使用 ps aux|head -1;ps aux|grep -v PID|sort -rn -k 4|head -10swap 使用 for i in $(ls /proc | grep "^[0-9]" | awk $0>100); do awk /Swap:/{aa$2}END{print "$i",a/1024"M"} /proc/$i/smaps;done| sort -k2nr | headmo…...
CNN-day5-经典神经网络LeNets5
经典神经网络-LeNets5 1998年Yann LeCun等提出的第一个用于手写数字识别问题并产生实际商业(邮政行业)价值的卷积神经网络 参考:论文笔记:Gradient-Based Learning Applied to Document Recognition-CSDN博客 1 网络模型结构 …...
登录到docker里
在Docker中登录到容器通常有两种情况: 登录到正在运行的容器内部:如果你想要进入到正在运行的容器内部,可以使用docker exec命令。 登录到容器中并启动一个shell:如果你想要启动一个容器,并在其中启动一个shell&…...
利用PHP爬虫开发获取淘宝分类详情:解锁电商数据新视角
在电商领域,淘宝作为中国最大的电商平台之一,其分类详情数据对于市场分析、竞争策略制定以及电商运营优化具有极高的价值。通过PHP爬虫技术,我们可以高效地获取这些数据,为电商从业者提供强大的数据支持。本文将详细介绍如何使用P…...
LeetCode 142题解|环形链表II的快慢指针法(含数学证明)
题目如下: 解题过程如下: 思路:快慢指针在环里一定会相遇,相遇结点到入环起始结点的距离 链表头结点到入环起始结点的距离(距离看从左往右的方向,也就是单链表的方向),从链表头结点…...
[图文]课程讲解片段-Fowler分析模式的剖析和实现01
解说: GJJ-004-1,分析模式高阶Fowler分析模式的剖析和实现,这个课是针对Martin Fowler的《分析模式》那本书里面的模式来讲解,对里面的模式来剖析,然后用代码来实现。 做到这一步的,我们这个是世界上独…...
Dify使用
1. 概述 官网:Dify.AI 生成式 AI 应用创新引擎 文档:欢迎使用 Dify | Dify GITHUB:langgenius/dify: Dify is an open-source LLM app development platform. Difys intuitive interface combines AI workflow, RAG pipeline, agent capabilities, model management, ob…...
解锁 DeepSeek 模型高效部署密码:蓝耘平台全解析
💖亲爱的朋友们,热烈欢迎来到 青云交的博客!能与诸位在此相逢,我倍感荣幸。在这飞速更迭的时代,我们都渴望一方心灵净土,而 我的博客 正是这样温暖的所在。这里为你呈上趣味与实用兼具的知识,也…...
7.PPT:“中国梦”学习实践活动【20】
目录 NO1234 NO5678 NO9\10\11 NO1234 考生文件夹下创建一个名为“PPT.pptx”的新演示文稿Word素材文档的文字:复制/挪动→“PPT.pptx”的新演示文稿(蓝色、黑色、红色) 视图→幻灯片母版→重命名:“中国梦母版1”→背景样…...
Linux系统-centos防火墙firewalld详解
Linux系统-centos7.6 防火墙firewalld详解 1 firewalld了解 CentOS 7.6默认的防火墙管理工具是firewalld,它取代了之前的iptables防火墙。firewalld属于典型的包过滤防火墙或称之为网络层防火墙,与iptables一样,都是用来管理防火墙的工具&a…...
零基础都可以本地部署Deepseek R1
文章目录 一、硬件配置需求二、详细部署步骤1. 安装 Ollama 工具2. 部署 DeepSeek-R1 模型3. API使用4. 配置图形化交互界面(可选)5. 使用与注意事项 一、硬件配置需求 不同版本的 DeepSeek-R1 模型参数量不同,对硬件资源的要求也不尽相同。…...
通过Ollama本地部署DeepSeek R1以及简单使用的教程(超详细)
本文介绍了在Windows环境下,通过Ollama来本地部署DeepSeek R1。该问包含了Ollama的下载、安装、安装目录迁移、大模型存储位置修改、下载DeepSeek以及通过Web UI来对话等相关内容。 1、🥇下载Ollama 首先我们到Ollama官网去下载安装包,此处我…...
css实现长尾箭头(夹角小于45度的)
1. 长尾夹角小于45度的箭头 代码 //h5<div class"singleArrow"></div>//css .singleArrow {width: 150px;height: 1px;position: relative;background-color: #15ff00;/* transform: rotate(-40deg); */ /* 旋转角度 */}.singleArrow::after{ // 成品-有…...
封装descriptions组件,描述,灵活
效果 1、组件1,dade-descriptions.vue <template><table><tbody><slot></slot></tbody> </table> </template><script> </script><style scoped>table {width: 100%;border-collapse: coll…...
OC-Block
关于OC中的block作为属性时,为什么要要用copy修饰 property (nonatomic, copy) void (^completionBlock)(void);很多文章包括AI都会给出类似结论 Block 默认分配在栈上,如果没有 copy,当方法退出后,Block 会被销毁。使用 copy 修…...
关于知识蒸馏的概念原理以及常见方法
1. 概念与原理 知识蒸馏的基本定义 知识蒸馏(Knowledge Distillation) 是一种将模型压缩与迁移学习结合的技术:它利用预先训练好的大模型(通常参数量大、精度高、计算开销大)指导一个更轻量(参数量小、推理速度快)的学生模型进行训练,从而在保持模型精度的同时显著减少…...
C++轻量级桌面GUI库FLTK
C轻量级桌面GUI库FLTK Screenshots - Fast Light Toolkit (FLTK) 这里写个备忘录,可以参考一下....
C++20导出模块及使用
1.模块声明 .ixx文件为导入模块文件 math_operations.ixx export module math_operations;//模块导出 //导出命名空间 export namespace math_ {//导出命名空间中函数int add(int a, int b);int sub(int a, int b);int mul(int a, int b);int div(int a, int b); } .cppm文件…...
PID 算法简介(C语言)
一、简介: PID是比例、积分、微分三个环节的组合,用来进行反馈控制。每个部分都有对应的系数,也就是Kp、Ki、Kd。PID 算法实现这三个部分的计算,然后综合起来得到控制输出。 二、PID控制器结构体: PID控制器结构体:包含PID参数(Kp, Ki, Kd);存储积分项和上一次误差;…...
脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)
一、数据处理与分析实战 (一)实时滤波与参数调整 基础滤波操作 60Hz 工频滤波:勾选界面右侧 “60Hz” 复选框,可有效抑制电网干扰(适用于北美地区,欧洲用户可调整为 50Hz)。 平滑处理&…...
Java如何权衡是使用无序的数组还是有序的数组
在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...
FastAPI 教程:从入门到实践
FastAPI 是一个现代、快速(高性能)的 Web 框架,用于构建 API,支持 Python 3.6。它基于标准 Python 类型提示,易于学习且功能强大。以下是一个完整的 FastAPI 入门教程,涵盖从环境搭建到创建并运行一个简单的…...
Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!
一、引言 在数据驱动的背景下,知识图谱凭借其高效的信息组织能力,正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合,探讨知识图谱开发的实现细节,帮助读者掌握该技术栈在实际项目中的落地方法。 …...
全志A40i android7.1 调试信息打印串口由uart0改为uart3
一,概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本:2014.07; Kernel版本:Linux-3.10; 二,Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01),并让boo…...
如何理解 IP 数据报中的 TTL?
目录 前言理解 前言 面试灵魂一问:说说对 IP 数据报中 TTL 的理解?我们都知道,IP 数据报由首部和数据两部分组成,首部又分为两部分:固定部分和可变部分,共占 20 字节,而即将讨论的 TTL 就位于首…...
浪潮交换机配置track检测实现高速公路收费网络主备切换NQA
浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求,本次涉及的主要是收费汇聚交换机的配置,浪潮网络设备在高速项目很少,通…...
【Linux】自动化构建-Make/Makefile
前言 上文我们讲到了Linux中的编译器gcc/g 【Linux】编译器gcc/g及其库的详细介绍-CSDN博客 本来我们将一个对于编译来说很重要的工具:make/makfile 1.背景 在一个工程中源文件不计其数,其按类型、功能、模块分别放在若干个目录中,mak…...
SpringAI实战:ChatModel智能对话全解
一、引言:Spring AI 与 Chat Model 的核心价值 🚀 在 Java 生态中集成大模型能力,Spring AI 提供了高效的解决方案 🤖。其中 Chat Model 作为核心交互组件,通过标准化接口简化了与大语言模型(LLM࿰…...
华为OD最新机试真题-数组组成的最小数字-OD统一考试(B卷)
题目描述 给定一个整型数组,请从该数组中选择3个元素 组成最小数字并输出 (如果数组长度小于3,则选择数组中所有元素来组成最小数字)。 输入描述 行用半角逗号分割的字符串记录的整型数组,0<数组长度<= 100,0<整数的取值范围<= 10000。 输出描述 由3个元素组成…...
