c++链式前向星

这篇具有很好参考价值的文章主要介绍了c++链式前向星。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

介绍

模板

具体介绍

用法

结语


链式前向星,一听就很让人头疼的名字,博主曾经也很不清楚。但是,经过了时间的沉淀和苦思冥想,我明白了。而我作为一个学习者,过来人,也深知其中难以理解的地方,今天我就给大家介绍链式前向星,力求将大家讲明白。而我也会把理解的难点重点拿出来讲。

介绍

链式前向星,是一种储存图的信息的方法,有着很高的空间利用率和较低的时间复杂度,而且遍历也很简单高效。其实存图的方法不在少数,优秀的也很多,那为什么要讲链式前向星呢?我们拿其他的方法对比就行了,比如最最常用的 vector ,作为 stl 库的一员,也有很高的空间利用率与时间效率。不过相较于链式前向行来说,vector 每次申请内存所花费的时间是不少的,而且还会申请两倍的内存,全方面比链式前向星差。虽然差的不多,但在考试的时候能少一毫秒都是好的!

所以,我的建议是:考场上尽量用链式前向星,除非一种情况:时间来不及。没错,链式前向星码量要大一点,查错也繁杂一点。不过,看完这篇文章,掌握了链式前向星之后,这些都不是问题!

模板

在讲之前,我们先给出模板,方便后续的讲解。

定义:

struct node{
	int to, next, w;
}e[N];

加边:

void add(int u, int v, int w){
	e[++cnt].to = v;
	e[cnt].w = w;
	e[cnt].next = head[u];
	head[u] = cnt;
}

具体介绍

模板,相信很多人都背上了。可是理解了吗?不一定。下面我们就来详细讲解。

我们看到上面的模板,很头疼对吧。其实也不是完全不理解,比如 to 代表这条边的终点,w 代表边的权值,这些都好理解。

我们主要讲很让人头疼的地方:

  1. cnt
  2. head数组
  3. next

来一组数据,可以更加具体的想:

u->v to next cnt head[u]
1->3 3 0 1 1
2->5 5 0 2 2
1->2 2 1 3 3
3->4 4 0 4 4
1->4 4 3 5 5
2->4 4 2 6 6
3->5 5 4 7 7
4->5 5 0 8 8

第一个,也是最容易想到的一个。cnt 是一个计数器,用于记录边的编号。比如:1到3这条边我定义为第一条边,2到5这一条边认为是第二条边。边的编号并没有特定的顺序,按照的是输入的先后顺序,cnt的含义理解了吧。

第二个,到了最难理解的 head 了,这也是博主当年没有理解的。按照网上流行的说法,head[a] 是以 a 为起点的最后一条边。这么说还是太难理解了,我们换个方式解释。head 数组的作用是什么呢?我们看到上面的 cnt,作为一个边的编号,但我们怎么知道 e[1] 代表那一条边呢?因为我们存边是按照输入的顺序,并不知道 e[cnt] 具体是哪个点到哪个点的边。而 head 数组就充当了一个索引的角色。比如说,我要找点以3为起点的边,按照常理应该是 e[3] 数组才对,但是由于我们存边是按照 cnt 的值,所以 e[3] 储存的并不是以 3 为起点的边,那我们怎么办?只能用一个数组,让它的下表作为一条边的起点,值就是这条边的编号。简单来讲,我们要知道以1 为起点的边,用的不是 e[1],而是 e[head[1]],这下大概明白 head 的意思了吧。

但是 head[a] 只能存一条边,如果以 a 为起点有很多条边怎么办呢?我们连着下面的 next 一起讲。

第三个,next。上面说到,head 只能存一条边,要是同一个点有很多条边,那怎么办呢?我们只需要把以这个点为起点的上一条边的 head 存到这一条边(还是以这个点为起点)的 next 中就可以了。

举个例子吧,不然太抽象了。还是这个数据,c++链式前向星,# c++数据结构,c++,数据结构

 看第一条边、第三条边和第五条边。我们看到 e[5].next = 3,而第三条边正好是以1为起点的边。e[3].next = 1,第1条变也是以1为起点的边。

