当前位置: 首页 > news >正文

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

文章目录 数据结构实验十二 图的遍历及应用一、【实验目的】二、【实验内容】三、实验源代码&#x1f37b; CPP&#x1f37b; C 数据结构实验十二 图的遍历及应用 一、【实验目的】 1、 理解图的存储结构与基本操作&#xff1b; 2、熟悉图的深度度优先遍历和广度优先遍历算法…...

什么是 Proxy?

目录 Proxy 的作用 1. 流量过滤 2. 记录日志 3. 加快访问速度 4. 隐藏 IP 地址 Proxy 的分类 1. 按协议分类 - HTTP 代理&#xff1a;只支持 HTTP 协议的代理服务器&#xff0c;它可以缓存 HTTP 请求和响应并过滤 HTTP 流量。 - FTP 代理&#xff1a;只支持 FTP 协议的…...

Vue系列:Vue Element UI中,使用按钮实现视频的播放、停止、停止后继续播放、播放完成后重新播放功能

最近在工作中有个政务大屏用到了视频播放&#xff1b; 技术栈是Vue2、Element UI&#xff1b; 要实现的功能是&#xff1a;使用按钮实现视频的播放、停止、停止后继续播放、播放完成后重新播放功能 具体可以按照以下步骤进行操作&#xff1a; 引入插件&#xff1a; 在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 使用详解

最近这俩天正好有时间给自己做一下减法&#xff0c;忘记是去年还是今年&#xff0c;在升级 AndroidStudio 后使用 Logcat查看日志的方式也发生了一些变化&#xff0c;虽然一直在使用&#xff0c;但每当看到之前还未关闭 Logcat 命令行工具额昂也&#xff0c;就感觉可能还存在知…...

Webpack ECMAScript 模块

文章目录 前言标题一导出导入将模块标记为 ESM 后言 前言 hello world欢迎来到前端的新世界 &#x1f61c;当前文章系列专栏&#xff1a;webpack &#x1f431;‍&#x1f453;博主在前端领域还有很多知识和技术需要掌握&#xff0c;正在不断努力填补技术短板。(如果出现错误&a…...

knife4j集合化postman

knife4j集合化postman 01 knife4j的介绍 基于 JavaMVC的集成框架swagger的进一步强化&#xff0c;在原有通过注释就能生成文档的前身swagger-bootstrap-ui之上&#xff0c;增加了postman的测试功能&#xff0c;优化了文档的UI界面&#xff0c;在测试api接口的方面有了极大的进…...

MongoDB的原子性和多文档事务处理

原子性和事务处理是数据库操作的核心&#xff0c;保证了数据的准确性。依据数据库原子性&#xff0c;数据库和使用数据库的人员定义事务处理的方式。本文依据Mongodb的官方文档&#xff0c;整理Mongodb数据库的原子性和事务处理方法。 Mongodb的原子操作 Mongodb中&#xff0c…...

代理模式 1、静态代理 2、动态代理 jdk自带动态代理 3、Cglib代理

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

ELK+filebeat+kafka

无需创建logstash的端口&#xff0c;直接创建topic 远程收集mysql和httpd的日志 &#xff08;一&#xff09;安装nginx和mysql服务 1、打开mysql的日志功能 2、创建日志&#xff08;创库、创表、添加数据&#xff09; &#xff08;1&#xff09;mysql服务器上安装http system…...

LLVM学习笔记(63)

4.4.3.3.2.3. 向量操作数类型的处理 下面开始处理向量类型。在默认情形下这些操作都会拆分为更小的操作或者调用库。 X86TargetLowering::X86TargetLowering&#xff08;续&#xff09; 667 // Some FP actions are always expanded for vector types. 668 for…...

【python+requests】接口自动化测试

这两天一直在找直接用python做接口自动化的方法&#xff0c;在网上也搜了一些博客参考&#xff0c;今天自己动手试了一下。 一、整体结构 上图是项目的目录结构&#xff0c;下面主要介绍下每个目录的作用。 Common:公共方法:主要放置公共的操作的类&#xff0c;比如数据库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中&#xff0c;线程是一种轻量级的子进程&#xff0c;它是程序中的最小执行单元。Java的多线程编程可以通过两种方式实现&#xff1a;继承Threa…...

