C++实现DFS、BFS、Kruskal算法和Prim算法、拓扑排序、Dijkstra算法
背景:
实现要求:
- 根据图的抽象数据类型的定义,请采用邻接矩阵来存储图1,采用邻接表来存储图2,并完成如下操作:

- 对图1无向图进行深度优先遍历和广度优先遍历。
- 对图1无向图采用Kruskal算法和Prim算法得出最小生成树。
- 对图2有向图进行拓扑排序,并输出。
实现无向图类和有向图类,编写测试main()函数,实例化无向图类对象和有向图类对象。
2.编制校园导航程序。依托青岛理工大学校园,给出主要建筑的名称信息及有路线连通的建筑之间的距离,抽象为图的数据结构,编程给出从任一建筑出发去校园另一建筑位置的最优路线及其距离。
实现要求:
构建带权有向图,并在附录中给出;
(2)实现Dijkstra算法或者Floyd算法;
(3)程序运行时,给出校园所有建筑物供用户选择,选出起点和终点,给出最短路径及距离。
实现提示:
(3)测试数据(或者自定义其他输入,或者使用文件)。
过程效果:
1-DFS和BFS(对图1无向图进行深度优先遍历和广度优先遍历):
2-对图1无向图采用Kruskal算法和Prim算法得出最小生成树:



3-对图2有向图进行拓扑排序,并输出:

- 编写测试main函数
- ⽤户界⾯能够进⾏交互;
4-:实现Dijkstra算法:


