【C++数据结构——图】图的邻接矩阵和邻接表的存储（头歌实践教学平台习题）【合集】
目录😋
任务描述
相关知识
1. 带权有向图
2. 图的邻接矩阵
3. 图的邻接表
测试说明
通关代码
测试结果
任务描述
本关任务：编写一个程序实现图的邻接矩阵和邻接表的存储。
相关知识
为了完成本关任务，你需要掌握：
- 带权有向图
- 图的邻接矩阵，
- 图的邻接表。
1. 带权有向图
针对有向图的邻接矩阵和邻接表的存储，如下列图形：
2. 图的邻接矩阵
若 G 为带权有向图，其邻接矩阵 A 中的元素 Aij 遵循以下规则进行赋值：
- 当 i≠j，并且存在从顶点 i 指向顶点 j 的有向边，即 <i, j>∈E (G) 时，此时 Aij 的值等于该有向边的权值 wij；
- 当 i = j 时，Aij 的取值为 0，这表示顶点到自身的权值为 0；
- 而在其他情况下，也就是不存在从顶点 i 指向顶点 j 的有向边时，Aij 的值设定为无穷大（通常用特定的极大数值来表示，例如在程序实现中可以采用类似 INT_MAX 这样能表示极大值的常量来表示无穷大的概念）。
示例代码如下：
if (g.edges[i][j]!=INF)printf("%d ",g.edges[i][j]);elseprintf("%s ","∞");（INF表示无穷大，表示整数：32767)
3. 图的邻接表
邻接表结点由三个域组成：
- adjvex指示与顶点vi邻接的点在图中的位置,
- nextarc指示下一条边或弧的结点,
- info存储与边或弧的权值。
表头结点由两个域组成：
- data存储顶点vi的名称或其他信息,
- firstarc指向链表中第一个结点。
示例代码如下：
for (int i=0;i<G->n;i++){p=G->adjlist[i].firstarc;printf("%3d: ",i);while (p!=NULL){printf("%3d[%d]→",p->adjvex,p->weight);p=p->nextarc;}printf("∧\n");}
测试说明
平台会对你编写的代码进行测试：
测试输入：（ 输入图的顶点数和边数，再输入图的邻接矩阵。）
6 10 0 5 32767 7 32767 32767 32767 0 4 32767 32767 32767 8 32767 0 32767 32767 9 32767 32767 5 0 32767 6 32767 32767 32767 5 0 32767 3 32767 32767 32767 1 0
预期输出：（Prim算法求解结果）
边(0,5)权为:3边(5,4)权为:1边(0,1)权为:5 边(1,2)权为:4边(4,3)权为:5
开始你的任务吧，祝你成功！
通关代码
#include <algorithm>
#include <iostream>
#include <limits>
#include <vector>
using namespace std;
const int MAX_VERTICES = 6; // 最大顶点数
const int INF = 32767; // 表示无穷大// 邻接矩阵表示的图
struct GraphMatrix {int n; // 顶点数vector<vector<int>> edges; // 邻接矩阵
};// 邻接表的边节点
struct ArcNode {int adjvex; // 邻接点在图中的位置int weight; // 边的权重ArcNode *nextarc; // 指向下一条边
};// 邻接表
struct VNode {int data; // 顶点信息ArcNode *firstarc; // 指向第一条边
};struct GraphList {int n; // 顶点数vector<VNode> adjlist; // 邻接表
};// 输入邻接矩阵并构建图
void inputGraphMatrix(GraphMatrix &g) {cin >> g.n; // 读入顶点数int e; // 边数cin >> e; // 读入边数g.edges.resize(g.n, vector<int>(g.n, INF));for (int i = 0; i < g.n; ++i) {g.edges[i][i] = 0; // 对角线元素为0}// 读入邻接矩阵for (int i = 0; i < g.n; ++i) {for (int j = 0; j < g.n; ++j) {cin >> g.edges[i][j];}}
}// 输出邻接矩阵
void printGraphMatrix(const GraphMatrix &g) {cout << "(1)图G的邻接矩阵:" << endl;for (int i = 0; i < g.n; ++i) {for (int j = 0; j < g.n; ++j) {if (g.edges[i][j] == INF) {cout << "∞ ";} else {cout << g.edges[i][j] << " ";}}cout << endl;}
}// 构建邻接表
void buildGraphList(const GraphMatrix &gm, GraphList &gl) {gl.n = gm.n;gl.adjlist.resize(gl.n);for (int i = 0; i < gm.n; ++i) {gl.adjlist[i].data = i; // 存储顶点gl.adjlist[i].firstarc = nullptr; // 初始化第一条边}// 从邻接矩阵构建邻接表for (int i = 0; i < gm.n; ++i) {for (int j = 0; j < gm.n; ++j) {if (gm.edges[i][j] != INF && gm.edges[i][j] != 0) {ArcNode *arc = new ArcNode(); // 动态分配新边arc->adjvex = j; // 指向邻接点arc->weight = gm.edges[i][j]; // 边的权重arc->nextarc = nullptr; // 初始化下一条边为nullptr// 将新节点插入已排序的链表中if (gl.adjlist[i].firstarc == nullptr ||gl.adjlist[i].firstarc->adjvex > j) {arc->nextarc = gl.adjlist[i].firstarc; // 插入到链表头gl.adjlist[i].firstarc = arc;} else {ArcNode *p = gl.adjlist[i].firstarc;while (p->nextarc != nullptr && p->nextarc->adjvex < j) {p = p->nextarc; // 寻找插入位置}arc->nextarc = p->nextarc; // 插入p->nextarc = arc;}}}}
}// 输出邻接表
void printGraphList(const GraphList &gl) {cout << "(2)图G的邻接表:" << endl;for (int i = 0; i < gl.n; ++i) {cout << " " << i << ": ";ArcNode *p = gl.adjlist[i].firstarc;while (p != nullptr) {cout << " " << p->adjvex << "[" << p->weight << "]→";p = p->nextarc;}cout << "∧" << endl;}
}int main() {GraphMatrix gm;inputGraphMatrix(gm);printGraphMatrix(gm);GraphList gl;buildGraphList(gm, gl);printGraphList(gl);return 0;
}
测试结果
相关文章：
【C++数据结构——图】图的邻接矩阵和邻接表的存储（头歌实践教学平台习题）【合集】
目录😋 任务描述 相关知识 1. 带权有向图 2. 图的邻接矩阵 3. 图的邻接表 测试说明 通关代码 测试结果 任务描述 本关任务：编写一个程序实现图的邻接矩阵和邻接表的存储。 相关知识 为了完成本关任务，你需要掌握： 带权有向图…...
基于单片机的直流稳压电源的设计（论文+源码）
1.系统方案设计 在本次直流稳压电源的设计中，其关键指标如下： 系统输入电压220V交流系统输出直流0到12V可调，步进可以达到0.1V电流最大输出可以到2A具有短路保护功能可以通过液晶或者数码管等显示设备显示当前输出电压 2. 电路图...
Golang开发-案例整理汇总
前言 CSDN的文章缺少一个索引所有文章分类的地方，所以手动创建这么一个文章汇总的地方，方便查找。Golang开发经典案例汇总 GoangWeb开发 GolangWeb开发- net/http模块 GolangWeb开发-好用的HTTP客户端httplib(beego) GolangWeb开发- Gin不使用Nginx部署Vue项目 Golang并发开…...
从入门到精通：Ansible Shell 模块的应用与最佳实践
Ansible是一款强大的自动化运维工具，通过其模块化的设计，可以方便地管理和配置远程主机。作为Ansible的一个常用模块，shell 模块使得我们可以在目标主机上执行复杂的命令或脚本。无论是单一的命令，还是复杂的Shell脚本，…...
【Javascript Day1】javascript基础
javascript编程规则 弹窗（举例） alert("内容")，直接写在控制区生效 三种写法 1、行内js语法 ：需要注意引号的问题 <input type"button" value"提示窗" οnclick alert("消息") &…...
dbeaver导入导出数据库（sql文件形式）
目录 前言dbeaver导出数据库dbeaver导入数据库 前言 有时候我们需要复制一份数据库，可以使用dbeaver简单操作！ dbeaver导出数据库 选中数据库右键->工具->转储数据库 dbeaver导入数据库 选中数据库右键->工具->执行脚本 mysql 默…...
字玩FontPlayer开发笔记6 Tauri2设置菜单
字玩FontPlayer开发笔记6 Tauri2设置菜单 字玩FontPlayer是笔者开源的一款字体设计工具，使用Vue3 ElementUI开发，源代码： github: https://github.com/HiToysMaker/fontplayer gitee: https://gitee.com/toysmaker/fontplayer 笔记 字玩目…...
)
大学生HTML5期末作业 Web前端网页制作 html5+css3+js html+css+js网页设计 美食 美食3个页面(带js)
大学生HTML5期末作业 Web前端网页制作 html5css3js htmlcssjs网页设计 美食 美食3个页面(带js) 网页作品代码简单，可使用任意HTML辑软件（如：Dreamweaver、HBuilder、Vscode 、Sublime 、Webstorm、Text 、Notepad 等任意html编辑软件进行运行…...
创龙3588——debian根文件系统制作
文章目录 build.sh debian 执行流程build.sh源码流程 30-rootfs.sh源码流程 mk-rootfs-bullseys.sh源码流程 mk-sysroot.sh源码流程 mk-image.sh源码流程 post-build.sh 大致流程系统制作步骤 build.sh debian 执行流程 build.sh 源码 run_hooks() {DIR"$1"shiftf…...
element组件el-select、el-tree-select有值，不渲染lable
大致情况是这个样子的............ 之前vue页面和script脚本是放在一个页面的，今天把页面和脚本拆开了。这一拆不打紧，完犊子！它奶奶的el-select、el-tree-select这俩组件不正常显示了！！！ 我这个是vite-vue…...
【C++数据结构——线性表】顺序表的基本运算（头歌实践教学平台习题）【合集】
目录😋 任务描述 相关知识 一、线性表的基本概念 二、初始化线性表 三、销毁线性表 四、判定是否为空表 五、求线性表的长度 六、输出线性表 七、求线性表中某个数据元素值 八、按元素值查找 九、插入数据元素 十、删除数据元素 测试说明 通关代码 测…...
2025第1周 | JavaScript中的正则表达式
目录 1. 正则表达式是个什么东东？1.1 怎么定义正则1.2 对象字面量方式1.3 类创建方式 2. 怎么使用2.1 实例方法2.1.1 exec方法2.1.2 test方法 2.2 字符串中的方法2.2.1 match/matchAll2.2.2 replace/replaceAll2.2.3 split2.2.4 search 3. 规则3.1 修饰符3.2 字符类…...
模型 九屏幕分析法
系列文章 分享 模型，了解更多👉 模型_思维模型目录。九屏幕法：全方位分析问题的系统工具。 1 九屏幕分析法的应用 1.1 新产品研发的市场分析 一家科技公司计划开发一款新型智能手机，为了全面评估市场潜力和风险，他们…...
，冒泡排序 【C语言】)
快速排序(霍尔法)，冒泡排序 【C语言】
冒泡排序 效率低，但是稳定性高 代码 // 冒泡排序 void maopao(int a[]);int main() {int a1[10] {34,78,29,46,12,85,63,92,57,31};printf("\n排序前:\n");print(a1);maopao(a2);printf("冒泡排序后:");print(a2); }//冒泡排序 void maopao(…...
国产编辑器EverEdit - 两种删除空白行的方法
1 使用技巧：删除空白行 1.1 应用场景 用户在编辑文档时，可能会遇到很多空白行需要删除的情况，比如从网页上拷贝文字，可能就会存在大量的空白行要删除。 1.2 使用方法 1.2.1 方法1： 使用编辑主菜单 选择主菜单编辑 …...
20241230 AI智能体-用例学习（LlamaIndex/Ollama）
AI小白一枚，入门实验。 1. Pg-Hydra 颠覆数据库体验：Hydra —— 开源的列式存储 PostgreSQL-CSDN博客 git clone https://github.com/hydradatabase/hydra && cd hydra cp .env.example .env docker compose up psql postgres://postgres:hydra@127.0.0.1:5432 do…...
2024年终总结及计划
24年收获不少，早就想总结下，但是有的问题不想去思考，也不想去面对，就晚了几天，趁着加班总结反思下。 一、计划完成情况 1、生活 ①运动：继续坚持每周慢跑15公里，这是必须要做的。另外&#x…...
基于深度学习算法的AI图像视觉检测
基于人工智能和深度学习方法的现代计算机视觉技术在过去10年里取得了显著进展。如今，它被广泛用于图像分类、人脸识别、图像中物体的识别等。那么什么是深度学习？深度学习是如何应用在视觉检测上的呢？ 什么是深度学习？ 深度学习是…...
分布式环境下定时任务扫描时间段模板创建可预订时间段
🎯 本文详细介绍了场馆预定系统中时间段生成的实现方案。通过设计场馆表、时间段模板表和时间段表，系统能够根据场馆的提前预定天数生成未来可预定的时间段。为了确保任务执行的唯一性和高效性，系统采用分布式锁机制和定时任务，避…...
谷粒商城-高级篇完结-Sleuth+Zipkin 服务链路追踪
1、基本概念和整合 1.1、为什么用 微服务架构是一个分布式架构，它按业务划分服务单元，一个分布式系统往往有很多个服务单元。由于服务单元数量众多，业务的复杂性，如果出现了错误和异常，很难去定位 。主要体现在&#…...
GraphRAG：LLM之Graphrag接入milvus
前言 微软目前的graphrag更像个demo，数据量大的时候不是很友好的啊，所以将milvus接入了graphrag，看完这篇文章，其他数据库接入应该也没问题 注：这篇文章只是在search的时候接入进来，index过程或者说整个流…...
flink cdc oceanbase（binlog模式）
接上文：一文说清flink从编码到部署上线 环境：①操作系统：阿里龙蜥 7.9（平替CentOS7.9）；②CPU：x86；③用户：root。 预研初衷：现在很多项目有国产化的要求&#…...
【算法】算法初步
要学好数据结构和算法的设计与分析，请务必先打好C语言基础，因为C语言中的数据存储、内存映射、指针等等概念最接近计算机的底层原理，数据结构是数据在内存空间当中的组织形式，而算法则是提供了解决某个问题的一种思路，…...
Eureka原理
my: 服务注册与发现 心跳 自我保护 故障转移 Eureka 原理 Eureka 是一个由 Netflix 开源的服务注册与发现框架，广泛用于微服务架构中，尤其是 Spring Cloud 中的服务注册与发现。Eureka 的主要作用是管理和协调分布式系统中的服务实例，使…...
关于linux的ld.so.conf.d
初级代码游戏的专栏介绍与文章目录-CSDN博客 我的github：codetoys，所有代码都将会位于ctfc库中。已经放入库中我会指出在库中的位置。 这些代码大部分以Linux为目标但部分代码是纯C的，可以在任何平台上使用。 源码指引：github源…...
)
Linux Shell 脚本编程基础知识篇—awk的条件判断(3)
ℹ️大家好，我是练小杰，今天周五了，又是一周过去了😆 本文是有关Linux shell脚本编程的awk命令的条件语句，后续我会不断增加相关内容 ~~ 回顾:【awk字符串函数和内置变量】 更多Linux 相关内容请点击👉【Li…...
安装Cockpit服务，使用Web页面管理你的Linux服务器
说起管理 Linux 服务器，大家首先想到的使用 SecureCRT、Xshell、MobaXterm 等工具远程到服务器，然后使用命令行管理服务器。今天给大家介绍一个好玩的工具，名字叫Cockpit， Cockpit 是一个免费开源的基于 web 的 Linux 服务器管理…...
基于微信小程序的面部动作检测
目录 引言系统架构概述前端实现细节后端实现细节防止欺骗与误导的措施前后端数据交互详细细节关键技术选型关键技术框架与算法详细说明优化与注意事项总结 引言 微信小程序的面部动作检测的核心功能包括检测用户的左右转头、眨眼和张嘴动作，并根据检测结果逐步引导…...
使用npm 插件[mmdc]将.mmd时序图转换为图片
使用npm 插件[mmdc]将.mmd时序图转换为图片 1. 安装 mmdc2. 转换为图片 可以使用 mmdc （Mermaid CLI）这个工具来将 .mmd 时序图（Mermaid语法描述的时序图）转换为图片，以下是使用步骤： 1. 安装 mmdc 确保…...
服务端错误的处理和web安全检测
文章目录 I 服务端错误的处理业务返回码处理前端处理业务返回码nginx处理http状态码II web安全检测区分服务器类型主机扫漏III 使用 micro_httpd 搭建一个PHP站点步骤下载micro_httpd 并安装它配置micro_httpd 来服务PHP文件I 服务端错误的处理 服务端发生错误时，返回给前端的…...
周记-Repeater中的children和item区别
Repeater中的children和item 在开发qml的界面时，用到了Repeater，表头需要根据Repeater是否存在显示的项，来进行显示。 repeater.children[i] repeater.itemAt(i)如果判断有没有存在显示的项，可以用下面的代码 function is_exis…...
JVM实战—8.如何分析jstat统计来定位GC
大纲 1.使用jstat了解线上系统的JVM运行状况 2.使用jmap和jhat了解线上系统的对象分布 3.如何分析JVM运行状况并合理优化 4.使用jstat分析模拟的BI系统JVM运行情况 5.使用jstat分析模拟的计算系统JVM运行情况 6.问题汇总 1.使用jstat了解线上系统的JVM运行状况 (1)JVM的…...
halcon三维点云数据处理（五）创建代表工具和机器人底座的3D模型
目录 一、gen_robot_tool_and_base_object_model_3d 函数调用二、gen_arrow_object_model_3d 函数调用 首先说明一下这部分代码在find_box_3d这个例程中，非常好用的一个坐标系生成函数。 一、gen_robot_tool_and_base_object_model_3d 函数调用 RobotToolSize : 0.…...
React Router 向路由组件传state参数浏览器回退历史页面显示效果问题
昨天在看尚硅谷张天禹老师讲的 React教程p90，老师讲到 React路由的 replace模式和push模式，老师的演示效果与自己本地操作不太一样。 老师的效果：点击查看消息1，消息2，消息3 再点回退，可以依次查看到 消息…...
LabVIEW四旋翼飞行器姿态监测系统
四旋翼飞行器姿态监测系统是一个集成了高度、速度、俯仰角与滚转角数据采集与分析的系统，提高飞行器在复杂环境中的操作精确度与安全性。系统利用LabVIEW平台与硬件传感器相结合，实现实时数据处理与显示，有效地提升了四旋翼飞行器的监测与控制…...
HTML——66.单选框
<!DOCTYPE html> <html><head><meta charset"UTF-8"><title>单选框</title></head><body><!--input元素的type属性：(必须要有)--> <!--单选框:（如所住省会，性别选择&…...
av1学习笔记（二）：sequence_header_obu
av1学习笔记（二）：sequence_header_obu 目录 av1学习笔记（二）：sequence_header_obu1，图片的编解码方式1.1 seq_profile:1.2 still_picture1.3 reduced_still_picture_header1.4 编解码图像的宽高…...
嵌入式驱动开发详解8（阻塞/非阻塞/异步通信）
文章目录 前言阻塞非阻塞异步通知后续 前言 首先来回顾一下“中断”，中断是处理器提供的一种异步机制，我们配置好中断以后就 可以让处理器去处理其他的事情了，当中断发生以后会触发我们事先设置好的中断服务函数， 在中断服务函数…...
CSS进阶和SASS
目录 一、CSS进阶 1.1、CSS变量 1.2、CSS属性值的计算过程 1.3、做杯咖啡 1.4、下划线动画 1.5、CSS中的混合模式(Blending) 二、SASS 2.1、Sass的颜色函数 2.2、Sass的扩展(extend)和占位符(%)、混合(Mixin) 2.3、Sass的数学函数 2.4、Sass的模块化开发 2.5、Sass…...
求交错序列前N项和（PTA）C语言
本题要求编写程序，计算交错序列 1-2/33/5-4/75/9-6/11... 的前N项之和。 输入格式: 输入在一行中给出一个正整数N。 输出格式: 在一行中输出部分和的值，结果保留三位小数。 输入样例: 5输出样例: 0.917 代码： #include<stdio.h&g…...
【Delphi】创建COM服务器供浏览器（WebView）使用的操作步骤
首先创建一个VCL程序在程序的主界面放置WebView浏览器控件新增Automation Object（ActiveX 页面中），重点，注意WebView只支持IDisptcher接口然后根据这个提示实现实现其函数功能在浏览器中众注册： Delphi程序 procedure …...
 3.0.2.3版本)