寿险公司通过开源治理保障数字创新,安全打通高质量服务新通道

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

SpringBoot中的部分注解

1.SpringBoot/spring SpringBootApplication: 包含Configuration、EnableAutoConfiguration、ComponentScan通常用在主类上&#xff1b; Repository: 用于标注数据访问组件&#xff0c;即DAO组件&#xff1b; Service: 用于标注业务层组件&#xff1b; RestController: 用…...

蓝桥杯-02-蓝桥杯C/C++组考点与14届真题

文章目录 蓝桥杯C/C组考点与14届真题参考资源C/C组考点1. 组别2. 竞赛赛程3. 竞赛形式4. 参赛选手机器环境5. 试题形式5.1. 结果填空题5.2. 编程大题 6. 试题考查范围7. 答案提交8. 评分9. 样题样题 1&#xff1a;矩形切割&#xff08;结果填空题&#xff09;样题 2&#xff1a…...

计算机杂谈系列精讲100篇-【计算机应用】关于TensorFlow和PyTorch的一些看法

目录 前言 知识储备 PyTorch使用高频代码 导入包和版本查询​​​​​​...

Uni-App知识点

文章目录 一、事件总线二、什么是事件总线三、触发事件1、监听事件2、只监听一次3、移除监听4、触发事件注意事项5、代码示例6、注意事项 一、事件总线 除了父子组件传参之外&#xff0c;兄弟组件之间共享信息也是我们经常会遇到的。如果遇到这类问题&#xff0c;我们现在可以…...

Postman如何使用(四):接口测试

一.接口 1.程序内部接口&#xff1a;方法与方法之间&#xff0c;模块与模块之间的交互&#xff0c;程序内部抛出的接口&#xff0c;比如bbs系统&#xff0c;有登录模块&#xff0c;发帖模块等等&#xff0c;那你要发帖就必须先登录&#xff0c;那么这两个模块就得有交互&#…...

应用升级/灾备测试时使用guarantee 闪回点迅速回退

1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间&#xff0c; 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点&#xff0c;不需要开启数据库闪回。…...

CTF show Web 红包题第六弹

提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框&#xff0c;很难让人不联想到SQL注入&#xff0c;但提示都说了不是SQL注入&#xff0c;所以就不往这方面想了 ​ 先查看一下网页源码&#xff0c;发现一段JavaScript代码&#xff0c;有一个关键类ctfs…...

AI Agent与Agentic AI:原理、应用、挑战与未来展望

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

为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?

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

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

【项目实战】通过多模态+LangGraph实现PPT生成助手

PPT自动生成系统 基于LangGraph的PPT自动生成系统&#xff0c;可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析&#xff1a;自动解析Markdown文档结构PPT模板分析&#xff1a;分析PPT模板的布局和风格智能布局决策&#xff1a;匹配内容与合适的PPT布局自动…...

江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命

在华东塑料包装行业面临限塑令深度调整的背景下&#xff0c;江苏艾立泰以一场跨国资源接力的创新实践&#xff0c;重新定义了绿色供应链的边界。 跨国回收网络&#xff1a;废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点&#xff0c;将海外废弃包装箱通过标准…...

在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上实现鼠标、触摸等事件捕获的解决方案

这个问题我看其他博主也写了&#xff0c;要么要会员、要么写的乱七八糟。这里我整理一下&#xff0c;把问题说清楚并且给出代码&#xff0c;拿去用就行&#xff0c;照着葫芦画瓢。 问题 在继承QWebEngineView后&#xff0c;重写mousePressEvent或event函数无法捕获鼠标按下事…...

动态 Web 开发技术入门篇

一、HTTP 协议核心 1.1 HTTP 基础 协议全称 &#xff1a;HyperText Transfer Protocol&#xff08;超文本传输协议&#xff09; 默认端口 &#xff1a;HTTP 使用 80 端口&#xff0c;HTTPS 使用 443 端口。 请求方法 &#xff1a; GET &#xff1a;用于获取资源&#xff0c;…...