构造有向(无向)加权图

邻接表的一般构造

#include<bits/stdc++.h>
#define N 1e4
using namespace std;
typedef struct BP{
int P;//边所指的顶点位置
struct BP *nextB;//指向下一条边的指针
int Q;//储存边的信息
}BP;
typedef struct  DP{
int date;//顶点信息
BP *FirstB;//指向第一条连接该点的边
}DP,lin[N];//构建邻接表类型lin;

int main()
{

return 0;
}

以上步骤些许繁杂,利用STL构建邻接表就方便多了

以下是一vector构建的邻接表

#include<bits/stdc++.h>
#define N 1e4
using namespace std;
typedef struct Node{//构建储存节点信息模块
int Pin;//定点编号
int Quan;//边权值
}Node;
vector<Node>lin[N];

int main()
{
//操作方式:
//顶点u,连接点v,边权值w
int u,v,w;
cin>>u>>v>>w;
Node P;//创建新节点
P.Pin=v,P.Quan=w;
lin[u].push_back(P);

return 0;
}


链式前向星

适合于存储稀疏图,它可以有效地存储图的边和节点信息,以及边的权重

存储的数据结构:

#define N 1e4
typedef struct t{
int to;//边的终点
int w;//边的权值
int next;//指向同一起点的上一条边
}t[N];
int last[N];//邻接表头节点数组
int con=1;//记录第几条边

实现过程

int u,v,w;//u顶点,v被指向点,w边权
cin>>u>>v>>w;
//实现函数
void add(int u,int v,int w)
{
	t[con].to=v;
	t[con].w=w;
	t[con].next=last[con];//采用头插法,新插入的点记录顶点的下一个点
	last[u]=con++;//更新顶点连接的第一个点
	}

以下图为例
在这里插入图片描述

过程演示
初始
last[1]=-1
last[2]=-1
last[3]=-1
last[4]=-1
刚开始没录入连接关系,各点未连接其它点,赋值为-1
cin>>u>>v>>w;
首先输入:1 2 1 //1指向2权值为1;con==1;
last[u]=-1 (last[1]=-1)

t[1].to=2//该边指向点2
t[1].w=1//该边权值为1
t[1].next=last[1]//采用头插法,将该边指向顶点连接的第一条边,由于第一个点还未连接,所以不指向任何点,值仍为-1
(这里是以边指向边来记录的)

last[u]=con++ (last[1]==1 );//更新顶点连接的第一条边,con自增,准备录入第2条边
第二条边和第三条边同样如此
假设第2和3边录入,此时con
4;

输入:1 3 4//1指向3,边权为4
last[u]=-1 (last[1]=1)//刚才顶点1已连接第一条边,所以等于1;

t[4].to=3//该边指向3
t[4].w=4//该边权值为4
t[4].next=last[u]==1//刚才顶点已连接第一条边,所以,第四条边连接第一条边
last[1]=con++//更新顶点信息为顶点连接第四条边

第五条边同上。
在这里插入图片描述
完成数据录入后,数据储存如上图所示

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

RabbitMQ交换机类型

RabbitMQ交换机类型 1、RabbitMQ工作模型2、RabbitMQ交换机类型2.1、Fanout Exchange&#xff08;扇形&#xff09;2.1.1、介绍2.1.2、示例2.1.2.1、生产者2.1.2.2、消费者2.1.2.3、测试 2.2、Direct Exchange&#xff08;直连&#xff09;2.2.1、介绍2.2.2、示例2.2.2.1、生产…

字符串算法

字符串 1.kmp匹配算法Anya and 1100 1.kmp匹配算法 模板题链接 不懂可以看这个~详细的思路 #include <string> #include <iostream>using namespace std; const int N 1000010;string s,p;// s[]是长文本&#xff0c;p[]是模式串&#xff0c;n是s的长度&#xff…

WSL开发--利用Git连接远程仓库(详细步骤)

这篇文章主要介绍了如何将本地项目推送到 GitLab 上&#xff0c;并且避免每次提交都需要输入用户名和密码。文中分步讲解了配置 GitLab SSH 密钥以及配置 Git 远程仓库地址的方法。以下是文章的优化和简洁版&#xff1a; 将本地项目推送到 GitLab 并配置 SSH 免密登录 为了方便…

操作系统(10) (并发(2)------基于软件/硬件/操作系统层面解决两个进程之间的临界区问题/抢占式/非抢占式内核)

目录 1. 基于软件层面(Petersons Solution) Petersons Solution 满足三个要求: 好处: 缺点 2. 基于硬件层面 1. Disabling Interrupts (禁用中断) 概念解释&#xff1a; 代码框架&#xff1a; 要求&#xff1a; 禁用中断的好处与问题&#xff1a; 2. Test and Set Lock (…

基于 JAVASSM 框架沙县小吃点餐系统

基于 JAVASSM 框架&#xff08;即 Java Spring Spring MVC MyBatis&#xff09;开发一个沙县小吃点餐系统。 步骤一&#xff1a;需求分析 明确系统需要实现的功能&#xff0c;比如&#xff1a; 用户注册和登录浏览菜单添加菜品到购物车下单并支付订单管理后台管理&#…

零基础Java第十三期:继承与多态(一)

目录 一、继承 1.1. 继承的目的 1.2. 继承的概念 1.3. 继承的语法 1.4. 父类的访问 1.5. 继承中的重载与重写 1.6. 子类的构造方法 1.7. 再谈初始化 一、继承 1.1. 继承的目的 我们来定义一个Dog和Cat的类&#xff1a; public class Dog {public int age;public Strin…

论文翻译 | Evaluating the Robustness of Discrete Prompts