Spring Security(maven项目) 3.0.2.3版本
前言 通过实践而发现真理，又通过实践而证实真理和发展真理。从感性认识而能动地发展到理性认识，又从理性认识而能动地指导革命实践，改造主观世界和客观世界。实践、认识、再实践、再认识，这种形式，循环往复以至无穷&a…...
如何删除 Docker 中的悬虚镜像？
在 Docker 中，悬虚镜像（Dangling Images）是指那些没有 标签 且没有被任何容器使用的镜像。这些镜像通常是由于构建过程中生成的中间层镜像或未正确清理的镜像残留。删除悬虚镜像可以释放磁盘空间并保持 Docker 环境的整洁。 1. 列出悬虚镜像…...
【JMeter】配置元件Config Element
1.配置元件 作用： 通用接口配置，协议，IP, 端口等，减少重复工作量 元件的分类 HTTP Request Defaults即HTTP请求默认值 作用： 可以配置成通用请求行的信息，可复用 JDBC Co…...
【Vue】分享一个快速入门的前端框架以及如何搭建
先上效果图: 登录 菜单: 下载地址: 链接：https://pan.baidu.com/s/1m-ZlBARWU6_2n8jZil_RAQ 提取码：ui20 … 主要是可以自定义设置token,更改后端请求地址较为方便。 应用设置: 登录与token设置: 在这里设置不用登录,可以请求的接口: request.js i…...
搭建开源版Ceph分布式存储
系统：Rocky8.6 三台2H4G 三块10G的硬盘的虚拟机 node1 192.168.2.101 node2 192.168.2.102 node3 192.168.2.103 三台虚拟机环境准备 1、配置主机名和IP的映射关系 2、关闭selinux和firewalld防火墙 3、配置时间同步且所有节点chronyd服务开机自启 1、配置主机名和…...
运动相机拍摄的视频打不开怎么办
3-10 GoPro和大疆DJI运动相机的特点，小巧、高清、续航长、拍摄稳定，很多人会在一些重要场合用来拍摄视频，比如可以用来拿在手里拍摄快速运动中的人等等。 但是毕竟是电子产品，有时候是会出点问题的，比如意外断电、摔重…...
信号处理-消除趋势项
matlab 版本 python 版本 import numpy as np import matplotlib.pyplot as plt from matplotlib import rcParams# 设置中文字体 rcParams[font.sans-serif] [SimHei] # 设置默认字体为黑体 rcParams[axes.unicode_minus] False # 解决负号显示问题def compute_time(n, f…...
民宿酒店预订系统小程序+uniapp全开源+搭建教程
一.介绍 一.系统介绍 基于ThinkPHPuniappuView开发的多门店民宿酒店预订管理系统，快速部署属于自己民宿酒店的预订小程序，包含预订、退房、WIFI连接、吐槽、周边信息等功能。提供全部无加密源代码，支持私有化部署。 二.搭建环境 系统环境…...
Java（1）入门基础
1. Java简介 1.1 什么是Java Java 是一款由Sun Microsystems公司（现为甲骨文公司Oracle Corporation的一部分）的James Gosling及其团队在1995年发布的高级编程语言。同时，Java 是一种面向对象的语言，这意味着它允许开发者通过创…...