这是怎么做到的呢?我们只需要把当前这条边的 cnt ,就是编号,存入head中。比如第3条边,我们把 head[1] 赋值成当前的 cnt,这样下一次再有以1为起点的边时,我们就把那条边的 next 赋值成 head[1] 就行了。

这样,next 就存储了以当前边起点为起点的上一条边的编号(不是绕口令)。然后 head[u] 就存储了当前边的编号,这样下一次有 u 点为起点的边的时候,就能通过 head[u] 找到上一条边的编号了。

光听我说你可能还不理解,把上面的多看几遍,结合数据,在草稿纸上自己模拟一遍存图的过程,可能有更深刻的理解。

用法

先把上面的理解了再往下看。

存完边了我们怎么遍历呢?还是先放模板再讲:

for(int i = head[u]; i; i = e[i].next){
	cout << e[i].to;
}

上面就是一个遍历以 u 为起点的边的程序,i 就是边的编号。

i = e[i].next 是什么意思呢?i 本来就是边的编号,e 的下标也是边的编号,所以直接用 e[i].next 代表与这条边起点相同的上一条边的编号,这样就可以遍历以 u 为起点的所有边了。

下面来个实战吧(题目自己出的):

题面:

有 n 个节点,m 条边(有向),给出每条边的起点 u ,终点 v ,权值 w,请从点1到点 n 输出以这个点为起点的每条边的和权值。

输入:

第一行 n 和 m,代表有 n 个节点,m 条边。第二到 m + 1 行,每行三个整数 u、v、w,意义见体面。

输出:

共 n 行,第 i 行输出以 i 为起点的每条边的终点和权值。

样例输入:

3 3

1 3 5

2 3 4

1 2 -1

样例输出:

2 -1 3 5

3 4

这题只需要把上面的模板熟练运用就可以了,下面给出源代码:

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 5;
int n, m, x, y, z, head[N], cnt;
struct node{
	int to, next, w;
}e[N];
void add(int x, int y, int z){
	e[++cnt].to = y;
	e[cnt].w = z;
	e[cnt].next = head[x];
	head[x] = cnt;
}
int main(){
	cin >> n >> m;
	for(int i = 1; i <= m; i++){
		cin >> x >> y >> z;
		add(x, y, z);
	}
	for(int i = 1; i <= n; i++){
		for(int j = head[i]; j; j = e[j].next){
			cout << e[j].to << " " << e[j].w << " ";
		}
		cout << endl;
	}
    return 0;
}

结语

关于链式前向星的原理以及用法的解释就这么多了,这只是一个存图的工具,运用还得看具体的题目,比如有些无向图,存图就要正反存两次。有些还要判断重边,等等。

这是一个很重要的工具,要做到运用游刃有余,理解原理。

讲的还有不清楚的地方,可以私信我,慢慢讲~文章来源地址https://www.toymoban.com/news/detail-676289.html

