图的存储:链式向前星
1. 概念
链式向前星代码是基于向前星代码的优化，这是极大多数算法竞赛以及高效率图论算法喜欢适用的创建方法，与邻接表和邻接矩阵比较容易的理解方式，向前星算法并不容易理解。
在理解链式向前星之前我们需要了解什么是向前星，前向星是一种特殊的边集数组，我们把边集数组中的每一条边按照起点从小到大排序，如果起点相同就按照终点从小到大排序，并记录下以某个点为起点的所有边在数组中的起始位置和存储长度,那么前向星就构造好了。
链式向前星的本质是利用链表的特性（一个结点指向另一个结点），以达到不需要像向前星那样排序（排序的平均情况需要O(nlogn)的代价）就可以直接搜索到目标，从而达到减少计算机运算时间使用的情况。
2.结构设计
与前文不同，本文我们先展示代码再做具体讲解，链式向前星的结构模板代码如下：
struct Edge{ //表示边
int w;
int to;
int next;
}edge[10005];
int cnt=0; //用以控制并统计边的数量
int head[10005]; //表示来源的边序号
具体的解释为：
a)Edge表示边，这个结构体数组将逐步记录边信息，其中包含有三个元素
l w为权重即边之间的权值，下图中为默认的1，不演示
l to表示为第i条边指向哪一个结点
l edge[i].next表示第i条边的下一条边的序号
b)Cnt表示边的数量，在输入时利用他逐个+1
c)Head表示第x个结点所需要访问的边
同样的我们以这个结构的图为例，链式向前星中需要存储如下内容：
（例图，并且假设所有边的权值均为1）
上图可以得到一个这样的运算表格（不唯一）
| Edge[0].to | 2 | Edge[0].next | -1 | Head[1] | 0 |
| Edge[1].to | 3 | Edge[1].next | 0 | Head[1] | 1 |
| Edge[2].to | 4 | Edge[2].next | -1 | Head[2] | 2 |
| Edge[3].to | 5 | Edge[3].next | 2 | Head[2] | 3 |
| Edge[4].to | 4 | Edge[4].next | -1 | Head[3] | 4 |
| Edge[5].to | 5 | Edge[5].next | -1 | Head[4] | 5 |
可以见的，比如我们访问与1相互联通的所有结点，我们首先访问head[1]的内容，head的下标表示1结点，其内容表示我们应该访问边的标号，此时我们得到了数据1，表明我们需要访问边1，此时我们找到edge[1]并获取第一个to的内容，表示1结点与3结点相连通，接下来访问next的内容，在edge[1].next中获得了下一条边的标号0，因此接下来访问edge[0]的内容，得到了新得信息，edge[0].to=2，表示1结点与2结点相互联通，在访问next的内容为-1时表示没有下一条了，结束向下访问，自此，我们获得了与1相互联通的所有结点的信息。
因此可以得到如下的信息表：
| 结点1 | -1 | 2 | 3 |
| 结点2 | 1 | 4 | 5 |
| 结点3 | -1 | 4 | |
| 结点4 | -1 | 5 | |
| 结点5 | -1 |
添加边信息时使用以下代码
void add_edge(int from, int to, int w) {
edge[cnt].to = to;
edge[cnt].w = w;
edge[cnt].next = head[from];
head[from] = cnt++;
}
注意，我们需要对全体数组进行赋-1的初值，这对于出错和检验错误都是很有帮助的，因为-1正是本算法的判定边界点，当然，这个边界点也可以由自己定位任意一个负数。
3. 优势
链式向前星的有点在于高效，访问速度较快，是图论算法的热门构建方法，这点在算法竞赛中体现尤为重要，缺点也很明显，不易理解和构造麻烦。
链式本身就有访问此结点会自动体现下一节点的效果，因此很适合遍历和访问的算法代码构建，这点在后文会提到。
注：建议初学者多次阅读本章内容
作者：喵哥笔记
