图的存储:链式向前星

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）

上图可以得到一个这样的运算表格（不唯一）

可以见的，比如我们访问与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相互联通的所有结点的信息。

因此可以得到如下的信息表：

添加边信息时使用以下代码

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. 优势

链式向前星的有点在于高效，访问速度较快，是图论算法的热门构建方法，这点在算法竞赛中体现尤为重要，缺点也很明显，不易理解和构造麻烦。

链式本身就有访问此结点会自动体现下一节点的效果，因此很适合遍历和访问的算法代码构建，这点在后文会提到。

注：建议初学者多次阅读本章内容