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 系统领域的分享! 本…...
如何对售后服务的全流程进行精细化的管理?
——“如何对售后服务的全流程进行精细化的管理?” ——“售后又是一个十分复杂的过程,仅靠手工或者电子表格记录这些内容,肯定是低效率、易出错的。最好的办法是借助合适的管理工具进行精细化的过程管理。” 假设你购买了一台新的家用电器…...
利用最小二乘法找圆心和半径
#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...
HTML 语义化
目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案: 语义化标签: <header>:页头<nav>:导航<main>:主要内容<article>&#x…...
视频字幕质量评估的大规模细粒度基准
大家读完觉得有帮助记得关注和点赞!!! 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用,因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型(VLMs)在字幕生成方面…...
如何理解 IP 数据报中的 TTL?
目录 前言理解 前言 面试灵魂一问:说说对 IP 数据报中 TTL 的理解?我们都知道,IP 数据报由首部和数据两部分组成,首部又分为两部分:固定部分和可变部分,共占 20 字节,而即将讨论的 TTL 就位于首…...
蓝桥杯3498 01串的熵
问题描述 对于一个长度为 23333333的 01 串, 如果其信息熵为 11625907.5798, 且 0 出现次数比 1 少, 那么这个 01 串中 0 出现了多少次? #include<iostream> #include<cmath> using namespace std;int n 23333333;int main() {//枚举 0 出现的次数//因…...
均衡后的SNRSINR
本文主要摘自参考文献中的前两篇,相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程,其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt 根发送天线, n r n_r nr 根接收天线的 MIMO 系…...
GruntJS-前端自动化任务运行器从入门到实战
Grunt 完全指南:从入门到实战 一、Grunt 是什么? Grunt是一个基于 Node.js 的前端自动化任务运行器,主要用于自动化执行项目开发中重复性高的任务,例如文件压缩、代码编译、语法检查、单元测试、文件合并等。通过配置简洁的任务…...
GitFlow 工作模式(详解)
今天再学项目的过程中遇到使用gitflow模式管理代码,因此进行学习并且发布关于gitflow的一些思考 Git与GitFlow模式 我们在写代码的时候通常会进行网上保存,无论是github还是gittee,都是一种基于git去保存代码的形式,这样保存代码…...
MySQL 部分重点知识篇
一、数据库对象 1. 主键 定义 :主键是用于唯一标识表中每一行记录的字段或字段组合。它具有唯一性和非空性特点。 作用 :确保数据的完整性,便于数据的查询和管理。 示例 :在学生信息表中,学号可以作为主键ÿ…...
淘宝扭蛋机小程序系统开发:打造互动性强的购物平台
淘宝扭蛋机小程序系统的开发,旨在打造一个互动性强的购物平台,让用户在购物的同时,能够享受到更多的乐趣和惊喜。 淘宝扭蛋机小程序系统拥有丰富的互动功能。用户可以通过虚拟摇杆操作扭蛋机,实现旋转、抽拉等动作,增…...
