【图论C++】链式前向星(图(树)的存储)

/*** @file            * @author          jUicE_g2R(qq:3406291309)————彬(bin-必应)*						一个某双流一大学通信与信息专业大二在读	* * @brief           一直在竞赛算法学习的路上* * @copyright       2023.9* @COPYRIGHT			 原创技术笔记:转载需获得博主本人同意,且需标明转载源* @language        C++* @Version         1.0还在学习中  */
  • UpData Log👆 2023.9.25 更新进行中
  • Statement0🥇 一起进步
  • Statement1💯 有些描述是个人理解,可能不够标准,但能达其意

技术提升站点

链式前向星

  • 链式前向星 建立在 邻接表 的基础上,从 2结点 开始记录(只画了部分部分):

  • 根据 邻接表 建立 链式前向星存图

h e a d [ u ] head[u] head[u] :记录 u节点 的 第一个邻居节点 的存储编号

i i i :存储编号

e d g e [ i ] . t o edge[i].to edge[i].to :u节点 的邻居节点(编号)

e d g e [ i ] . n e x t edge[i].next edge[i].next :记录 u节点 下一个邻居节点 的存储编号

(上图与下面的测试无关)

模拟存储过程

//test:手动模拟数据存储过程,假设: 存入边 2-1 2-3 2-4 2-5
//存入2-1
edge[0].to=1, edge[0].next=head[2]=-1, head[2]=0;
i		0
to		1
next	-1
//存入2-3
edge[1].to=3, edge[1].next=head[2]=0, head[2]=1;
i		0	1
to		1	3
next	-1	0
//存入2-4
edge[2].to=4, edge[2].next=head[2]=1, head[2]=2;
i		0	1	2
to		1	3	4
next	-1	0	1
//存入2-5
edge[2].to=5, edge[3].next=head[2]=2, head[2]=3;
i		0	1	2	3
to		1	3	4	5
next	-1	0	1	2
//2结点的边存储完成,head[2]=3

代码实现

