开启成长之旅！这是我参与「日新方案 12 月更文挑战」的第2天，点击检查活动概况
前向星的名字很好听，但它并不是一颗真正星星呀。 它是一种很特别的边集数组，数组里面的边，以起点为下标，依照序号升序来排序。同起点的边，依照结尾升序排序。
构建前向星咱们需求两个数据结构
边数组
这个咱们构建一个结构体
struct edge{
int to,dis,last;
}e[2333];
对于每条边有三个特点
-
to： 边的结尾 -
last： 边的起点衔接的上一条边 -
dis：边的长度
PS：咱们讲过，边调集数组里面的边是依照起点从小到大排序的，而且一个起点或许衔接着许多条边，所以一条边的 last特点便是 起点衔接的上一条结尾序号更小的边
由上图咱们知道，一号点衔接着三个结尾，那么就发生了三条边。这些边的起点都是一号点，因而他们依照结尾升序来排序。另外，每条边的 last特点讲的是该点衔接的上一条结尾序号更小的边，倘若该边便是起点衔接的榜首条边，那么这条边的 last 能够设为-1或者0.（边序号默认从1开端）
| 边序号 | 起点序号 | 结尾序号 | 起点的上一条边序号 |
|---|---|---|---|
| 1 | 1 | 2 | 0 |
| 2 | 1 | 3 | 1 |
| 3 | 1 | 4 | 2 |
咱们通过上面的表格能够发现：起点1的上一条边序号会跟着咱们边的添加进行更新 0==>1==>2 。当边3创建完毕后，咱们点1的最终一条出边便是边3了
上面咱们讲了同一个起点的边调集状况，接下来咱们讲不同起点应该怎么办。
咱们引入第二个数据结构
next数组
其实这个数组存的便是 每个点衔接的最终一条出边的序号
它以 点的序号为下标，该点衔接的最终一条边序号为值。
每当一个点衔接某个点，发生新边后，这个点的next数组就更新为新边的序号
由上图咱们知道， 点1的最终衔接的出边为边3， 点2的最终衔接的出边为边5， 点3的最终衔接的出边为边6 点4的最终衔接的出边为边8， 点5，6，7均无出边。 因而咱们能够把上面图的next数组作出：
| next[1] | 3 |
|---|---|
| next[2] | 5 |
| next[3] | 6 |
| next[4] | 8 |
| next[5] | 0 |
| next[6] | 0 |
| next[7] | 0 |
接下来咱们依照链式前向⭐来构建这张图
图中带黑框的数字是边的长度
咱们再来回忆下 ，咱们构建前向星用了两个结构。
榜首个
然后咱们构建前向星的边还会用到一个加边函数add , 这个便是咱们构建前向星的实质
Add函数
void add(int u,int v,int d){
e[++cnt].to=v;
e[cnt].d=d;
e[cnt].last=next[u];
next[u]=cnt;
}
在上面这个函数中，cnt变量指的便是边的序号，它从1开端 ，每构建一条新边，cnt就添加1.
咱们的next数组的存的是该点衔接的最终一条出边的序号，因而每当某个点构建一条新边时，咱们要更新它的next存的值。至于咱们这条边的last特点，自然便是在构建这条边之前，没有更新的next数组啦。
建图
现在咱们给出的数据方式是这样的：
榜首行给出两个整数n m
接下来m行，每行给出三个整数 u ，v，d 分别代表一条边的起点 ，结尾，长度
数据如下：
5 8
1 2 3
1 3 4
2 3 1
2 4 6
3 4 7
3 5 10
4 3 2
4 5 5
咱们现在按顺序来构建每一条边
| 边序号 | 起点 | 结尾 | 长度 | e[]数组特点 | next[]更新 |
|---|---|---|---|---|---|
| <1> | 1 | 2 | 3 | e[1]:to=2,d=3;last=0 | next[1]:0=>1 |
| <2> | 1 | 3 | 4 | e[2]:to=3,d=4;last=1 | next[1]:1=>2 |
| <3> | 2 | 3 | 1 | e[3]:to=3,d=1;last=0 | next[2]:0=>3 |
| <4> | 2 | 4 | 6 | e[4]:to=4,d=6;last=3 | next[2]:3=>4 |
| <5> | 3 | 4 | 7 | e[5]:to=4,d=7;last=0 | next[3]:0=>5 |
| <6> | 3 | 5 | 10 | e[6]:to=3,d=10;last=5 | next[1]:5=>6 |
| <7> | 4 | 3 | 2 | e[7]:to=3,d=2;last=0 | next[1]:0=>7 |
| <8> | 4 | 5 | 5 | e[8]:to=5,d=5;last=4 | next[1]:4=>8 |