到了这里,关于c++链式前向星的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 图的存储--邻接矩阵/边集数组/邻接表/链式邻接表/链式前向星

    使用二维数组w[u][v]存储点u到点v的边的权值。 一般应用在点数不多的稠密图 时间复杂度:O(n 2 ) 空间复杂度:O(n 2 ) 边集数组e[i]存储第i条边的「起点、终点、边权」。在kruskal算法中,将边按边权排序,直接存边。 时间复杂度:O(nm) 空间复杂度:O(m) 出边数组e[u][i]存储u的所

    2024年02月02日
    浏览(38)
  • 算法复习6.1链式前向星(代码块式理解)

    一号初始节点head[1]=3(cnt=3)指向四号节点 edge[3(cnt=3)],其中edge[3].to=4 即四号节点 ,同时令edge[3].next=(new)cnt 指向下一个 ... (循环) 有点像指针,如果功能不复杂的话,可以直接简写为vector快捷操作  

    2024年02月21日
    浏览(62)
  • 【图论】图的存储--链式前向星存图法以及深度优先遍历图

    无向图 - 就是一种特殊的有向图 - 只用考虑有向图的存储即可 邻接矩阵 邻接表 邻接表 存储结构: (为每一个点开了一个单链表,存储这个点可以到达哪个点) 1 : 3-4-null 2 : 1-4-null 3 : 4-null 4 : null 插入一条新的边 比如要插一条边: 2-3 先找到 2 对应的 单链表 然后将 3 插入到单链表

    2024年04月14日
    浏览(46)
  • 数据结构与算法—二叉树数组表示(ArrayBinTree)、二叉树的链式表示(LinkedBinTree)的基于C++模板代码实现

    1、二叉树的顺序表示:ArrayBinTree.h 二叉树的顺序表示法操作方便,但缺点是容易造成存储空间浪费。 这是一个用数组实现的二叉树类模板。它可以创建一个空树,也可以在指定的位置插入结点并设置结点的值,可以删除子树,并支持逐层遍历。使用该类时,需要提供一个元

    2024年02月06日
    浏览(44)
  • 【数据结构】二叉树——链式结构

    目录  一、前置声明 二、二叉树的遍历 2.1 前序、中序以及后序遍历 2.2 层序遍历 三、节点个数以及高度 3.1 节点个数 3.2 叶子节点个数 3.3 第k层节点个数 3.4 二叉树的高度/深度 3.5 查找值为x的节点 四、二叉树的创建和销毁 4.1 构建二叉树 4.2 二叉树销毁 4.3 判断二叉树

    2024年02月16日
    浏览(47)
  • 【数据结构】二叉树链式结构

    🚀write in front🚀 📜所属专栏:初阶数据结构 🛰️博客主页:睿睿的博客主页 🛰️代码仓库:🎉VS2022_C语言仓库 🎡您的点赞、关注、收藏、评论,是对我最大的激励和支持!!! 关注我,关注我,关注我 , 你们将会看到更多的优质内容!!   在之前的二叉树的顺序结

    2024年02月03日
    浏览(41)
  • 数据结构(顺序结构、链式结构、索引结构、散列结构)

    数据结构,就是一种程序设计优化的方法论,研究数据的逻辑结构和物理结构以及它们之间相互关系,并对这种结构定义相应的运算, 目的是加快程序的执行速度、减少内存占用的空间 。 数据的逻辑结构指反映数据元素之间的逻辑关系,而与数据的存储无关,是独立于计算

    2024年02月03日
    浏览(82)
  • 【数据结构】二叉树之链式结构

    🔥 博客主页 : 小羊失眠啦. 🎥 系列专栏 : 《C语言》 《数据结构》 《Linux》 《Cpolar》 ❤️ 感谢大家点赞👍收藏⭐评论✍️ 在学习二叉树各种各样的操作前,我们先来回顾一下二叉树的概念: 二叉树是度不超过2的树,由根结点和左右2个子树组成,每个子树也可以看作

    2024年02月04日
    浏览(46)
  • 数据结构——二叉树的链式结构

      个人主页 : 日刷百题 系列专栏 : 〖C语言小游戏〗〖Linux〗〖数据结构〗  〖C语言〗 🌎 欢迎各位 → 点赞 👍+ 收藏 ⭐️+ 留言 📝  ​ 这里我们使用先序遍历的思想来创建二叉树,这里的内容对于刚接触二叉树的朋友可能有些难理解,不妨先看完下面的二叉树各种遍历

    2024年02月05日
    浏览(48)
  • 【数据结构】二叉树的链式结构

    学习链式二叉树要知道三种遍历方式,便于对二叉树的节点以及左子树和右子树进行操作。 前序遍历:根、左子树、右子树 中序遍历:左子树、根、右子树 后序遍历:左子树、右子树、根 以下图为例: 得到的结果: 前序遍历:1 2 3 4 5 6 中序遍历:3 2 1 5 4 6 后序遍历:3 2

    2024年02月08日
    浏览(57)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包