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

【图论 | 数据结构】用链式前向星存图(保姆级教程,详细图解+完整代码)

一、概述

链式前向星是一种用于存储图的数据结构,特别适合于存储稀疏图,它可以有效地存储图的边和节点信息,以及边的权重。

它的主要思想是将每个节点的所有出边存储在一起,通过数组的方式连接(类似静态数组实现链表)。这种方法的优点是存储空间小,查询速度快,尤其适合于处理大规模的图数据,在一些笔试或者竞赛的场景中经常使用

下面,我们用这张图来图解一下链式前向星的存储逻辑:

在这里插入图片描述

二、前置准备

注意看这里的设定,以及我加粗的提示。

  1. head数组:head[i]存储的是节点i的第一条边的编号。这样,我们可以通过head[i]快速找到从节点i出发的所有边。

  2. next数组:next[j]存储的是编号为j的边的下一条边的编号。这样,我们可以通过next[j]快速找到从同一个节点出发的下一条边。

  3. to数组:to[j]存储的是编号为j的边的终点节点编号。这样,我们可以通过to[j]快速找到边j的终点,也就是这条边要去往哪里。

  4. weight数组:weight[j]存储的是编号为j边的权重。这样,我们可以通过weight[j]快速找到边j的权重。

  5. cnt变量:cnt用于存储边的数量,也表示边的编号。每添加一条边,cnt就会增加1。这样,我们可以通过cnt快速知道当前图中边的数量,同时我们也认为cnt是新添加边的编号

三、初始化

public static void build(int n) {cnt = 1; // 边从1开始编号Arrays.fill(head, 1, n + 1, 0); // head[1 ... n] 全设为 0
}

在链式前向星中,我们使用cnt来作为边的编号,由于边的编号是从1开始的,所以初始化时我们将cnt设置为1。同时,将head数组的所有元素设置为0。因为head[i]存储的是节点i的第一条边的编号,所以,如果节点i没有出度(即没有从节点i出发的边),那么head[i]就应该为0。初始化时所有节点都没有出度,后续在添加边的时候,会更新对应的head[i]的值。

在这里插入图片描述

四、添加边(重点)

在链式前向星中添加边的操作是最核心的,它涉及到headnexttoweight数组的更新,以及边的编号cnt的自增。

在看代码之前,我们先回顾一下各个结构的下标以及值的含义:

  1. head数组:下标i表示节点编号,值head[i]表示从节点i出发的第一条边的编号。

  2. next数组:下标j表示边的编号,值next[j]表示编号为j的边的下一条边的编号。

  3. to数组:下标j表示边的编号,值to[j]表示编号为j的边的终点节点编号。

  4. weight数组:下标j表示边的编号,值weight[j]表示编号为j的边的权重。

结合上述含义,我们来看代码就很清晰了:

// (u, v, w): 有一条边,从u节点指向v节点,权重为w
// 在每一次添加边时,cnt都表示当前未分配的边的编号,添加边后cnt需++
public static void addEdge(int u, int v, int w) {next[cnt] = head[u];to[cnt] = v;weight[cnt] = w;head[u] = cnt;++cnt;
}

首先,我们需要更新next数组。next[cnt]存储的是编号为cnt的边的下一条边的编号。在添加新边时,我们将新边的next置为旧的头边号head[u],这样就可以通过next[cnt]快速找到从节点u出发的下一条边。

然后,我们需要更新to数组,将新边的终点设置为v,这样就可以通过to[cnt]快速找到边cnt的终点。

更新weight数组也很自然,就是将新边的权重设置为w,最后,我们将节点u的头边号修改为当前新边的编号,这样就可以通过head[u]快速找到从节点u出发的第一条边。

备注:记得每添加一条边,边的编号cnt就需要增加1

五、建图

建图分为有向图与无向图,输入的参数是一个二维数组edges作为输入,这个数组的每个元素都是一个长度为3的数组,代表一条边的两个端点和这条边的权重。