主要代码:
int main() {Graph g;g.addEdge(0, 1, 6);g.addEdge(0, 2, 1);g.addEdge(0, 3, 5);g.addEdge(1, 2, 5);g.addEdge(2, 3, 5);g.addEdge(1, 4, 3);g.addEdge(2, 4, 6); g.addEdge(2, 5, 4);g.addEdge(3, 5, 2);g.addEdge(4, 5, 6);/*g.addEdge(0, 1, 4);g.addEdge(0, 2, 3);g.addEdge(1, 3, 2);g.addEdge(1, 4, 7);g.addEdge(2, 4, 1);g.addEdge(3, 4, 5);g.addEdge(3, 5, 6);*/cout << "DFS搜索,从节点0[代表图中1]开始 ";g.DFS(0);cout << endl;cout << "BFS搜索,从节点0[代表图中1]开始";g.BFS(0);cout << endl;return 0;
}
int main() {Graph g(7);g.addEdge(0, 2);g.addEdge(2, 3);g.addEdge(1, 3);g.addEdge(1, 6);g.addEdge(1, 4);g.addEdge(3, 5);g.addEdge(6, 5);g.addEdge(3, 4);g.topologicalSort();return 0;
}
相关文章:
C++实现DFS、BFS、Kruskal算法和Prim算法、拓扑排序、Dijkstra算法
背景: 实现要求: 根据图的抽象数据类型的定义,请采用邻接矩阵来存储图1,采用邻接表来存储图2,并完成如下操作:对图1无向图进行深度优先遍历和广度优先遍历。对图1无向图采用Kruskal算法和Prim算法得出最小…...
Spring 依赖注入的三种方式优缺点
小王学习录 前言属性注入1. 属性注入的优点2. 属性注入的缺点 Setter注入Setter注入的优点Setter注入的缺点 构造方法注入1. 构造方法的优点 总结补充Aurowired注解和Resource注解的区别 前言 在前面的文章中介绍了基于注解的方式将Bean存储到Spring中, 接下来介绍如何基于注解…...
代理模式介绍(静态代理、jdk动态代理、cglib代理)
一、静态代理 (一)定义 1、定义 为其他对象提供一种代理以控制对这个对象的访问; 2、涉及到的角色 (1)抽象主题角色:真实主题和代理主题的共同接口,便于在使用真实主题的地方都可以使用代理…...
设计模式基础——工厂模式剖析(2/2)
目录 一、工厂模式 1.1 工厂模式的定义 1.2 工厂模式的设计意图 1.3 工厂模式主要解决的问题 1.4 工厂模式的缺点 1.5 实际的应用案例 1. 数据库连接池 2. 图形用户界面(GUI)组件 3. 文件操作 二、各种工厂模式的变形 1.1 简单工厂模式&#…...
spark3.x 读取hudi报错
报错信息如下: Exception in thread "main" org.apache.hudi.exception.HoodieUpsertException: Failed to upsert for commit time 20231201203145254 at org.apache.hudi.table.action.commit.BaseWriteHelper.write(BaseWriteHelper.java:64) at org.apa…...
微信小程序中block和View组件的使用区别
block和View组件都是用于布局的组件: 1. Block组件: Block组件是一个无实际显示效果的组件,它主要用于包裹一组组件,并提供了类似于div的作用。使用Block组件可以将一组组件进行分组,便于样式的管理和控制。Block组件不会在页面…...
代码混淆技术探究与工具选择
代码混淆技术探究与工具选择 引言 在软件开发中,保护程序代码的安全性是至关重要的一环。代码混淆(Obfuscated code)作为一种常见的保护手段,通过将代码转换成难以理解的形式来提升应用被逆向破解的难度。本文将介绍代码混淆的概…...
selenium 解决 id定位、class定位中,属性值带空格的解决办法
一、前置说明 selenium遇到下面这种元素: <th id"demo id" class"value1 value2 value3 ">1、虽然id一般不会有空格,但是前端错误的这种写法(如下图),会造成使用id定位不到元素,如: find…...
gma 空间绘图实战(1):绘制多个子图,连接并展示局部放大区域
安装 gma:pip install gma 本文基于:gma 2.0.3,Python 3.10 本文用到的矢量数据为:CTAmap 1.12。来源于 https://www.shengshixian.com/ 。(感谢锐多宝) 绘图目标 参考代码 import matplotlib.pyplot as p…...
Unity中C#使用协程控制Shader材质变化
文章目录 前言一、协程是什么二、在Unity中使用协程1、我们在 Start 中测试一下协程的执行顺序2、我们实现一个点击按钮实现角色受击效果 三、协程中的动画过渡1、首先,在协程内实现中毒并且消散的效果2、在 OnGUI 内,给一个新按钮使用刚刚定义的协程 四…...
WordPress禁止显示指定类别的文章
使用wordpress禁止输出指定类别的文章可以给get_posts()函数传个数组参数,如下: <div class"widget" id"diary1"> <h3>随机呈现</h3> <ul> <?php $argsarray( numberposts>16, category>-9,-12, …...
C#里面的泛型(T),泛型类,泛型方法,泛型接口等简单解释
https://blog.csdn.net/dap769815768/article/details/81946506 只是比较简单的解释,在实际使用中,如果遇到需要深入研究的场景,再翻阅相关资料深入研究下。 一、泛型T 这个T在实际使用中很常见,比如List<T>。其实我们还…...
C语言——指针(五)
📝前言: 上篇文章C语言——指针(四)更加深入的介绍了不同类型指针的特点,这篇文章主要想记录一下函数与指针的结合运用以及const和assert关于指针的用法: 1,函数与指针 2,const 3&am…...
文章解读与仿真程序复现思路——中国电机工程学报EI\CSCD\北大核心《考虑气电联合需求响应的气电综合能源配网系统协调优化运行》
这个标题涉及到一个涉及气体(天然气)和电力的综合能源配网系统,并且强调了考虑气电联合需求响应的协调优化运行。让我们逐步解读: 气电综合能源配网系统: 这指的是一个结合了气体(通常是天然气)…...
PostgreSQL 主键和唯一键的区别
主键和唯一键的区别 主键(Primary Key): 主键是用于唯一标识表中的每一条记录的键。主键必须是唯一的,不允许为空。一个表只能有一个主键。主键可以由一个或多个字段组成。主键的值在整个表中必须是唯一的,用于确保数据…...
删除表格中的所有绘图
Ctrl G 调出定位的对话框再点击定位条件 按Delete键,删除...
Linux卸载Nginx
1、停止Nginx软件 #/usr/local/nginx/sbin/nginx-sstop 或者kill进程 #ps -ef|grep nginx #kill -9 PID 2、查找根下所有名子包含nginx的文件 #sudofind/-namenginx* 3、执行命令删掉nignx安装的相关文件 # rm -rf /usr/local/sbin/nginx # rm -rf /usr/local/nginx # r…...
Qt之QGraphicsView —— 笔记1:绘制简单图元(附完整源码)
效果 相关类介绍 QGraphicsView类提供了一个小部件,用于显示QGraphicsScene的内容。QGraphicsView在可滚动视口中可视化。QGraphicsView将滚动其视口,以确保该点在视图中居中。 QGraphicsScene类 提供了一个用于管理大量二维图形项的场景。请注意,QGraphicsScene没有自己的视…...
SpringIoC原理
我是南城余!阿里云开发者平台专家博士证书获得者! 欢迎关注我的博客!一同成长! 一名从事运维开发的worker,记录分享学习。 专注于AI,运维开发,windows Linux 系统领域的分享! 本…...
如何对售后服务的全流程进行精细化的管理?
——“如何对售后服务的全流程进行精细化的管理?” ——“售后又是一个十分复杂的过程,仅靠手工或者电子表格记录这些内容,肯定是低效率、易出错的。最好的办法是借助合适的管理工具进行精细化的过程管理。” 假设你购买了一台新的家用电器…...
IDEA运行Tomcat出现乱码问题解决汇总
最近正值期末周,有很多同学在写期末Java web作业时,运行tomcat出现乱码问题,经过多次解决与研究,我做了如下整理: 原因: IDEA本身编码与tomcat的编码与Windows编码不同导致,Windows 系统控制台…...
51c自动驾驶~合集58
我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留,CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制(CCA-Attention),…...
【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器
——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的一体化测试平台,覆盖应用全生命周期测试需求,主要提供五大核心能力: 测试类型检测目标关键指标功能体验基…...
【磁盘】每天掌握一个Linux命令 - iostat
目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat(I/O Statistics)是Linux系统下用于监视系统输入输出设备和CPU使…...
页面渲染流程与性能优化
页面渲染流程与性能优化详解(完整版) 一、现代浏览器渲染流程(详细说明) 1. 构建DOM树 浏览器接收到HTML文档后,会逐步解析并构建DOM(Document Object Model)树。具体过程如下: (…...
JDK 17 新特性
#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持,不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的ÿ…...
多种风格导航菜单 HTML 实现(附源码)
下面我将为您展示 6 种不同风格的导航菜单实现,每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...
大学生职业发展与就业创业指导教学评价
这里是引用 作为软工2203/2204班的学生,我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要,而您认真负责的教学态度,让课程的每一部分都充满了实用价值。 尤其让我…...
【生成模型】视频生成论文调研
工作清单 上游应用方向:控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...
安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖
在Vuzix M400 AR智能眼镜的助力下,卢森堡罗伯特舒曼医院(the Robert Schuman Hospitals, HRS)凭借在无菌制剂生产流程中引入增强现实技术(AR)创新项目,荣获了2024年6月7日由卢森堡医院药剂师协会࿰…...
