目录
介绍
模板
具体介绍
用法
结语
链式前向星,一听就很让人头疼的名字,博主曾经也很不清楚。但是,经过了时间的沉淀和苦思冥想,我明白了。而我作为一个学习者,过来人,也深知其中难以理解的地方,今天我就给大家介绍链式前向星,力求将大家讲明白。而我也会把理解的难点重点拿出来讲。
介绍
链式前向星,是一种储存图的信息的方法,有着很高的空间利用率和较低的时间复杂度,而且遍历也很简单高效。其实存图的方法不在少数,优秀的也很多,那为什么要讲链式前向星呢?我们拿其他的方法对比就行了,比如最最常用的 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 代表边的权值,这些都好理解。
我们主要讲很让人头疼的地方:
- cnt
- head数组
- 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 中就可以了。
举个例子吧,不然太抽象了。还是这个数据,
看第一条边、第三条边和第五条边。我们看到 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
讲的还有不清楚的地方,可以私信我,慢慢讲~文章来源地址https://www.toymoban.com/news/detail-676289.html
到了这里,关于c++链式前向星的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!