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

链式前向星(最通俗易懂的讲解)

链式前向新:用于存储图的 边集 数组

前言

当我们存储图的时候,往往会使用 邻接矩阵 或是 邻接表。

邻接矩阵 好写,但太浪费空间,节点一多就存不下;

邻接表 效率高,但涉及指 ,不好写容易出错;用 vector 又可能超时。

链式前向星 就是一个相对中庸的存储方式,虽然说,链式前向星 使用并不广泛,但在需要使用复杂 邻接表 时,这就是一个较好的选择。

链式前向星 其实就是 静态建立的邻接表,时间复杂度为O(m),空间复杂度也为O(m)。


思想

对于下图:

图1

 输入为:

5 7

1 2 3

2 3 1

1 3 4

1 5 3

4 1 5

4 5 1

3 4 2

我们将起点都是 from  的边串在一起,用 head[from] 存储头节点(见图2,下图为最终形式)

 图2

具体插入操作与链表相似 (见图3)

图3


代码与运行结果

里有注释,慢慢理解

#include <iostream>
#include <cstring>using namespace std;const int N = 2e2 + 5, M = 1e3 + 5;int n, m, cnt; //n个点,m条边
struct Edge {int to, value, next;//终点,边权,同起点的上一条边的编号
} edge[M]; //边集
int head[N]; //head[i] 表示以 i 为起点的第一条边在边集数组的位置(编号)void add_edge(int from, int to, int value) { //u起点,v终点,w边权edge[++ cnt] = {to, value, head[from]}, head[from] = cnt;// 赋终点权值 并且将新的节点赋在头上	更新头
}int main() {cin >> n >> m;/* 初始化 */cnt = 0;memset(head, -1, sizeof head);/* 加边 */for (int i = 1; i <= m; i ++) { //输入m条边int a, b, c;cin >> a >> b >> c;add_edge(a, b, c);}/* 遍历 */for (int i = 1; i <= n; i ++) {cout << ">" << i << "\n";bool hase = false;for (int j = head[i]; j != -1; j = edge[j].next) //遍历以i为起点的边cout << i << " " << edge[j].to << " " << edge[j].value << "\n", hase = true;if (!hase)cout << "nothing\n"; //第i个节点没有出去的边}return 0;
}
/*
5 7
1 2 3
2 3 1
1 3 4
1 5 3
4 1 5
4 5 1
3 4 2
*/

可以注意到 head 的初始值为 -1

这使得 head[i] 中第一个边的 next 为 -1,这正作为链的结尾(见图3

所以当 访问指针 ( j ) 为 -1 时,就代表访问结束了

运行结果参考

图4

(从 图2~4 和 代码中,我们都可以发现 链式前向星 是按输入倒着存的)


结语

个人觉得 链式前向星 和 邻接表 是几乎一样的,只不过 前者 是静态的,后者 是动态的

相关文章:

链式前向星(最通俗易懂的讲解)

链式前向新&#xff1a;用于存储图的 边集 数组 前言 当我们存储图的时候&#xff0c;往往会使用 邻接矩阵 或是 邻接表。 邻接矩阵 好写&#xff0c;但太浪费空间&#xff0c;节点一多就存不下&#xff1b; 邻接表 效率高&#xff0c;但涉及指 &#xff0c;不好写容易出错…...

【C++设计模式】(四)创建型模式:简单工厂模式,工厂方法模式,抽象工厂模式

文章目录 &#xff08;四&#xff09;创建型模式&#xff1a;简单工厂模式&#xff0c;工厂方法模式&#xff0c;抽象工厂模式简单工厂模式工厂方法模式抽象工厂模式 &#xff08;四&#xff09;创建型模式&#xff1a;简单工厂模式&#xff0c;工厂方法模式&#xff0c;抽象工…...

浅析Golang的Context

文章目录 1. 简介2. 常见用法2.1 控制goroutine的生命周期&#xff08;cancel&#xff09;2.2 传递超时&#xff08;Timeout&#xff09;信息2.3 传递截止时间&#xff08;Deadline&#xff09;2.4 传递请求范围内的全局数据 &#xff08;value&#xff09; 3 特点3.1 上下文的…...

生日礼物C++代码

#include<bits/stdc.h> using namespace std; string s; int a,b; int main(){cout<<" 生日之地"<<\n;cout<<" 1.开始游戏"<<" 2.不想开始"<<\n;cin>>a;if(a1||a2){if(a2)cout<<…...

使用python基于DeepLabv3实现对图片进行语义分割

DeepLabv3 介绍 DeepLabv3 是一种先进的语义分割模型&#xff0c;由 Google Research 团队提出。它在 DeepLab 系列模型的基础上进行了改进&#xff0c;旨在提高图像中像素级分类的准确性。以下是 DeepLabv3 的详细介绍&#xff1a; 概述DeepLabv3 是 DeepLab 系列中的第三代…...

【漏洞复现】泛微OA E-Office do_excel.php 任意文件写入漏洞

》》》产品描述《《《 泛微0-0fice是一款标准化的协同 OA办公软件&#xff0c;泛微协同办公产品系列成员之一,实行通用化产品设计&#xff0c;充分贴合企业管理需求&#xff0c;本着简洁易用、高效智能的原则&#xff0c;为企业快速打造移动化、无纸化、数字化的办公平台。 》》…...

算法(食物链)

240. 食物链 题目 动物王国中有三类动物 A,B,C&#x1d434;,&#x1d435;,&#x1d436;&#xff0c;这三类动物的食物链构成了有趣的环形。 A&#x1d434; 吃 B&#x1d435;&#xff0c;B&#x1d435; 吃 C&#x1d436;&#xff0c;C&#x1d436; 吃 A&#x1d434;。…...

ubuntu20.04系统安装zookeeper简单教程

Ubuntu系统中安装和配置Zookeeper的完整指南 Apache Zookeeper是一个开源的分布式协调服务&#xff0c;广泛用于分布式应用程序中管理配置、提供命名服务、分布式同步以及组服务等。在本教程中&#xff0c;我们将详细介绍如何在Ubuntu系统中安装Zookeeper&#xff0c;并进行相关…...

.NET Core 高性能并发编程

一、高性能大并发架构设计 .NET Core 是一个高性能、可扩展的开发框架&#xff0c;可以用于构建各种类型的应用程序&#xff0c;包括高性能大并发应用程序。为了设计和开发高性能大并发 .NET Core 应用程序&#xff0c;需要考虑以下几个方面&#xff1a; 1. 异步编程 异步编程…...

B 私域模式升级:开源技术助力传统经销体系转型

一、引言 1.1 研究背景 随着市场竞争加剧&#xff0c;传统经销代理体系面临挑战。同时&#xff0c;开源技术发展迅速&#xff0c;为 B 私域升级带来新机遇。在当今数字化时代&#xff0c;企业面临着日益激烈的市场竞争。传统的经销代理体系由于管理效率低下、渠道局限、库存压…...

vue之vuex的使用及举例

Vuex是专门为Vue.js设计的集中式状态管理架构&#xff0c;它允许你将所有的组件共享状态存储在一个单独的地方&#xff0c;即“store”&#xff0c;并以相应的规则保证状态以一种可预测的方式发生变化。以下是Vuex的基本使用方法&#xff1a; 一、安装Vuex 对于Vue 2项目&…...

使用 vite 快速初始化 shadcn-vue 项目

Vite 1. 创建项目 使用 vite 创建一个新的 vue 项目。 如果你正在使用 JS 模板&#xff0c;需要存在 jsconfig.json 文件才能正确运行 CLI。 # npm 6.x npm create vitelatest my-vue-app --template vue-ts# npm 7, extra double-dash is needed: npm create vitelatest m…...

微信小程序:一个小程序跳转至另一个小程序

一、微信小程序支持一个小程序跳转至另一个小程序吗&#xff1f; 支持。 1.1、目标小程序需开放被跳转&#xff1a;目标小程序需要在其 app.json 文件中配置 navigateToMiniProgramAppIdList&#xff0c;将源小程序的 AppID 加入其中。 1.2、用户授权&#xff1a;用户需要授…...

Java第二阶段---10方法带参---第二节 方法重载(Overloading)

1.概念 在同一个类中&#xff0c;方法名相同&#xff0c;参数列表不同的多个方法构造成方法重载 2.示例 public class Calculator{public int sum(int a,int b){return ab;}public int sum(int a,int b,int c){return abc;} } 3.误区 下面的方法是否属于方法重载&#xff…...

Java Web 之 Session 详解

在 JavaWeb 开发中&#xff0c;Session 就像网站的专属记忆管家&#xff0c;为每个用户保管着重要的信息和状态&#xff0c;确保用户在网站的旅程顺畅无阻。 场景一&#xff1a; 想象你去一家大型超市购物&#xff0c;推着购物车挑选商品。这个购物车就如同 Session&#xff…...

63.5 注意力提示_by《李沐:动手学深度学习v2》pytorch版

系列文章目录 文章目录 系列文章目录注意力提示生物学中的注意力提示查询、键和值注意力的可视化使用 show_heatmaps 显示注意力权重代码示例 代码解析结果 小结练习 注意力提示 &#x1f3f7;sec_attention-cues 感谢读者对本书的关注&#xff0c;因为读者的注意力是一种稀缺…...

vscode 的terminal 输出打印行数限制设置

修改 VSCODE 的 settings.json文件 "terminal.integrated.scrollback": 100000, {"extensions.ignoreRecommendations": true,"workbench.colorTheme": "Monokai","explorer.confirmDelete": false,"editor.fontSize…...

深入挖掘C++中的特性之一 — 继承

目录 1.继承的概念 2.举个继承的例子 3.继承基类成员访问方式的变化 1.父类成员的访问限定符对在子类中访问父类成员的影响 2.父类成员的访问限定符子类的继承方式对在两个类外访问子类中父类成员的影响 4.继承类模版&#xff08;注意事项&#xff09; 5.父类与子类间的转…...

Linux 下 poll 详解

在Linux系统编程中&#xff0c;poll 是一个强大的多路复用&#xff08;I/O 多路复用&#xff09;函数&#xff0c;用于同时监控多个文件描述符的事件&#xff0c;特别是在处理网络套接字或其他I/O设备时。相比于select&#xff0c;poll 支持监控更多的文件描述符&#xff0c;并…...

virtualbox配置为NAT模式后物理机和虚拟机互通

virtualbox配置为 NAT模式后&#xff0c;虚拟机分配到的 IP地址一般是 10.xx网段的&#xff0c;虚拟机可以通过网络地址转换访问物理机所在的网络&#xff0c;但若不做任何配置&#xff0c;则物理机无法直接访问虚拟机。 virtualbox在提供 NAT配置模式时&#xff0c;也提供了端…...

轻舟体重管理大模型:赋能减重全病程管理,构建智能体重健康生态

在“健康中国2030”战略深入推进的背景下&#xff0c;慢性病防控与全民体重管理已成为公共卫生体系的重要议题。随着肥胖及相关代谢性疾病发病率持续上升&#xff0c;传统的体重干预模式已难以满足全人群、全生命周期的健康管理需求。在此趋势下&#xff0c;基于人工智能技术的…...

为什么你的Java车载服务在-40℃冷启动失败?温度敏感型ClassLoader加载异常的12小时紧急修复路径

第一章&#xff1a;为什么你的Java车载服务在-40℃冷启动失败&#xff1f;温度敏感型ClassLoader加载异常的12小时紧急修复路径低温环境并非仅影响硬件可靠性——JVM 的类加载机制在极端低温下会触发底层文件系统与内存映射的隐式行为偏移。某车规级 Java 服务在-40℃冷启动时反…...

学生信息管理系统--Python进阶项目

1.需求分析: ​需求&#xff1a;根据操作流程以及系统需求&#xff0c;完成面向对象版学生管理系统项目开发 ​a.可以显示基本的版本信息和操作界面; ​b.可以通过键盘输入信息来完成基本功能,例如选择序号、确认退出、添加学生、修改信息等; ​c.学生属性信息有姓名、性别、年…...

【JupyterLab实战】构建跨平台AI算力监控仪表盘

1. 为什么需要跨平台AI算力监控&#xff1f; 在AI开发过程中&#xff0c;我们经常遇到这样的场景&#xff1a;模型训练到一半突然卡死&#xff0c;却不知道是GPU内存爆了还是CPU瓶颈&#xff1b;多卡并行时某张卡莫名其妙跑不满&#xff1b;昇腾芯片的温度报警频繁触发却找不到…...

League-Toolkit:颠覆式英雄联盟客户端增强工具的全攻略

League-Toolkit&#xff1a;颠覆式英雄联盟客户端增强工具的全攻略 【免费下载链接】League-Toolkit An all-in-one toolkit for LeagueClient. Gathering power &#x1f680;. 项目地址: https://gitcode.com/gh_mirrors/le/League-Toolkit League-Toolkit是一款基于官…...

Adafruit NeoMatrix 原理与坐标映射详解

1. 项目概述 Adafruit NeoMatrix 是一款专为 NeoPixel 矩阵与网格显示设备设计的嵌入式图形库&#xff0c;其核心定位是作为 Adafruit_GFX 图形抽象层的硬件适配实现。它并非独立渲染引擎&#xff0c;而是通过继承并扩展 Adafruit_GFX 的绘图接口&#xff08;如 drawPixel() …...

STM32除零运算不崩溃的机制与配置解析

1. STM32单片机除零运算不崩溃的底层机制解析 在嵌入式开发领域&#xff0c;STM32系列单片机因其出色的性能和丰富的外设资源而广受欢迎。许多从传统PC平台转向嵌入式开发的工程师都会发现一个有趣的现象&#xff1a;在STM32上执行除零操作时&#xff0c;程序竟然不会像在PC上那…...

Geoserver空间查询全解析:从基础bbox到高级CQL_FILTER的完整指南

Geoserver空间查询全解析&#xff1a;从基础bbox到高级CQL_FILTER的完整指南 当你面对海量地理空间数据时&#xff0c;如何快速准确地提取所需信息&#xff1f;Geoserver作为开源地理信息系统&#xff08;GIS&#xff09;的中枢神经&#xff0c;其强大的空间查询能力往往被开发…...

BiliTools:B站资源高效管理与下载完全指南

BiliTools&#xff1a;B站资源高效管理与下载完全指南 【免费下载链接】BiliTools A cross-platform bilibili toolbox. 跨平台哔哩哔哩工具箱&#xff0c;支持下载视频、番剧等等各类资源 项目地址: https://gitcode.com/GitHub_Trending/bilit/BiliTools BiliTools是一…...

终极指南:如何让2012-2015年老款Mac安装最新macOS系统

终极指南&#xff1a;如何让2012-2015年老款Mac安装最新macOS系统 【免费下载链接】OpenCore-Legacy-Patcher Experience macOS just like before 项目地址: https://gitcode.com/GitHub_Trending/op/OpenCore-Legacy-Patcher 您的2012-2015年老款Mac是否已被苹果官方抛…...