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

SEO_10个提升网站排名的实用SEO技巧分享(370 )

SEO:10个提升网站排名的实用SEO技巧分享 在当今的互联网时代&#xff0c;一个网站的成功离不开搜索引擎优化&#xff08;SEO&#xff09;。SEO不仅仅是一套技术&#xff0c;更是一种思维方式。本文将详细分享十个实用的SEO技巧&#xff0c;帮助你提升网站的排名&#xff0c;吸…...

竞赛获奖保研加分测评:除了挑战杯,哪些垂直赛事含金量更高?

在 2026 年推免&#xff08;保研&#xff09;竞争进入白热化的背景下&#xff0c;工科学子的加分项已不仅仅是绩点的博弈&#xff0c;更是工程实战能力的短兵相接。随着教育部《关于加强新时代卓越工程师培养的指导意见》的深入实施&#xff0c;各大名校对人才的评价标准正从“…...

FLAC3D 6.0 和 7.0 版本输出塑形区体积及破坏区域体积那些事儿

FLAC3D输出塑形区体积&#xff0c;适用于6.0和7.0版本&#xff0c;输出剪切破坏区域&#xff0c;张拉破坏区域体积&#xff0c;如图2中所示在岩土工程数值模拟领域&#xff0c;FLAC3D 是一款相当强大的工具。今天咱就聊聊如何在 FLAC3D 6.0 和 7.0 版本中输出塑形区体积&#x…...

实战指南:基于快马平台生成git自动化部署脚本,实现ci/cd流水线

今天想和大家分享一个实战中特别实用的技巧&#xff1a;如何用git结合自动化脚本来简化版本发布和部署流程。这个方案在我们团队的实际项目中已经稳定运行了大半年&#xff0c;效果非常不错。 版本号自动打tag功能 这个脚本的核心功能之一就是自动读取项目中的版本号文件&…...

小米智能家居无缝接入Home Assistant的3种高效方法

小米智能家居无缝接入Home Assistant的3种高效方法 【免费下载链接】ha_xiaomi_home Xiaomi Home Integration for Home Assistant 项目地址: https://gitcode.com/GitHub_Trending/ha/ha_xiaomi_home Xiaomi Home集成是小米官方为Home Assistant提供的智能家居集成组件…...

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

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

COMSOL相场法/水平集方法多孔介质两相驱替模型案例 附随机孔隙度几何程序 助力学习两相流驱替模拟

COMSOL相场法&#xff08;/水平集方法&#xff09;多孔介质驱替模型案例&#xff0c;可以提供随机孔隙度几何程序。 提供基于COMSOL中相场方法模拟多孔介质两相驱替&#xff08;水气、油水等等&#xff09;的算例&#xff08;也可以定做水平集驱替的算例&#xff09;&#xff0…...

马年市场快报分析:欧美组合式一氧化碳及可燃气体报警器指南

马年市场快报分析&#xff1a;欧美组合式一氧化碳及可燃气体报警器指南根据您提供的快报内容&#xff0c;我将从专业角度逐步分析欧美组合式一氧化碳&#xff08;CO&#xff09;及可燃气体报警器的关键信息&#xff0c;包括安全标准、风险因素、探测器区别、安装建议以及相关产…...

别再为联合仿真头疼了!手把手教你用Amesim 2019和Matlab 2022b配置S-Function(Win10环境)

从零搭建Amesim与Matlab联合仿真环境&#xff1a;避坑指南与实战技巧 联合仿真技术已成为多物理场系统设计的黄金标准&#xff0c;但配置过程却让无数工程师在深夜的办公室里抓狂——编译器版本冲突、环境变量设置错误、接口编译失败&#xff0c;每一个环节都可能成为项目进度的…...

在wsl中利用快马平台五分钟搭建flask博客后端原型

最近在Windows系统下折腾WSL&#xff08;Windows Subsystem for Linux&#xff09;时&#xff0c;发现结合InsCode(快马)平台可以快速搭建项目原型&#xff0c;特别适合需要Linux环境特性的开发验证。就拿搭建一个Flask博客后端来说&#xff0c;传统方式从零开始配置环境、编写…...