BFS算法篇——打开智慧之门,BFS算法在拓扑排序中的诗意探索(上)
文章目录
- 引言
- 一、拓扑排序的背景
- 二、BFS算法解决拓扑排序
- 三、应用场景
- 四、代码实现
- 五、代码解释
- 六、总结

引言
在这浩瀚如海的算法世界中,有一扇门,开启后通向了有序的领域。它便是拓扑排序,这个问题的解决方法犹如一场深刻的哲学思考:在一个由节点和边构成的有向图中,如何安排节点的顺序,以满足每一条边的方向约束?这是一个在计算机科学中至关重要的问题,广泛应用于任务调度、依赖关系分析等领域。
在求解拓扑排序的问题时,广度优先搜索(BFS)
算法带着它那独特的力量,悄然走入我们的视野。BFS不仅仅是图的遍历工具,它还能帮助我们揭开拓扑排序的神秘面纱。
在这篇报告中,我们将探讨如何用BFS算法实现拓扑排序,揭示其中的算法思想与实现步骤,同时通过C语言代码实现这一过程。
一、拓扑排序的背景
在计算机科学中,拓扑排序
是针对有向无环图(DAG, Directed Acyclic Graph)的一种排序方法。拓扑排序要求图中的每一条有向边 (u, v) 都满足节点 u 在排序中出现在节点 v 之前。
拓扑排序的问题在于,它要求我们找出一个节点的顺序,以确保每个节点的依赖关系被正确处理。该问题广泛应用于任务调度、课程安排、项目管理等场景中。
二、BFS算法解决拓扑排序
BFS算法通常与图的层次遍历相关联,而在拓扑排序问题中,BFS能够通过一种特殊的方式——Kahn算法来解决.Kahn
算法是一种基于BFS的拓扑排序算法,核心思想如下:
- 初始化:找出所有入度为0的节点。入度为0意味着这些节点没有依赖项,可以作为排序的起始节点。
- 遍历:将所有入度为0的节点加入队列,每次从队列中取出一个节点,输出该节点,并减少它指向的所有节点的入度。
- 更新:当某个节点的入度减为0时,将该节点加入队列。重复此过程,直到所有节点被处理。
BFS的队列操作确保了我们始终从最早可以处理的节点开始,逐步构建出正确的拓扑顺序。
三、应用场景
拓扑排序在多个领域中都有重要应用,尤其是当任务之间有依赖关系时,拓扑排序能够帮助我们安排任务的执行顺序。例如:
- 任务调度:在多任务系统中,如何按顺序执行任务,以确保每个任务的前置任务已完成。
- 课程安排:在大学课程安排中,如何安排课程的先后顺序,确保前置课程在后续课程之前完成。
- 项目管理:在项目中,如何安排不同子任务的顺序,以便最终顺利完成项目。
四、代码实现
下面是一个使用C语言实现BFS算法求解拓扑排序的代码示例:
#include <stdio.h>
#include <stdlib.h>#define MAX 100// 队列结构体定义
typedef struct {int items[MAX];int front, rear;
} Queue;// 队列初始化
void initQueue(Queue* q) {q->front = q->rear = 0;
}// 入队操作
void enqueue(Queue* q, int item) {q->items[q->rear++] = item;
}// 出队操作
int dequeue(Queue* q) {return q->items[q->front++];
}// 判断队列是否为空
int isEmpty(Queue* q) {return q->front == q->rear;
}// 拓扑排序的BFS实现
void topologicalSortBFS(int graph[MAX][MAX], int n) {int inDegree[MAX] = {0}; // 存储每个节点的入度Queue q;initQueue(&q);// 计算所有节点的入度for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (graph[i][j] == 1) {inDegree[j]++;}}}// 将所有入度为0的节点入队for (int i = 0; i < n; i++) {if (inDegree[i] == 0) {enqueue(&q, i);}}int count = 0; // 记录已输出的节点数while (!isEmpty(&q)) {int current = dequeue(&q);printf("%d ", current); // 输出节点// 遍历当前节点的邻接节点,减少它们的入度for (int i = 0; i < n; i++) {if (graph[current][i] == 1) {inDegree[i]--;// 如果入度变为0,将其入队if (inDegree[i] == 0) {enqueue(&q, i);}}}count++;}// 如果输出的节点数与图中的节点数不同,说明图中存在环,无法进行拓扑排序if (count != n) {printf("\n图中存在环,无法进行拓扑排序。\n");} else {printf("\n拓扑排序完成。\n");}
}int main() {int graph[MAX][MAX] = {{0, 1, 0, 0, 0},{0, 0, 1, 0, 0},{0, 0, 0, 1, 0},{0, 0, 0, 0, 1},{0, 0, 0, 0, 0}};int n = 5; // 节点数printf("拓扑排序结果:\n");topologicalSortBFS(graph, n);return 0;
}
五、代码解释
-
图的表示
:我们使用一个二维数组 graph[MAX][MAX] 来表示图的邻接矩阵,其中 graph[i][j] 为 1 表示存在从节点 i 到节点 j 的有向边,0 表示没有边。 -
入度数组
:inDegree[MAX] 用来存储每个节点的入度,表示指向该节点的边的数量。 -
队列操作
:我们用队列来实现BFS,确保节点按照拓扑顺序逐一处理。通过 enqueue 和 dequeue 操作,我们可以依次访问入度为 0 的节点,并逐步更新其他节点的入度。 -
拓扑排序过程
:首先计算每个节点的入度,并将所有入度为 0 的节点入队。然后,通过逐一访问队列中的节点,输出节点并更新它的邻接节点的入度。如果某个邻接节点的入度减为 0,就将该节点加入队列。 -
环检测
:如果在处理过程中,我们没有输出所有节点,那么图中必然存在环,无法完成拓扑排序。
六、总结
BFS在拓扑排序中的应用如同一位心思缜密的指挥家,按照特定的规则,逐步安排每一个节点的顺序。在这个过程中,算法不仅顺利完成了节点的排列,也避免了其中可能出现的循环依赖,确保了排序的正确性。
拓扑排序让我们看到了一个有序的世界,而BFS算法如同那把钥匙,为我们打开了通向有序图形的智慧之门。通过这扇门,我们能够在复杂的依赖关系中找到秩序,将混乱转化为优雅,最终走向光明的终点。
本篇关于BFS算法解决拓扑排序的介绍就暂告段落啦,希望能对大家的学习产生帮助,欢迎各位佬前来支持斧正!!!
相关文章:
BFS算法篇——打开智慧之门,BFS算法在拓扑排序中的诗意探索(上)
文章目录 引言一、拓扑排序的背景二、BFS算法解决拓扑排序三、应用场景四、代码实现五、代码解释六、总结 引言 在这浩瀚如海的算法世界中,有一扇门,开启后通向了有序的领域。它便是拓扑排序,这个问题的解决方法犹如一场深刻的哲学思考&#…...
【Nova UI】十六、打造组件库之滚动条组件(中):探秘滑块的计算逻辑
序言 在上篇文章中,我们完成了滚动条组件开发的前期准备工作,包括理论推导、布局规划和基础设置。现在,我们将把这些准备转化为实际代码,开启滚动条组件的具体开发之旅🌟。我们会详细阐述如何实现各项功能,…...
题海拾贝:P1833 樱花
Hello大家好!很高兴我们又见面啦!给生活添点passion,开始今天的编程之路! 我的博客:<但凡. 我的专栏:《编程之路》、《数据结构与算法之美》、《题海拾贝》、《C修炼之路》 欢迎点赞,关注&am…...
集成钉钉消息推送功能
1. 概述 本文档详细描述了在若依框架基础上集成钉钉消息推送功能的开发步骤。该功能允许系统向指定钉钉用户发送文本和富文本消息通知。 2. 环境准备 2.1 钉钉开发者账号配置 登录钉钉开发者平台:https://open.dingtalk.com/创建/选择企业内部应用获取以下关键信…...
texlive 与 Texmaker 安装
一、安装 Texmaker 1、下载Texmaker 链接地址: Texmaker (free cross-platform latex editor) 点击 FREE DOWNLOAD ,点击 Texmaker_6.0.1_Win_x64.msi ,下载即可。 2、安装Texmaker 双击如下文件 若出现如下,点击更多信息 点击仍要运行 …...
Milvus(21):过滤搜索、范围搜索、分组搜索
1 过滤搜索 ANN 搜索能找到与指定向量嵌入最相似的向量嵌入。但是,搜索结果不一定总是正确的。您可以在搜索请求中包含过滤条件,这样 Milvus 就会在进行 ANN 搜索前进行元数据过滤,将搜索范围从整个 Collections 缩小到只搜索符合指定过滤条件…...
AD PCB布局时常用的操作命令
1. 框选 往右下方框选:选中矩形接触到的对象(选中整体才会被选中) 往左上方框选:选中矩形接触到的对象(选中局部,也是选中整体) 线选:快捷键S,弹出界面: …...
[免费]微信小程序医院预约挂号管理系统(uni-app+SpringBoot后端+Vue管理端)【论文+源码+SQL脚本】
大家好,我是java1234_小锋老师,看到一个不错的微信小程序医院预约挂号管理系统(uni-appSpringBoot后端Vue管理端),分享下哈。 项目视频演示 【免费】微信小程序医院预约挂号管理系统(uni-appSpringBoot后端Vue管理端) Java毕业设计_哔哩哔哩…...
分析Docker容器Jvm 堆栈GC信息
# 打印jvm启动参数 docker exec -ti <容器名> jcmd 1 VM.flags-XX:CICompilerCount3 -XX:InitialHeapSize1073741824 -XX:MaxHeapSize2147483648 -XX:MaxMetaspaceSize157286400 -XX:MaxNewSize715653120 -XX:MinHeapDeltaBytes524288 -XX:NewSize357564416 -XX:OldSize7…...
Java——集合基础
一、集合与数组的特点对比 1.集合类的特点:提供一种存储空间可变的存储模型,存储的数据容量可以发生改变 2.集合和数组的区别 共同点:都是存储数据的容器不同点:数组的容量是固定的,集合的容量是可变的 3.如果存储…...
spark MySQL数据库配置
Spark 连接 MySQL 数据库的配置 要让 Spark 与 MySQL 数据库实现连接,需要进行以下配置步骤。下面为你提供详细的操作指南和示例代码: 1. 添加 MySQL JDBC 驱动依赖 你得把 MySQL 的 JDBC 驱动添加到 Spark 的类路径中。可以通过以下两种方式来完成&a…...
http断点续传
🛑 默认的 http.server(Python 的 SimpleHTTPRequestHandler)在某些版本和实现中并不可靠地支持 HTTP Range 请求(即断点续传)。 尤其在 Python 3.7~3.10 之间的某些版本中,这种支持是不完整或不可预测的。…...
# YOLOv3:基于 PyTorch 的目标检测模型实现
YOLOv3:基于 PyTorch 的目标检测模型实现 引言 YOLOv3(You Only Look Once)是一种流行的单阶段目标检测算法,它能够直接在输入图像上预测边界框和类别概率。YOLOv3 的优势在于其高效性和准确性,使其在实时目标检测任…...
Mac修改hosts文件方法
Mac修改hosts文件方法 在 macOS 上修改 hosts 文件需要管理员权限 步骤 1:打开终端 通过 Spotlight 搜索(Command 空格)输入 Terminal,回车打开。或进入 应用程序 > 实用工具 > 终端。 步骤 2:备份 hosts 文件…...
构建你的第一个简单AI助手 - 入门实践
在当今AI迅速发展的时代,构建自己的AI助手不再是高不可攀的技术壁垒。即使对于刚接触AI开发的程序员,也可以利用现代大语言模型(LLM)API构建功能丰富的AI助手。本文将带您完成一个简单但实用的AI助手构建过程,帮助您在日常工作中提高效率。 …...
Qt在统信UOS及银河麒麟Kylin系统中进行软件开发的环境配置,打包发布和注意事项
前述 之前由于项目的产品需要,必须将原本Windows上的产品移植到信创环境,也就是现在的主流国产操作系统统信UOS及银河麒麟Kylin。 先大概讲下信创系统: 信创系统就像是中国自己打造的 “数字基建”,目的是让咱们国家的信息技术不…...
一个完整的项目示例:taro开发微信小程序
前一周完成了一个项目,体测成绩转换的工具,没做记录,。这次计划开发一个地图应用小程序,记录一下。方便给使用的人。 一、申请微信小程序,填写相应的信息,取得开发者ID。这个要给腾讯地图使用的。 二、申…...
二次封装 el-dialog 组件:打造更灵活的对话框解决方案
文章目录 引言为什么需要二次封装?封装思路代码实现1. 基础封装组件 (Dialog.vue)2. Vue中引入使用示例 封装后的优势进阶优化建议 总结 引言 在 Vue 项目中,Element UI 的 el-dialog 是一个非常实用的对话框组件。但在实际开发中,我们经常会…...
3.2 一点一世界
第一步:引入背景与动机 “一点一世界”这个概念来源于泰勒公式的思想,即通过一个点及其导数信息来近似描述整个函数的行为。这种方法在数学分析中非常有用,因为它允许我们将复杂的函数简化为多项式形式,从而更容易进行计算和理解…...
力扣第156场双周赛
1. 找到频率最高的元音和辅音 给你一个由小写英文字母(a 到 z)组成的字符串 s。你的任务是找出出现频率 最高 的元音(a、e、i、o、u 中的一个)和出现频率最高的辅音(除元音以外的所有字母),并返…...
学习日志05 java
1 java里面的类型转换怎么做?int转double为例 在 Java 里,把int转换为double有自动类型转换和强制类型转换两种方式。下面为你详细介绍: 自动类型转换(隐式转换) 由于double的取值范围比int大,Java 能够…...
4.7/Q1,GBD数据库最新文章解读
文章题目:Burden of non-COVID-19 lower respiratory infections in China (1990-2021): a global burden of disease study analysis DOI:10.1186/s12931-025-03197-7 中文标题:中国非 COVID-19 下呼吸道感染负担(1990-2021 年&a…...
do while
先进再查 import java.util.Scanner;public class Hello {public static void main(String[] args) {Scanner in new Scanner(System.in);int number in.nextInt();int count 0;do{number number / 10;count count 1;} while( number > 0 );System.out.println(count…...
MySQL 主从复制与读写分离
一、MySQL 主从复制 (0)概述 MySQL 主从复制是一种数据同步机制,允许数据从一个主数据库(Master)复制到一个或多个从数据库(Slave)。其主要用途包括: 数据冗余与灾备:通…...
CSS3 基础知识、原理及与CSS的区别
CSS3 基础知识、原理及与CSS的区别 CSS3 基础知识 CSS3 是 Cascading Style Sheets 的第3个版本,是CSS技术的升级版本,于1999年开始制订,2001年5月23日W3C完成了CSS3的工作草案。 CSS3 主要模块 选择器:更强大的元素选择方式盒…...
第十七章:Llama Factory 深度剖析:易用性背后的微调框架设计
章节引导:在模型定制的实践中,Llama Factory (github.com/hiyouga/LLaMA-Factory) 以其惊人的易用性和对多种开源大模型、多种参数高效微调方法(PEFT)的广泛支持,迅速成为开源社区的热门选择。你可能已经熟练掌握了如何…...
SpringSecurity当中的CSRF防范详解
CSRF防范 什么是CSER 以下是基于 CSRF 攻击过程的 顺序图 及详细解释,结合多个技术文档中的攻击流程: CSRF 攻击顺序图 #mermaid-svg-FqfMBQr8DsGRoY2C {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#m…...
CSRF防范歪招
不保存到Cookie里呗 如果每次请求都强制通过请求头携带Token,并且不将Token存储在Cookie中,这种设计可以有效防御CSRF攻击。以下是具体原因和关键实现要点: 1. 防御原理 CSRF攻击的本质是攻击者伪造用户的请求,利用浏览器自动携…...
MyBatis与MyBatis-Plus深度分析
MyBatis与MyBatis-Plus深度分析 一、MyBatis原理与基础 1. MyBatis核心原理 MyBatis是一个半自动ORM框架,主要原理包括: SQL与代码分离:通过XML或注解配置SQL语句动态SQL:提供if、choose、foreach等标签实现动态SQL结果集映射…...
STM32 变量加载到flash的过程中
在STM32中,BIN文件内需要加载到RAM的数据由链接脚本(Linker Script)和启动代码(Startup Code)共同决定,具体机制如下: 一、BIN文件内容结构 STM32的BIN文件包含三类数据: Co…...
TCP核心机制
1. TCP五大核心机制 1.1. 顺序问题(稳重不乱) 背景:网络传输中数据包可能因路径不同或网络波动导致乱序到达,需保证接收方能按正确顺序处理数据。 原理: 序列号(Sequence Number)࿱…...
6.3对象序列化
在 Java 中,ObjectInputStream 和 ObjectOutputStream 是用于实现对象序列化(Serialization)和反序列化(Deserialization)的核心类。通过这两个类,可以将对象转换为字节流进行存储或传输,并在需…...
Flutter小白入门指南
Flutter小白入门指南 🚀 轻松构建漂亮的跨平台应用 📑 目录 一、Flutter是什么? 为什么选择Flutter?Flutter工作原理 二、环境搭建与命令行 安装Flutter SDK常用Flutter命令创建第一个项目 三、Flutter基础语法 变量与类型函数条…...
Python -将MP4文件转为GIF图片
给大家提供一个工具代码,使用Python,将MP4格式的视频文件,转换为GIF图片 首先先安装必要的包: pip install imageio pip install imageio[ffmpeg] 工具代码: import imageio# 视频文件路径 video_path r""…...
51c嵌入式~电路~合集27
我自己的原文哦~ 一、7805应用电路 简介 如上图,7805 集成稳压电路。 7805是串联式三端稳压器,三个端口分别是电压输入端(IN),地线(GND),稳压输出(OUT)…...
数据结构—(链表,栈,队列,树)
本文章写的比较乱,属于是缝合怪,很多细节没处理,显得粗糙,日后完善,今天赶时间了。 1. 红黑树的修复篇章 2. 红黑树的代码理解(部分写道注释之中了) 3. 队列与栈的代码 4. 重要是理解物理逻辑&a…...
GitHub 趋势日报 (2025年05月12日)
本日报由 TrendForge 系统生成 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日整体趋势 Top 10 排名项目名称项目描述今日获星总星数语言1harry0703/MoneyPrinterTurbo利用ai大模型,一键生成高清短视频使用…...
ebook2audiobook开源程序使用动态 AI 模型和语音克隆将电子书转换为带有章节和元数据的有声读物。支持 1,107+ 种语言
一、软件介绍 文末提供程序和源码下载 ebook2audiobook开源程序使用动态 AI 模型和语音克隆将电子书转换为带有章节和元数据的有声读物。支持 1,107 种语言。从电子书到带有章节和元数据的有声读物的 CPU/GPU 转换器,使用 XTTSv2、Bark、Vits、Fairseq、YourTTS …...
《算法导论(第4版)》阅读笔记:p39-p48
《算法导论(第4版)》学习第 13 天,p39-p48 总结,总计 10 页。 一、技术总结 1. recurrence/recurrence equation 书里面 recurrence(递归式) 和 recurrence equation(递归方程) 指的是同一个东西。 二、英语总结(生词:2) 1. squint (1)…...
c语言第一个小游戏:贪吃蛇小游戏07
贪吃蛇吃饭喽 所谓贪吃蛇的食物,也就是创建一个和蛇身一样的结构体,只是这个结构体不是链表,也是将这个结构体设置hang和lie坐标,放进gamepic进行扫描,扫到了就也是做操作将 ## 打出来 #include <curses.h> #i…...
(七)深度学习---神经网络原理与实现
分类问题回归问题聚类问题各种复杂问题决策树√线性回归√K-means√神经网络√逻辑回归√岭回归密度聚类深度学习√集成学习√Lasso回归谱聚类条件随机场贝叶斯层次聚类隐马尔可夫模型支持向量机高斯混合聚类LDA主题模型 一.神经网络原理概述 二.神经网络的训练方法 三.基于Ker…...
VSCode中Node.js 使用教程
一、visual studio code下载与安装 二、修改vscode主题颜色 三、汉化 菜单view-->Command Palette...,输入Configure Display Language。 重启之后如下: 四、安装node.js Node.js 是一个基于Chrome V8引擎的JavaScript运行环境,使用了事件驱动、非阻…...
web 自动化之 KDT 关键字驱动详解
一、什么是关键字驱动? 1、什么是关键字驱动?(以关键字函数驱动测试) 关键字驱动又叫动作字驱动,把项目业务封装成关键字函数,再基于关键字函数实现自动化测试 2、关键字驱动测试原理 关键字驱动测试是一…...
web 自动化之 yaml 数据/日志/截图
文章目录 一、yaml 数据获取二、日志获取三、截图 一、yaml 数据获取 需要安装 PyYAML 库 import yaml import os from TestPOM.common import dir_config as Dirdef read_yaml(key,file_name"test_datas.yaml"):file_path os.path.join(Dir.testcases_dir, file_…...
基于javaweb的SpringBoot酒店管理系统设计与实现(源码+文档+部署讲解)
技术范围:SpringBoot、Vue、SSM、HLMT、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、小程序、安卓app、大数据、物联网、机器学习等设计与开发。 主要内容:免费功能设计、开题报告、任务书、中期检查PPT、系统功能实现、代码编写、论文编写和辅导、论文…...
数学复习笔记 6
前言 复习一下行列式的一些基本的题。感觉网课有点没跟上了。今天花点时间跟上网课的进度。要紧跟进度,然后剩下的时间再去复习前面的内容。多复习,提升自己的解题能力。 行列式和矩阵 三年级,我现在是三年级下册。。。马上就要结束大学的…...
JS Map使用方法
JS Map使用方法 Map 是 ES6 引入的一种新的数据结构,它类似于对象(Object),但提供了更强大的键值对存储功能。 文章目录 JS Map使用方法基本特性基本用法创建 Map常用方法遍历方法 与 Object 的区别实际应用示例示例1:…...
大模型分布式光伏功率预测实现详解
一、引言 随着全球能源结构向可再生能源转型,光伏发电作为清洁能源的重要组成部分,其装机容量持续快速增长。然而,光伏发电具有显著的间歇性和波动性特点,给电力系统的稳定运行带来了巨大挑战。准确的光伏功率预测对于电网调度、电力市场交易和电站运营管理至关重要。近年…...
武汉大学无人机视角下的多目标指代理解新基准!RefDrone:无人机场景指代表达理解数据集
作者:Zhichao Sun, Yepeng Liu, Huachao Zhu, Yuliang Gu, Yuda Zou, Zelong Liu, Gui-Song Xia, Bo Du, Yongchao Xu 单位:武汉大学计算机学院 论文标题:RefDrone: A Challenging Benchmark for Drone Scene Referring Expression Compreh…...
【LLM模型】如何构建自己的MCP Server?
什么是 MCP? Model Context Protocol (MCP) 是一种协议,它允许大型语言模型(LLMs)访问自定义的工具和服务。Trae 中的智能体作为 MCP 客户端可以选择向 MCP Server 发起请求,以使用它们提供的工具。你可以自行添加 MC…...