当前位置: 首页 > 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;那么这两个模块就得有交互&#…...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)

0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述&#xff0c;后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作&#xff0c;其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

基于服务器使用 apt 安装、配置 Nginx

&#x1f9fe; 一、查看可安装的 Nginx 版本 首先&#xff0c;你可以运行以下命令查看可用版本&#xff1a; apt-cache madison nginx-core输出示例&#xff1a; nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...

页面渲染流程与性能优化

页面渲染流程与性能优化详解&#xff08;完整版&#xff09; 一、现代浏览器渲染流程&#xff08;详细说明&#xff09; 1. 构建DOM树 浏览器接收到HTML文档后&#xff0c;会逐步解析并构建DOM&#xff08;Document Object Model&#xff09;树。具体过程如下&#xff1a; (…...

企业如何增强终端安全?

在数字化转型加速的今天&#xff0c;企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机&#xff0c;到工厂里的物联网设备、智能传感器&#xff0c;这些终端构成了企业与外部世界连接的 “神经末梢”。然而&#xff0c;随着远程办公的常态化和设备接入的爆炸式…...

LangChain知识库管理后端接口:数据库操作详解—— 构建本地知识库系统的基础《二》

这段 Python 代码是一个完整的 知识库数据库操作模块&#xff0c;用于对本地知识库系统中的知识库进行增删改查&#xff08;CRUD&#xff09;操作。它基于 SQLAlchemy ORM 框架 和一个自定义的装饰器 with_session 实现数据库会话管理。 &#x1f4d8; 一、整体功能概述 该模块…...

MFC 抛体运动模拟:常见问题解决与界面美化

在 MFC 中开发抛体运动模拟程序时,我们常遇到 轨迹残留、无效刷新、视觉单调、物理逻辑瑕疵 等问题。本文将针对这些痛点,详细解析原因并提供解决方案,同时兼顾界面美化,让模拟效果更专业、更高效。 问题一:历史轨迹与小球残影残留 现象 小球运动后,历史位置的 “残影”…...

SpringAI实战:ChatModel智能对话全解

一、引言&#xff1a;Spring AI 与 Chat Model 的核心价值 &#x1f680; 在 Java 生态中集成大模型能力&#xff0c;Spring AI 提供了高效的解决方案 &#x1f916;。其中 Chat Model 作为核心交互组件&#xff0c;通过标准化接口简化了与大语言模型&#xff08;LLM&#xff0…...

【UE5 C++】通过文件对话框获取选择文件的路径

目录 效果 步骤 源码 效果 步骤 1. 在“xxx.Build.cs”中添加需要使用的模块 &#xff0c;这里主要使用“DesktopPlatform”模块 2. 添加后闭UE编辑器&#xff0c;右键点击 .uproject 文件&#xff0c;选择 "Generate Visual Studio project files"&#xff0c;重…...

实战设计模式之模板方法模式

概述 模板方法模式定义了一个操作中的算法骨架&#xff0c;并将某些步骤延迟到子类中实现。模板方法使得子类可以在不改变算法结构的前提下&#xff0c;重新定义算法中的某些步骤。简单来说&#xff0c;就是在一个方法中定义了要执行的步骤顺序或算法框架&#xff0c;但允许子类…...

针对药品仓库的效期管理问题,如何利用WMS系统“破局”

案例&#xff1a; 某医药分销企业&#xff0c;主要经营各类药品的批发与零售。由于药品的特殊性&#xff0c;效期管理至关重要&#xff0c;但该企业一直面临效期问题的困扰。在未使用WMS系统之前&#xff0c;其药品入库、存储、出库等环节的效期管理主要依赖人工记录与检查。库…...