当前位置: 首页 > 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;也提供了端…...

网络编程(Modbus进阶)

思维导图 Modbus RTU&#xff08;先学一点理论&#xff09; 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议&#xff0c;由 Modicon 公司&#xff08;现施耐德电气&#xff09;于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...

在rocky linux 9.5上在线安装 docker

前面是指南&#xff0c;后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...

Objective-C常用命名规范总结

【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名&#xff08;Class Name)2.协议名&#xff08;Protocol Name)3.方法名&#xff08;Method Name)4.属性名&#xff08;Property Name&#xff09;5.局部变量/实例变量&#xff08;Local / Instance Variables&…...

Linux云原生安全:零信任架构与机密计算

Linux云原生安全&#xff1a;零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言&#xff1a;云原生安全的范式革命 随着云原生技术的普及&#xff0c;安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测&#xff0c;到2025年&#xff0c;零信任架构将成为超…...

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...

NLP学习路线图(二十三):长短期记忆网络(LSTM)

在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...

HDFS分布式存储 zookeeper

hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架&#xff0c;允许使用简单的变成模型跨计算机对大型集群进行分布式处理&#xff08;1.海量的数据存储 2.海量数据的计算&#xff09;Hadoop核心组件 hdfs&#xff08;分布式文件存储系统&#xff09;&a…...

mac 安装homebrew (nvm 及git)

mac 安装nvm 及git 万恶之源 mac 安装这些东西离不开Xcode。及homebrew 一、先说安装git步骤 通用&#xff1a; 方法一&#xff1a;使用 Homebrew 安装 Git&#xff08;推荐&#xff09; 步骤如下&#xff1a;打开终端&#xff08;Terminal.app&#xff09; 1.安装 Homebrew…...

Bean 作用域有哪些?如何答出技术深度?

导语&#xff1a; Spring 面试绕不开 Bean 的作用域问题&#xff0c;这是面试官考察候选人对 Spring 框架理解深度的常见方式。本文将围绕“Spring 中的 Bean 作用域”展开&#xff0c;结合典型面试题及实战场景&#xff0c;帮你厘清重点&#xff0c;打破模板式回答&#xff0c…...

Neko虚拟浏览器远程协作方案:Docker+内网穿透技术部署实践

前言&#xff1a;本文将向开发者介绍一款创新性协作工具——Neko虚拟浏览器。在数字化协作场景中&#xff0c;跨地域的团队常需面对实时共享屏幕、协同编辑文档等需求。通过本指南&#xff0c;你将掌握在Ubuntu系统中使用容器化技术部署该工具的具体方案&#xff0c;并结合内网…...