链式前向星(最通俗易懂的讲解)
链式前向新:用于存储图的 边集 数组
前言
当我们存储图的时候,往往会使用 邻接矩阵 或是 邻接表。
邻接矩阵 好写,但太浪费空间,节点一多就存不下;
邻接表 效率高,但涉及指 ,不好写容易出错;用 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 和 代码中,我们都可以发现 链式前向星 是按输入倒着存的)
结语
个人觉得 链式前向星 和 邻接表 是几乎一样的,只不过 前者 是静态的,后者 是动态的
相关文章:
链式前向星(最通俗易懂的讲解)
链式前向新:用于存储图的 边集 数组 前言 当我们存储图的时候,往往会使用 邻接矩阵 或是 邻接表。 邻接矩阵 好写,但太浪费空间,节点一多就存不下; 邻接表 效率高,但涉及指 ,不好写容易出错…...
【C++设计模式】(四)创建型模式:简单工厂模式,工厂方法模式,抽象工厂模式
文章目录 (四)创建型模式:简单工厂模式,工厂方法模式,抽象工厂模式简单工厂模式工厂方法模式抽象工厂模式 (四)创建型模式:简单工厂模式,工厂方法模式,抽象工…...
浅析Golang的Context
文章目录 1. 简介2. 常见用法2.1 控制goroutine的生命周期(cancel)2.2 传递超时(Timeout)信息2.3 传递截止时间(Deadline)2.4 传递请求范围内的全局数据 (value) 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 是一种先进的语义分割模型,由 Google Research 团队提出。它在 DeepLab 系列模型的基础上进行了改进,旨在提高图像中像素级分类的准确性。以下是 DeepLabv3 的详细介绍: 概述DeepLabv3 是 DeepLab 系列中的第三代…...
【漏洞复现】泛微OA E-Office do_excel.php 任意文件写入漏洞
》》》产品描述《《《 泛微0-0fice是一款标准化的协同 OA办公软件,泛微协同办公产品系列成员之一,实行通用化产品设计,充分贴合企业管理需求,本着简洁易用、高效智能的原则,为企业快速打造移动化、无纸化、数字化的办公平台。 》》…...
算法(食物链)
240. 食物链 题目 动物王国中有三类动物 A,B,C𝐴,𝐵,𝐶,这三类动物的食物链构成了有趣的环形。 A𝐴 吃 B𝐵,B𝐵 吃 C𝐶,C𝐶 吃 A𝐴。…...
ubuntu20.04系统安装zookeeper简单教程
Ubuntu系统中安装和配置Zookeeper的完整指南 Apache Zookeeper是一个开源的分布式协调服务,广泛用于分布式应用程序中管理配置、提供命名服务、分布式同步以及组服务等。在本教程中,我们将详细介绍如何在Ubuntu系统中安装Zookeeper,并进行相关…...
.NET Core 高性能并发编程
一、高性能大并发架构设计 .NET Core 是一个高性能、可扩展的开发框架,可以用于构建各种类型的应用程序,包括高性能大并发应用程序。为了设计和开发高性能大并发 .NET Core 应用程序,需要考虑以下几个方面: 1. 异步编程 异步编程…...
B 私域模式升级:开源技术助力传统经销体系转型
一、引言 1.1 研究背景 随着市场竞争加剧,传统经销代理体系面临挑战。同时,开源技术发展迅速,为 B 私域升级带来新机遇。在当今数字化时代,企业面临着日益激烈的市场竞争。传统的经销代理体系由于管理效率低下、渠道局限、库存压…...
vue之vuex的使用及举例
Vuex是专门为Vue.js设计的集中式状态管理架构,它允许你将所有的组件共享状态存储在一个单独的地方,即“store”,并以相应的规则保证状态以一种可预测的方式发生变化。以下是Vuex的基本使用方法: 一、安装Vuex 对于Vue 2项目&…...
使用 vite 快速初始化 shadcn-vue 项目
Vite 1. 创建项目 使用 vite 创建一个新的 vue 项目。 如果你正在使用 JS 模板,需要存在 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…...
微信小程序:一个小程序跳转至另一个小程序
一、微信小程序支持一个小程序跳转至另一个小程序吗? 支持。 1.1、目标小程序需开放被跳转:目标小程序需要在其 app.json 文件中配置 navigateToMiniProgramAppIdList,将源小程序的 AppID 加入其中。 1.2、用户授权:用户需要授…...
Java第二阶段---10方法带参---第二节 方法重载(Overloading)
1.概念 在同一个类中,方法名相同,参数列表不同的多个方法构造成方法重载 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.误区 下面的方法是否属于方法重载ÿ…...
Java Web 之 Session 详解
在 JavaWeb 开发中,Session 就像网站的专属记忆管家,为每个用户保管着重要的信息和状态,确保用户在网站的旅程顺畅无阻。 场景一: 想象你去一家大型超市购物,推着购物车挑选商品。这个购物车就如同 Sessionÿ…...
63.5 注意力提示_by《李沐:动手学深度学习v2》pytorch版
系列文章目录 文章目录 系列文章目录注意力提示生物学中的注意力提示查询、键和值注意力的可视化使用 show_heatmaps 显示注意力权重代码示例 代码解析结果 小结练习 注意力提示 🏷sec_attention-cues 感谢读者对本书的关注,因为读者的注意力是一种稀缺…...
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.继承类模版(注意事项) 5.父类与子类间的转…...
Linux 下 poll 详解
在Linux系统编程中,poll 是一个强大的多路复用(I/O 多路复用)函数,用于同时监控多个文件描述符的事件,特别是在处理网络套接字或其他I/O设备时。相比于select,poll 支持监控更多的文件描述符,并…...
virtualbox配置为NAT模式后物理机和虚拟机互通
virtualbox配置为 NAT模式后,虚拟机分配到的 IP地址一般是 10.xx网段的,虚拟机可以通过网络地址转换访问物理机所在的网络,但若不做任何配置,则物理机无法直接访问虚拟机。 virtualbox在提供 NAT配置模式时,也提供了端…...
IDEA运行Tomcat出现乱码问题解决汇总
最近正值期末周,有很多同学在写期末Java web作业时,运行tomcat出现乱码问题,经过多次解决与研究,我做了如下整理: 原因: IDEA本身编码与tomcat的编码与Windows编码不同导致,Windows 系统控制台…...
零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?
一、核心优势:专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发,是一款收费低廉但功能全面的Windows NAS工具,主打“无学习成本部署” 。与其他NAS软件相比,其优势在于: 无需硬件改造:将任意W…...
ios苹果系统,js 滑动屏幕、锚定无效
现象:window.addEventListener监听touch无效,划不动屏幕,但是代码逻辑都有执行到。 scrollIntoView也无效。 原因:这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作,从而会影响…...
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南 在数字化营销时代,邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天,我们将深入解析邮件打开率、网站可用性、页面参与时…...
听写流程自动化实践,轻量级教育辅助
随着智能教育工具的发展,越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式,也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建,…...
佰力博科技与您探讨热释电测量的几种方法
热释电的测量主要涉及热释电系数的测定,这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中,积分电荷法最为常用,其原理是通过测量在电容器上积累的热释电电荷,从而确定热释电系数…...
GruntJS-前端自动化任务运行器从入门到实战
Grunt 完全指南:从入门到实战 一、Grunt 是什么? Grunt是一个基于 Node.js 的前端自动化任务运行器,主要用于自动化执行项目开发中重复性高的任务,例如文件压缩、代码编译、语法检查、单元测试、文件合并等。通过配置简洁的任务…...
莫兰迪高级灰总结计划简约商务通用PPT模版
莫兰迪高级灰总结计划简约商务通用PPT模版,莫兰迪调色板清新简约工作汇报PPT模版,莫兰迪时尚风极简设计PPT模版,大学生毕业论文答辩PPT模版,莫兰迪配色总结计划简约商务通用PPT模版,莫兰迪商务汇报PPT模版,…...
基于Java+VUE+MariaDB实现(Web)仿小米商城
仿小米商城 环境安装 nodejs maven JDK11 运行 mvn clean install -DskipTestscd adminmvn spring-boot:runcd ../webmvn spring-boot:runcd ../xiaomi-store-admin-vuenpm installnpm run servecd ../xiaomi-store-vuenpm installnpm run serve 注意:运行前…...
PH热榜 | 2025-06-08
1. Thiings 标语:一套超过1900个免费AI生成的3D图标集合 介绍:Thiings是一个不断扩展的免费AI生成3D图标库,目前已有超过1900个图标。你可以按照主题浏览,生成自己的图标,或者下载整个图标集。所有图标都可以在个人或…...