// 建有向图
public static void directGraph(int[][] edges) {for (int[] edge : edges) {addEdge(edge[0], edge[1], edge[2]); // 添加有向边

相关文章:

【图论 | 数据结构】用链式前向星存图(保姆级教程,详细图解+完整代码)

一、概述 链式前向星是一种用于存储图的数据结构,特别适合于存储稀疏图,它可以有效地存储图的边和节点信息,以及边的权重。 它的主要思想是将每个节点的所有出边存储在一起,通过数组的方式连接(类似静态数组实现链表)。这种方法的优点是存储空间小,查询速度快,尤其适…...

【蓝桥杯3.23小白赛】(详解)

第一题签到题不多说 【二进制王国】 #include <iostream> #include <vector> #include <algorithm> using namespace std;//int Cmp(string s1, string s2)测试了一下时间差确实很明显&#xff0c;还是用下面的内个 int Cmp(const string &s1,const st…...

设计模式之抽象工厂模式精讲

概念&#xff1a;为创建一组相关或相互依赖的对象提供一个接口&#xff0c;而且无须指定他们的具体类。 抽象工厂模式是工厂方法模式的升级版本。在存在多个业务品种或分类时&#xff0c;抽象工厂模式是一种更好的解决方式。 抽象工厂模式的UML类图如下&#xff1a; 可以看…...

初识云原生、虚拟化、DevOps

文章目录 K8S虚拟化DevOpsdevops平台搭建工具大数据架构 K8S master 主节点&#xff0c;控制平台&#xff0c;Master节点负责核心的调度、管理和运维&#xff0c;不需要很高性能&#xff0c;不跑任务&#xff0c;通常一个就行了&#xff0c;也可以开多个主节点来提高集群可用度…...

怎麼實現Nginx反向代理?

Nginx是一款開源軟體&#xff0c;可以作為Web伺服器、負載均衡器和反向代理使用&#xff0c;是高性能的HTTP和反向代理伺服器。其中反向代理是Nginx的一項重要特性。接下來&#xff0c;我們詳細講一下Nginx反向代理的實現和應用。 反向代理是什麼&#xff1f; 代理一詞通常指的…...

IOS面试题编程机制 71-75

71. 简述有哪几种手势通知方法?-(void)touchesBegan:(NSSet*)touchedwithEvent:(UIEvent*)event; -(void)touchesMoved:(NSSet*)touched withEvent:(UIEvent*)event; -(void)touchesEnded:(NSSet*)touchedwithEvent:(UIEvent*)event; -(void)touchesCanceled:(NSSet*)touchedw…...

JMeter元件作用域和执行顺序

JMeter元件作用域和执行顺序 元件的基本介绍基本元件总结 作用域的基本介绍作用域的原则元件执行顺序Jmeter第一个案例&#xff1a; Jmeter三个重要组件&#xff08;重点&#xff09;线程组特点线程组分类线程组的属性案例分析 HTTP请求案例一&#xff08;使用HTTP请求路径来传…...

Jmeter 聚合报告之 90% Line 正确理解

今天看了些关于Jmeter 聚合报告之 90% Line 的一些博客 关于90% Line 的算法各有各自的见解 。 90%Line可以用公式计算&#xff1a; 100/总个数每一个所占的百分比&#xff0c;90%/每一个所占的百分比90%Line的序号&#xff08;从小到大排&#xff09; 例如&#xff1a;1.2.3.…...

2024 解决 Failed to launch process [ElasticSearch]

操作系统&#xff1a;centos 7 (x86) sonarQube不能使⽤root账号进⾏启动&#xff0c;所以需要创建普通⽤户及其⽤户组 一、问题描述&#xff1a;使用root启动时&#xff0c;一直反馈 SonarQube is not running 问题原因&#xff1a;不能够使用root用户进行启动 解决方案…...

平台介绍-搭建赛事运营平台(4)

存储结构是赛事运营平台的核心设计内容。平台整体采用分库结构&#xff0c;各赛事独立享有自己的数据库。但是选手、家长、赛事组织机构、培训机构、老师、志愿者信息都是存储在核心库中。新增报名时&#xff0c;家长或老师首先看自己名下有无该选手信息&#xff08;对照关系也…...

系列学习前端之第 7 章:一文掌握 AJAX

1、AJAX 简介 AJAX 全称为 Asynchronous JavaScript And XML&#xff08;中文名&#xff1a;阿贾克斯&#xff09;&#xff0c;就是异步的 JS 和 XML。AJAX 不是新的编程语言&#xff0c;而是一种将现有的标准组合在一起使用的新方式。AJAX 可以在浏览器中向服务器发送异步请求…...

iOS - Runtime - Class的结构

文章目录 iOS - Runtime - Class的结构前言1. Class的结构1.1 Class的结构1.1.1 objc_class1.1.2 class_rw_t1.1.3 class_ro_t 1.2 class_rw_t和class_ro_t的区别1.3 class_rw_t和class_ro_t的关系1.3.1 分析关系1.3.2 原因 1.4 method_t1.4.1 Type Encoding1.4.2 types iOS - …...

MySQL高阶语句(一)

一、常用查询 &#xff08;增、删、改、查&#xff09; 对 MySQL 数据库的查询&#xff0c;除了基本的查询外&#xff0c;有时候需要对查询的结果集进行处理。 例如只取 10 条数据、对查询结果进行排序或分组等等 1、按关键字排序 PS:类比于windows 任务管理器 使用 SELECT 语…...

MySQL知识总结

一条 SQL 语句过来的流程是什么样的&#xff1f; ①当客户端连接到 MySQL 服务器时&#xff0c;服务器对其进行认证。可以通过用户名与密码认证&#xff0c;也可以通过 SSL 证书进行认证。登录认证后&#xff0c;服务器还会验证客户端是否有执行某个查询的操作权限。 ②在正式…...

Go-Gin-Example 第八部分 优化配置接口+图片上传功能

文章目录 前情提要本节目标 优化配置结构讲解落实修改配置文件优化配置读取及设置初始化顺序第一步 验证 抽离file 实现上传图片接口图片名加密封装image的处理逻辑编写上传图片的业务逻辑增加图片上传的路由 验证实现前端访问 http.FileServerr.StaticFS修改文章接口新增、更新…...

阿里云国际DDoS高防的定制场景策略

DDoS高防的定制场景策略允许您在特定的业务突增时段&#xff08;例如新业务上线、双11大促销等&#xff09;选择应用独立于通用防护策略的定制防护策略模板&#xff0c;保证适应业务需求的防护效果。您可以根据需要设置定制场景策略。 背景信息 定制场景策略提供基于业务场景…...

v4l2采集视频

Video4Linux2&#xff08;v4l2&#xff09;是用于Linux系统的视频设备驱动框架&#xff0c;它允许用户空间应用程序直接与视频设备&#xff08;如摄像头、视频采集卡等&#xff09;进行交互。 linux系统下一切皆文件&#xff0c;对视频设备的操作就像对文件的操作一样&#xff…...

Spring Cloud 八:微服务架构中的数据管理

Spring Cloud 一&#xff1a;Spring Cloud 简介 Spring Cloud 二&#xff1a;核心组件解析 Spring Cloud 三&#xff1a;API网关深入探索与实战应用 Spring Cloud 四&#xff1a;微服务治理与安全 Spring Cloud 五&#xff1a;Spring Cloud与持续集成/持续部署&#xff08;CI/C…...

Chrome/Edge 使用 Markdown Viewer 查看 Markdown 格式文件

Chrome/Edge 使用 Markdown Viewer 查看 Markdown 格式文件 0. 引言1. 安装 Markdown Viewer 插件2. 使用 Markdown Viewer 阅读 Markdown 格式文件 0. 引言 大部分程序员都喜欢 Markdown 格式的文件&#xff0c;这时给一些没有在电脑上安装 Markdown 编辑器的同事分享资料时&…...

flutter 弹窗之系列一

自定义不受Navigator影响的弹窗 class MyHomePage extends StatefulWidget {const MyHomePage({super.key, required this.title});final String title;overrideState<MyHomePage> createState() > _MyHomePageState(); }class _MyHomePageState extends State<MyH…...

如何用Steam Achievement Manager掌控游戏成就?解锁7大实用技巧

如何用Steam Achievement Manager掌控游戏成就&#xff1f;解锁7大实用技巧 【免费下载链接】SteamAchievementManager A manager for game achievements in Steam. 项目地址: https://gitcode.com/gh_mirrors/st/SteamAchievementManager 在游戏世界中&#xff0c;成就…...

Applied Intelligence投稿实战:从格式要求到高接受率的5个关键策略

1. 精准匹配期刊范围&#xff1a;避免编辑秒拒的第一道防线 投稿Applied Intelligence期刊时&#xff0c;最容易被忽视却最关键的一步就是研究范围匹配。我审过30篇稿件&#xff0c;发现80%的"desk rejection"&#xff08;编辑直接拒稿&#xff09;都源于研究方向与…...

水墨江南模型效果对比:不同参数下的笔触与渲染风格

水墨江南模型效果对比&#xff1a;不同参数下的笔触与渲染风格 最近在尝试用AI生成水墨画&#xff0c;发现一个挺有意思的现象&#xff1a;同一个“水墨江南”模型&#xff0c;用不同的参数设置&#xff0c;画出来的效果天差地别。有时候是寥寥几笔的写意小品&#xff0c;有时…...

OpenAirInterface (OAI) 实战:如何用USRP搭建你的第一个5G仿真环境(附避坑指南)

OpenAirInterface (OAI) 实战&#xff1a;如何用USRP搭建你的第一个5G仿真环境&#xff08;附避坑指南&#xff09; 当5G技术从实验室走向商业化时&#xff0c;开源软件无线电平台OpenAirInterface&#xff08;OAI&#xff09;正成为开发者验证创新想法的关键工具。不同于商业设…...

从零搭建无人船:两年实战后,我总结的ArduPilot+Pixhawk避坑全流程

从零搭建无人船&#xff1a;两年实战后&#xff0c;我总结的ArduPilotPixhawk避坑全流程 第一次把无人船放进水里时&#xff0c;GPS信号突然丢失&#xff0c;船体在河中央失控打转——这个惊心动魄的瞬间让我意识到&#xff0c;开源飞控的实战应用远不是下载代码、连接硬件那么…...

Neeshck-Z-lmage_LYX_v2多场景落地:LoRA动态加载赋能数字人直播背景实时生成系统

Neeshck-Z-lmage_LYX_v2多场景落地&#xff1a;LoRA动态加载赋能数字人直播背景实时生成系统 1. 项目简介&#xff1a;一个专为本地绘画优化的轻量级工具 如果你对AI绘画感兴趣&#xff0c;特别是想体验国产的Z-Image文生图模型&#xff0c;但又被复杂的部署流程、繁琐的参数…...

Qwen3-14B镜像轻量化设计:50GB系统盘+40GB数据盘高效空间管理

Qwen3-14B镜像轻量化设计&#xff1a;50GB系统盘40GB数据盘高效空间管理 1. 镜像概述与核心优势 Qwen3-14B私有部署镜像是一款专为RTX 4090D 24GB显存显卡优化的轻量化解决方案。通过精心设计的50GB系统盘40GB数据盘架构&#xff0c;实现了大模型部署的空间效率最大化。这个镜…...

王二明古方草解毒茶商城模式解析

王二明古方草解毒茶商城模式解析&#xff1a;架构、争议与合规思考在社交电商与大健康产业的交叉赛道中&#xff0c;“王二明古方草解毒茶”凭借其独特的草本茶饮定位与多级分销模式&#xff0c;曾一度引发市场关注。该模式以产品为核心&#xff0c;通过数字化商城系统构建了一…...

GitLab中文版在Windows Docker部署后,解决‘git clone’和‘git push’失败的几个关键检查点

GitLab中文版Windows Docker部署后git clone和git push故障排查指南 当你终于完成了GitLab中文版在Windows Docker上的部署&#xff0c;准备大展拳脚时&#xff0c;却发现git clone和git push命令频频报错&#xff0c;这种挫败感我深有体会。本文将带你系统排查四个关键环节&am…...

TwinCAT3-UDP自定义协议实现高效点对点通信

1. TwinCAT3-UDP通信基础与场景解析 在工业自动化领域&#xff0c;设备间的高效数据交换一直是工程师们关注的焦点。TwinCAT3作为倍福&#xff08;Beckhoff&#xff09;推出的自动化软件平台&#xff0c;其UDP通信功能为点对点数据传输提供了轻量级解决方案。与TCP协议相比&…...