摘要 离散提示已被用于调整预训练语言模型&#xff0c;以适应不同的NLP任务。特别是&#xff0c;从一小组训练实例中生成离散提示的自动方法已经报告了优越的性能。然而&#xff0c;仔细观察习得的提示会发现&#xff0c;它们包含嘈杂和反直觉的词汇结构&#xff0c;而这些在手…

SQL,力扣题目1549,每件商品的最新订单【窗口函数】

一、力扣链接 LeetCode_1549 二、题目描述 表: Customers ------------------------ | Column Name | Type | ------------------------ | customer_id | int | | name | varchar | ------------------------ customer_id 是该表主键. 该表包含消费者的…

mysql查表相关练习

作业要求&#xff1a; 单表练习&#xff1a; 1 . 查询出部门编号为 D2019060011 的所有员工 2 . 所有财务总监的姓名、编号和部门编号。 3 . 找出奖金高于工资的员工。 4 . 找出奖金高于工资 40% 的员工。 5 找出部门编号为 D2019090011 中所有财务总监&#xff0c;和…

广东网站设计提升你网站在搜索引擎中的排名

在当今网络盛行的时代&#xff0c;拥有一个设计优良的网站&#xff0c;对企业的在线发展至关重要。特别是对于广东地区的企业来说&#xff0c;网站设计不仅仅是美观的问题&#xff0c;更直接影响着搜索引擎中的排名。因此&#xff0c;精心策划和设计的网站&#xff0c;能够显著…

qt QGroupBox详解

1、概述 QGroupBox是Qt框架中的一个容器控件&#xff0c;主要用于组织和管理一组相关的控件&#xff08;如按钮、复选框、文本框等&#xff09;&#xff0c;并为这些控件提供一个框架和标题。通过使用QGroupBox&#xff0c;可以创建具有逻辑分组和视觉层次结构的用户界面&…

数据库管理-第256期 Oracle DB 23.6新特性一览(20241031)

数据库管理256期 2024-10-31 数据库管理-第256期 Oracle DB 23.6新特性一览&#xff08;20241031&#xff09;1 AI向量搜索&#xff1a;新的向量距离度量2 混合向量索引3 分区&#xff1a;本地邻近分区向量索引4 持久邻近图向量索引5 稀疏向量6 邻居图向量索引的事务支持7 特征…

应急响应----本地环境配置,对内存马的研究分析

应急响应----本地环境配置,对内存马查杀研究分析 注:后续添加的补充内容框架型内存马 SpringController型内存马:动态注册Controller及映射路由。 SpringInterceptor型内存马:动态注册Interceptor及映射路由。 启动环境: Spring框架启动(Controller型内存马和Intercept…

JAVA 插入 JSON 对象到 PostgreSQL

博主主页:【南鸢1.0】 本文专栏&#xff1a;JAVA 目录 ​编辑 简介 所用&#xff1a; 1、 确保 PostgreSQL 数据库支持 JSON&#xff1a; 2、添加 PostgreSQL JDBC 驱动 3、安装和运行 PostgreSQL 4、建立数据库的连接 简介 在现代软件开发中&#xff0c;由于 JSON 数据…

AUTOSAR CP NVRAM Manager规范导读

一、NVRAM Manager功能概述 NVRAM Manager是AUTOSAR(AUTomotive Open System ARchitecture)框架中的一个模块,负责管理非易失性随机访问存储器(NVRAM)。它提供了一组服务和API,用于在汽车环境中存储、维护和恢复NV数据。以下是NVRAM Manager的一些关键功能: 数据存储和…

机器学习:我们能用机器学习来建立投资模型吗

机器学习模型能解决什么投资问题&#xff1f; 利用机器学习解决投资问题的思路&#xff0c;其实和在互联网领域解决推荐、广告问题的思路是一样的&#xff0c;只不过利用的特征完全变了。推荐、广告模型利用的是用户的年龄、性别&#xff0c;物品的类别、价格等特征&#xff0c…

FBX福币交易所国际油价突然大涨!美伊针锋相对

11月4日早上,国际原油大幅高开。WTI原油一度涨超2%。 消息面上,主要产油国宣布延长自愿减产措施至12月底 FBX福币凭借用户友好的界面和对透明度的承诺,迅速在加密货币市场中崭露头角,成为广大用户信赖的平台。 石油输出国组织(欧佩克)发表声明说,8个欧佩克和非欧佩克产油国决…

Flarum:简洁而强大的开源论坛软件

Flarum简介 Flarum是一款开源论坛软件&#xff0c;以其简洁、快速和易用性而闻名。它继承了esoTalk和FluxBB的优良传统&#xff0c;旨在提供一个不复杂、不臃肿的论坛体验。Flarum的核心优势在于&#xff1a; 快速、简单&#xff1a; Flarum使用PHP构建&#xff0c;易于部署&…

独立开发的个人品牌打造:个人IP与独立开发的结合

引言 个人品牌程序员也需要打造。在当今的创意经济中&#xff0c;个人IP与独立开发的结合成为了一种趋势&#xff0c;为个体带来了前所未有的机会和可能性。本文将探讨如何通过打造个人IP来增强独立开发的影响力&#xff0c;并探索这种结合为个人带来的潜在价值。 个人IP的重…

细说STM32单片机USART中断收发RTC实时时间并改善其鲁棒性的方法

目录 一、工程目的 1、 目标 2、通讯协议及应对错误指令的处理目标 二、工程设置 三、程序改进 四、下载与调试 1、合规的指令 2、 proBuffer[0]不是# 3、proBuffer[4]不是; 4、指令长度小于5 5、指令长度大于5 6、proBuffer[2]或proBuffer[3]不是数字 7、;位于p…