const int N=1e5;
vector<int> head(N,-1);
int cot=0;
struct Edge{int to,next;//int weight;Edge():to(-1), next(-1){}				    //初始化为无邻居节点//Edge(int to, int w):to(to), weight(w);	//对 结构体的成员 进行赋值 的构造函数
} edge[N];
void Add_Edge(int u, int to, int w){edge[cot].to=to;//edge[cot].weight=w;edge[cot].next=head[u];                     //记录 上一个邻居节点 的 存储编号head[u]=cot++;                              //当前 邻居节点 的 存储编号,以便下一个邻居节点的访问
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/145127.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

django 实现:闭包表—树状结构

闭包表—树状结构数据的数据库表设计 闭包表模型 闭包表&#xff08;Closure Table&#xff09;是一种通过空间换时间的模型&#xff0c;它是用一个专门的关系表&#xff08;其实这也是我们推荐的归一化方式&#xff09;来记录树上节点之间的层级关系以及距离。 场景 我们 …

红米手机 导出 通讯录 到电脑保存

不要搞什么 云服务 不要安装什么 手机助手 不要安装 什么app 用 usb 线 连接 手机 和 电脑 手机上会跳出 提示 选择 仅传输文件 会出现下面的 一个 盘 进入 MIUI目录 然后进入 此电脑\Redmi Note 5\内部存储设备\MIUI\backup\AllBackup\20230927_043337 如何没有上面的文件&a…

MyBatis的一级缓存和二级缓存:原理和作用

MyBatis的一级缓存和二级缓存&#xff1a;原理和作用 引言 在数据库访问中&#xff0c;缓存是一种重要的性能优化手段&#xff0c;它可以减少数据库查询的次数&#xff0c;加快数据访问速度。MyBatis作为一款流行的Java持久层框架&#xff0c;提供了一级缓存和二级缓存来帮助…

C++(string类)

本节目标&#xff1a; 1、为什么要学习string类 2.标准库中的string类 3.vs和g下string结构说明 1.为什么学习string类 1.1 c语言中的字符串 C 语言中&#xff0c;字符串是以 \0 结尾的一些字符的集合&#xff0c;为了操作方便&#xff0c; C 标准库中提供了一些 str系列的…

1.6.C++项目:仿mudou库实现并发服务器之channel模块的设计

项目完整版在&#xff1a; 文章目录 一、channel模块&#xff1a;事件管理Channel类实现二、提供的功能三、实现思想&#xff08;一&#xff09;功能&#xff08;二&#xff09;意义&#xff08;三&#xff09;功能设计 四、代码&#xff08;一&#xff09;框架&#xff08;二…

3.物联网射频识别,(高频)RFID应用ISO14443-2协议

一。ISO14443-2协议简介 1.ISO14443协议组成及部分缩略语 &#xff08;1&#xff09;14443协议组成&#xff08;下面的协议简介会详细介绍&#xff09; 14443-1 物理特性 14443-2 射频功率和信号接口 14443-3 初始化和防冲突 &#xff08;分为Type A、Type B两种接口&…

深入理解操作系统- - 进程篇(1)

目录 进程解释&#xff1a; process in memory(进程在内存中包含什么) : 并发的进程&#xff1a; 进程定义&#xff1a; 个人定义&#xff1a; 书本定义&#xff1a; 进程状态&#xff1a; 进程何时离开CPU&#xff1a; 内部事件&#xff1a; 外部事件&#xff1a; 进…

卫星图像应用 - 洪水检测 使用DALI进行数据预处理

这篇文章是上一篇的延申。 运行环境&#xff1a;Google Colab 1. 当今的深度学习应用包含由许多串行运算组成的、复杂的多阶段数据处理流水线&#xff0c;仅依靠 CPU 处理这些流水线已成为限制性能和可扩展性的瓶颈。 2. DALI 是一个用于加载和预处理数据的库&#xff0c;可…

消息队列实现进程之间通信方式代码,现象

1、向消息队列中写入数据 #include<myhead.h>//消息结构体 typedef struct {long msgtype; //消息类型char data[1024]; //消息正文 }Msg_ds;#define SIZE sizeof(Msg_ds)-sizeof(long) //正文大小int main(int argc, const char *argv[]) {//1、创建…

raw智能照片处理工具DxO PureRAW mac介绍

DxO PureRAW Mac版是一款raw智能照片处理工具&#xff0c;该软件采用了智能技术&#xff0c;以解决影响所有RAW文件的七个问题&#xff1a;去马赛克&#xff0c;降噪&#xff0c;波纹&#xff0c;变形&#xff0c;色差&#xff0c;不想要的渐晕&#xff0c;以及缺乏清晰度。 Dx…

渗透测试之打点

请遵守中华人民共和国网络安全法 打点的目的是获取一个服务器的控制权限 1. 企业架构收集 &#xff08;1&#xff09;官网 &#xff08;2&#xff09;网站或下属的子网站&#xff0c;依次往下 天眼查 企查查 2. ICP 备案查询 ICP/IP地址/域名信息备案管理系统 使用网站…

基于微信小程序的宠物寄养平台小程序设计与实现(源码+lw+部署文档+讲解等)

文章目录 前言系统主要功能&#xff1a;具体实现截图论文参考详细视频演示为什么选择我自己的网站自己的小程序&#xff08;小蔡coding&#xff09;有保障的售后福利 代码参考源码获取 前言 &#x1f497;博主介绍&#xff1a;✌全网粉丝10W,CSDN特邀作者、博客专家、CSDN新星计…

浏览器输入 URL 并回车发生了什么

本文节选自我的博客&#xff1a;浏览器输入 URL 并回车发生了什么 &#x1f496; 作者简介&#xff1a;大家好&#xff0c;我是MilesChen&#xff0c;偏前端的全栈开发者。&#x1f4dd; CSDN主页&#xff1a;爱吃糖的猫&#x1f525;&#x1f4e3; 我的博客&#xff1a;爱吃糖…

国庆9.30

消息队列实现进程间通信 snd #include <myhead.h> //消息结构体 typedef struct {long msgtype; //消息类型char data[1024]; //消息正文 }Msg_ds;#define SIZE sizeof(Msg_ds)-sizeof(long) //正文大小int main(int argc, const char *argv[]) {//1、创建key…

常用数学分布

正态分布&#xff08;高斯分布&#xff09; 若随机变数 X X X 服从一个期望 μ \mu μ&#xff0c;标准差 的正态分布 σ \sigma σ&#xff0c;则记为 X ≈ N ( μ , σ 2 ) X \approx N(\mu,\sigma^2) X≈N(μ,σ2)&#xff0c;其密度函数为&#xff1a; f ( x ) 1 σ …

JSP学习笔记【三】——JQuery

前言 在写项目的时候需要动态对某组件的属性进行调整&#xff0c;我看网上的教程都是使用document.getElementById等&#xff0c;但我在eclipse编写.jsp文件的时候&#xff0c;却提示document cannot be resolved。由于我对jsp没有系统的了解以及无人可咨询&#xff0c;网上也…

lv5 嵌入式开发-10 信号机制(下)

目录 1 信号集、信号的阻塞 2 信号集操作函数 2.1 自定义信号集 2.2 清空信号集 2.3 全部置1 2.4 将一个信号添加到集合中 2.5 将一个信号从集合中移除 2.6 判断一个信号是否在集合中 2.7 设定对信号集内的信号的处理方式(阻塞或不阻塞) 2.8 使进程挂起&#xff08;…

仿真数据检查器如何比较数据

可以定制仿真数据检查器比较过程&#xff0c;以多种方式满足您的需求。在比较各运行时&#xff0c;仿真数据检查器会执行以下操作&#xff1a; 根据对齐设置&#xff0c;对齐基线运行和比较项运行中的信号对组。 仿真数据检查器不会比较无法对齐的信号。 根据指定的同步方法同…

机器学习——一元线性回归构造直线,并给出损失函数

目 录 Question 问题分析 1.概念补充 2.流程分析 3.注意 具体实现 最终成果 代码 思考&#xff1a; Question 在二维平面有n个点&#xff0c;如何画一条直线&#xff0c;使得所有点到该直线距离之和最短 如果能找到&#xff0c;请给出其损失函数 问题分析 1.概念…

数据集笔记:杭州地铁刷卡数据

1 数据位置&#xff1a; 链接: https://pan.baidu.com/s/1iLHomv5NRodB_3jr7FcFow 提取码: arse 全球城市计算AI挑战赛_算法大赛_天池大赛-阿里云天池的赛制 (aliyun.com) 2 数据集介绍 杭州20190101至20190125共25天地铁刷卡数据记录&#xff0c;共涉及3条线路81个地铁站约…