图的存储：结构设计、链式向前星代码C语言示例

1. 概念文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25205.html

链式向前星代码是基于向前星代码的优化，这是极大多数算法竞赛以及高效率图论算法喜欢适用的创建方法，与邻接表和邻接矩阵比较容易的理解方式，向前星算法并不容易理解。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25205.html

在理解链式向前星之前我们需要了解什么是向前星，前向星是一种特殊的边集数组，我们把边集数组中的每一条边按照起点从小到大排序，如果起点相同就按照终点从小到大排序，并记录下以某个点为起点的所有边在数组中的起始位置和存储长度,那么前向星就构造好了。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25205.html

链式向前星的本质是利用链表的特性（一个结点指向另一个结点），以达到不需要像向前星那样排序（排序的平均情况需要O(nlogn)的代价）就可以直接搜索到目标，从而达到减少计算机运算时间使用的情况。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25205.html

2.结构设计文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25205.html

与前文不同，本文我们先展示代码再做具体讲解，链式向前星的结构模板代码如下：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25205.html

具体的解释为：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25205.html

a)Edge表示边，这个结构体数组将逐步记录边信息，其中包含有三个元素文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25205.html

l  w为权重即边之间的权值，下图中为默认的1，不演示文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25205.html

l  to表示为第i条边指向哪一个结点文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25205.html

l  edge[i].next表示第i条边的下一条边的序号文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25205.html

b)Cnt表示边的数量，在输入时利用他逐个+1文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25205.html

c)Head表示第x个结点所需要访问的边文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25205.html

同样的我们以这个结构的图为例，链式向前星中需要存储如下内容：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25205.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25205.html

（例图，并且假设所有边的权值均为1）文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25205.html

上图可以得到一个这样的运算表格（不唯一）文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25205.html

 文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25205.html

可以见的，比如我们访问与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相互联通的所有结点的信息。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25205.html

因此可以得到如下的信息表：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25205.html

添加边信息时使用以下代码文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25205.html

注意，我们需要对全体数组进行赋-1的初值，这对于出错和检验错误都是很有帮助的，因为-1正是本算法的判定边界点，当然，这个边界点也可以由自己定位任意一个负数。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25205.html

3. 优势文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25205.html

链式向前星的有点在于高效，访问速度较快，是图论算法的热门构建方法，这点在算法竞赛中体现尤为重要，缺点也很明显，不易理解和构造麻烦。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25205.html

链式本身就有访问此结点会自动体现下一节点的效果，因此很适合遍历和访问的算法代码构建，这点在后文会提到。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25205.html

注：建议初学者多次阅读本章内容。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25205.html