GDPU 数据结构 天码行空12
文章目录
- 数据结构实验十二 图的遍历及应用
- 一、【实验目的】
- 二、【实验内容】
- 三、实验源代码
- 🍻 CPP
- 🍻 C
数据结构实验十二 图的遍历及应用
一、【实验目的】
1、 理解图的存储结构与基本操作;
2、熟悉图的深度度优先遍历和广度优先遍历算法
3、掌握图的单源最短路径算法
二、【实验内容】
1.根据下图邻接矩阵,编程实现该图的深度与广度优先遍历算法,输出遍历序列。
2.单源节点最短路径问题
问题描述:求从有向图的某一结点出发到其余各结点的最短路径。
基本要求:
(1)有向图采用邻接矩阵表示。
(2)单源节点最短路径问题采用Dijkstra算法。
(3)输出有向图中从源结点T到其余各结点的最短路径和最短路径值。
三、实验源代码
🍻 CPP
#include<iostream>
#include<queue>
#include<cstring>
#include<vector>
using namespace std;const int N = 6;
const int M = N*N;
const int INF = 0x3f3f3f3f;
const int 无边 = -1;int g[N][N]; //grap数组记录邻接矩阵【-1 表示不可达】
bool vs[N];//visted数组记录结点是否已经被访问过void add(int a, int b, int c)
{// 邻接矩阵加边g[a][b] = c;
}void init()
{for(int i = 0; i < N; i++)for(int j = 0; j < N; j++)g[i][j] = 无边;//初始化为不可达状态【-1】// A B C D E F// 0 1 2 3 4 5// 加边add(1, 0, 2);add(2, 1, 15);add(0, 2, 5);add(0, 3, 30);add(2, 5, 7);add(1, 4, 8);add(4, 3, 4);add(5, 3, 10);add(5, 4, 18);
}void print()
{// 输出邻接矩阵cout << "输出邻接矩阵:" << endl;cout << " A B C D E F" << endl;char c = 'A';for (int i = 0; i < N; i++){cout << c++ << " ";for (int j = 0; j < N; j++)printf("%-2d ",g[i][j]);
// cout << g[i][j] << " ";cout << endl;}
}//深度优先遍历
// u 是当前访问的点
void dfs(int u)
{cout << char(u+'A') << " " ;vs[u] = true;//标记以访问for(int i = 0; i < N; i++)//访问当前结点可达的结点(有边){int e = g[u][i];if(vs[i])//已访问过continue;if(e == 无边)//无边continue;dfs(i); }
}//广度优先遍历
// u 是当前访问的点
void bfs(int u)
{memset(vs,false,sizeof(vs));//初始化访问表为 未访问状态vs[u] = true;queue<int> q;//队列(先进先出)q.push(u);while(!q.empty()){int t = q.front();//取队头cout << char(t+'A') << " " ;q.pop();//队头出列for(int i = 0; i < N; i++)//访问当前结点可达的结点(有边){int e = g[t][i];if(vs[i])//已访问过continue;if(e == 无边)//无边continue;q.push(i);vs[i] = true;}}
}int dist[N];//距离数组
int pre[N];//pre[i] 记录最短路径上,点 i 的前一个结点
//输出路径
void printRoute(int x)
{cout << "\nA到" << char(x + 'A') << "的最短路径长度为: " << dist[x] << endl;cout << "最短路径途径节点:";vector<int> v;while(x != -1){v.push_back(x);x = pre[x];}for(int i = v.size()-1; i >= 0; i--)cout << char(v[i]+'A') << " " ;cout << endl;
}//单源最短路 Dijkstra算法
void dijkstra(int u)//u表示起点
{cout << "\n\nDijkstra算法求最短路径"<<endl;memset(vs,false,sizeof(vs));//初始化访问表为 未访问状态memset(dist,0x3f,sizeof(dist));//初始化距离表为 无穷大memset(pre,-1,sizeof(pre));//初始化所有结点的前一个节点为 -1dist[u] = 0;for(int i = 0; i < N; i++){int t = -1;for(int j = 0; j < N; j++)//找n次{if(!vs[j] && (t == -1 || dist[j] < dist[t]))//循环找当前最小距离的点t = j;}printRoute(t);vs[t] = true;for(int j = 0; j < N; j++)//用当前最小距离的点尝试去更新其他点的距离{if(g[t][j] == 无边)continue;if(dist[j] > dist[t] + g[t][j]){dist[j] = dist[t] + g[t][j];pre[j] = t;//记录前驱节点}} }
}
int main()
{init(); // 初始化图print(); // 输出邻接矩阵和邻接表cout<< "\n深度优先遍历:";memset(vs,false,sizeof(vs));//初始化访问表为 未访问状态dfs(0);cout<< "\n广度优先遍历:";bfs(0);dijkstra(0);return 0;
}
🍻 C
#include<stdio.h>
#include<string.h>
#include<limits.h>
#include<stdbool.h>#define N 6
#define M (N * N)
#define INF 0x3f3f3f3f
#define NO_EDGE -1int g[N][N]; // graph数组记录邻接矩阵【-1 表示不可达】
bool vs[N]; // visited数组记录结点是否已经被访问过void add(int a, int b, int c)
{// 邻接矩阵加边g[a][b] = c;
}void init()
{for (int i = 0; i < N; i++){for (int j = 0; j < N; j++){g[i][j] = NO_EDGE; // 初始化为不可达状态【-1】}}// A B C D E F// 0 1 2 3 4 5// 加边add(1, 0, 2);add(2, 1, 15);add(0, 2, 5);add(0, 3, 30);add(2, 5, 7);add(1, 4, 8);add(4, 3, 4);add(5, 3, 10);add(5, 4, 18);
}void print()
{// 输出邻接矩阵printf("输出邻接矩阵:\n");printf(" A B C D E F\n");char c = 'A';for (int i = 0; i < N; i++){printf("%c ", c++);for (int j = 0; j < N; j++){if (g[i][j] == NO_EDGE){printf(" - ");}else{printf("%-2d ", g[i][j]);}}printf("\n");}
}//深度优先遍历
// u 是当前访问的点
void dfs(int u)
{printf("%c ", u + 'A');vs[u] = true; // 标记已访问for (int i = 0; i < N; i++) // 访问当前结点可达的结点(有边){int e = g[u][i];if (vs[i]) // 已访问过continue;if (e == NO_EDGE) // 无边continue;dfs(i);}
}//广度优先遍历
// u 是当前访问的点
void bfs(int u)
{memset(vs, false, sizeof(vs)); // 初始化访问表为未访问状态vs[u] = true;printf("%c ", u + 'A');int queue[N];int front = 0, rear = 0;queue[rear++] = u;while (front != rear){int t = queue[front++];for (int i = 0; i < N; i++) //访问当前结点可达的结点(有边){int e = g[t][i];if (vs[i]) //已访问过continue;if (e == NO_EDGE) //无边continue;printf("%c ", i + 'A');queue[rear++] = i;vs[i] = true;}}
}int dist[N]; //距离数组
int pre[N]; //pre[i] 记录最短路径上,点 i 的前一个结点//输出路径
void printRoute(int x)
{printf("\nA到%c的最短路径长度为:%d\n", x + 'A', dist[x]);printf("最短路径途径节点:");int v[N], cnt = 0;while (x != -1){v[cnt++] = x;x = pre[x];}for (int i = cnt - 1; i >= 0; i--){printf("%c ", v[i] + 'A');}printf("\n");
}//单源最短路 Dijkstra算法
void dijkstra(int u) //u表示起点
{printf("\n\nDijkstra算法求最短路径\n");memset(vs, false, sizeof(vs)); //初始化访问表为未访问状态memset(dist, INF, sizeof(dist)); //初始化距离表为无穷大memset(pre, -1, sizeof(pre)); //初始化所有结点的前一个节点为-1dist[u] = 0;for (int i = 0; i < N; i++){int t = -1;for (int j = 0; j < N; j++) //找n次{if (!vs[j] && (t == -1 || dist[j] < dist[t])) //循环找当前最小距离的点t = j;}printRoute(t);vs[t] = true;for (int j = 0; j < N; j++) //用当前最小距离的点尝试去更新其他点的距离{if (g[t][j] == NO_EDGE)continue;if (dist[j] > dist[t] + g[t][j]){dist[j] = dist[t] + g[t][j];pre[j] = t; //记录前驱节点}}}
}int main()
{init(); // 初始化图print(); // 输出邻接矩阵和邻接表printf("\n深度优先遍历:");memset(vs, false, sizeof(vs)); //初始化访问表为未访问状态dfs(0);printf("\n广度优先遍历:");bfs(0);dijkstra(0);return 0;
}
相关文章:

GDPU 数据结构 天码行空12
文章目录 数据结构实验十二 图的遍历及应用一、【实验目的】二、【实验内容】三、实验源代码🍻 CPP🍻 C 数据结构实验十二 图的遍历及应用 一、【实验目的】 1、 理解图的存储结构与基本操作; 2、熟悉图的深度度优先遍历和广度优先遍历算法…...
什么是 Proxy?
目录 Proxy 的作用 1. 流量过滤 2. 记录日志 3. 加快访问速度 4. 隐藏 IP 地址 Proxy 的分类 1. 按协议分类 - HTTP 代理:只支持 HTTP 协议的代理服务器,它可以缓存 HTTP 请求和响应并过滤 HTTP 流量。 - FTP 代理:只支持 FTP 协议的…...
Vue系列:Vue Element UI中,使用按钮实现视频的播放、停止、停止后继续播放、播放完成后重新播放功能
最近在工作中有个政务大屏用到了视频播放; 技术栈是Vue2、Element UI; 要实现的功能是:使用按钮实现视频的播放、停止、停止后继续播放、播放完成后重新播放功能 具体可以按照以下步骤进行操作: 引入插件: 在Vue组件…...

.Net 8 Blazor下 Auto交互渲染模式试用
一、环境 C:\Users\zhuji>dotnet --version 8.0.100C:\Users\zhuji>dotnet --list-sdks 5.0.403 [C:\Program Files\dotnet\sdk] 6.0.404 [C:\Program Files\dotnet\sdk] 8.0.100 [C:\Program Files\dotnet\sdk] Microsoft Visual Studio Enterprise 2022 (64 位) - Cu…...

AndroidStudio - 新版本 Logcat 使用详解
最近这俩天正好有时间给自己做一下减法,忘记是去年还是今年,在升级 AndroidStudio 后使用 Logcat查看日志的方式也发生了一些变化,虽然一直在使用,但每当看到之前还未关闭 Logcat 命令行工具额昂也,就感觉可能还存在知…...
Webpack ECMAScript 模块
文章目录 前言标题一导出导入将模块标记为 ESM 后言 前言 hello world欢迎来到前端的新世界 😜当前文章系列专栏:webpack 🐱👓博主在前端领域还有很多知识和技术需要掌握,正在不断努力填补技术短板。(如果出现错误&a…...

knife4j集合化postman
knife4j集合化postman 01 knife4j的介绍 基于 JavaMVC的集成框架swagger的进一步强化,在原有通过注释就能生成文档的前身swagger-bootstrap-ui之上,增加了postman的测试功能,优化了文档的UI界面,在测试api接口的方面有了极大的进…...
MongoDB的原子性和多文档事务处理
原子性和事务处理是数据库操作的核心,保证了数据的准确性。依据数据库原子性,数据库和使用数据库的人员定义事务处理的方式。本文依据Mongodb的官方文档,整理Mongodb数据库的原子性和事务处理方法。 Mongodb的原子操作 Mongodb中,…...

代理模式 1、静态代理 2、动态代理 jdk自带动态代理 3、Cglib代理
文章目录 代理模式1、静态代理2、动态代理jdk自带动态代理 3、Cglib代理 来和大家聊聊代理模式 代理模式 代理模式:即通过代理对象访问目标对象,实现目标对象的方法。这样做的好处是:可以在目标对象实现的基础上,增强额外的功能操…...

ELK+filebeat+kafka
无需创建logstash的端口,直接创建topic 远程收集mysql和httpd的日志 (一)安装nginx和mysql服务 1、打开mysql的日志功能 2、创建日志(创库、创表、添加数据) (1)mysql服务器上安装http system…...
LLVM学习笔记(63)
4.4.3.3.2.3. 向量操作数类型的处理 下面开始处理向量类型。在默认情形下这些操作都会拆分为更小的操作或者调用库。 X86TargetLowering::X86TargetLowering(续) 667 // Some FP actions are always expanded for vector types. 668 for…...

【python+requests】接口自动化测试
这两天一直在找直接用python做接口自动化的方法,在网上也搜了一些博客参考,今天自己动手试了一下。 一、整体结构 上图是项目的目录结构,下面主要介绍下每个目录的作用。 Common:公共方法:主要放置公共的操作的类,比如数据库sql…...

plt创建指定色系
1、创建不连续色系 import matplotlib.pyplot as plt from matplotlib.colors import ListedColormap# 定义颜色的RGB值 colors [(0.2, 0.4, 0.6), # 蓝色(0.8, 0.1, 0.3), # 红色(0.5, 0.7, 0.2),(0.3,0.5,0.8)] # 绿色# 创建色系 cmap ListedColormap(colors)# 绘制…...

Java多线程-第20章
Java多线程-第20章 1.创建线程 Java是一种支持多线程编程的编程语言。多线程是指在同一程序中同时执行多个独立任务的能力。在Java中,线程是一种轻量级的子进程,它是程序中的最小执行单元。Java的多线程编程可以通过两种方式实现:继承Threa…...

寿险公司通过开源治理保障数字创新,安全打通高质量服务新通道
某寿险公司致力于为消费者提供人性化的产品和服务,在中国保险市场中始终保持前列。该寿险公司以挖掘和满足客户需求为出发点,从产品开发、渠道销售、运营流程和售后服务等各环节,借助数字化工具,不断地努力探索并提升服务品质。 精…...

SpringBoot中的部分注解
1.SpringBoot/spring SpringBootApplication: 包含Configuration、EnableAutoConfiguration、ComponentScan通常用在主类上; Repository: 用于标注数据访问组件,即DAO组件; Service: 用于标注业务层组件; RestController: 用…...
蓝桥杯-02-蓝桥杯C/C++组考点与14届真题
文章目录 蓝桥杯C/C组考点与14届真题参考资源C/C组考点1. 组别2. 竞赛赛程3. 竞赛形式4. 参赛选手机器环境5. 试题形式5.1. 结果填空题5.2. 编程大题 6. 试题考查范围7. 答案提交8. 评分9. 样题样题 1:矩形切割(结果填空题)样题 2:…...
计算机杂谈系列精讲100篇-【计算机应用】关于TensorFlow和PyTorch的一些看法
目录 前言 知识储备 PyTorch使用高频代码 导入包和版本查询...
Uni-App知识点
文章目录 一、事件总线二、什么是事件总线三、触发事件1、监听事件2、只监听一次3、移除监听4、触发事件注意事项5、代码示例6、注意事项 一、事件总线 除了父子组件传参之外,兄弟组件之间共享信息也是我们经常会遇到的。如果遇到这类问题,我们现在可以…...

Postman如何使用(四):接口测试
一.接口 1.程序内部接口:方法与方法之间,模块与模块之间的交互,程序内部抛出的接口,比如bbs系统,有登录模块,发帖模块等等,那你要发帖就必须先登录,那么这两个模块就得有交互&#…...
应用升级/灾备测试时使用guarantee 闪回点迅速回退
1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间, 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点,不需要开启数据库闪回。…...

CTF show Web 红包题第六弹
提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框,很难让人不联想到SQL注入,但提示都说了不是SQL注入,所以就不往这方面想了 先查看一下网页源码,发现一段JavaScript代码,有一个关键类ctfs…...

AI Agent与Agentic AI:原理、应用、挑战与未来展望
文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例:使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例:使用OpenAI GPT-3进…...

为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?
在建筑行业,项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升,传统的管理模式已经难以满足现代工程的需求。过去,许多企业依赖手工记录、口头沟通和分散的信息管理,导致效率低下、成本失控、风险频发。例如&#…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)
服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

【项目实战】通过多模态+LangGraph实现PPT生成助手
PPT自动生成系统 基于LangGraph的PPT自动生成系统,可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析:自动解析Markdown文档结构PPT模板分析:分析PPT模板的布局和风格智能布局决策:匹配内容与合适的PPT布局自动…...

江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命
在华东塑料包装行业面临限塑令深度调整的背景下,江苏艾立泰以一场跨国资源接力的创新实践,重新定义了绿色供应链的边界。 跨国回收网络:废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点,将海外废弃包装箱通过标准…...
在Ubuntu24上采用Wine打开SourceInsight
1. 安装wine sudo apt install wine 2. 安装32位库支持,SourceInsight是32位程序 sudo dpkg --add-architecture i386 sudo apt update sudo apt install wine32:i386 3. 验证安装 wine --version 4. 安装必要的字体和库(解决显示问题) sudo apt install fonts-wqy…...
在QWebEngineView上实现鼠标、触摸等事件捕获的解决方案
这个问题我看其他博主也写了,要么要会员、要么写的乱七八糟。这里我整理一下,把问题说清楚并且给出代码,拿去用就行,照着葫芦画瓢。 问题 在继承QWebEngineView后,重写mousePressEvent或event函数无法捕获鼠标按下事…...
动态 Web 开发技术入门篇
一、HTTP 协议核心 1.1 HTTP 基础 协议全称 :HyperText Transfer Protocol(超文本传输协议) 默认端口 :HTTP 使用 80 端口,HTTPS 使用 443 端口。 请求方法 : GET :用于获取资源,…...