链式向前星代码是基于向前星代码的优化,这是极大多数算法竞赛以及高效率图论算法喜欢适用的创建方法,与邻接表和邻接矩阵比较容易的理解方式,向前星算法并不容易理解。
在理解链式向前星之前我们需要了解什么是向前星,前向星是一种特殊的边集数组,我们把边集数组中的每一条边按照起点从小到大排序,如果起点相同就按照终点从小到大排序,并记录下以某个点为起点的所有边在数组中的起始位置和存储长度,那么前向星就构造好了。
链式向前星的本质是利用链表的特性(一个结点指向另一个结点),以达到不需要像向前星那样排序(排序的平均情况需要O(nlogn)的代价)就可以直接搜索到目标,从而达到减少计算机运算时间使用的情况。
与前文不同,本文我们先展示代码再做具体讲解,链式向前星的结构模板代码如下:
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正是本算法的判定边界点,当然,这个边界点也可以由自己定位任意一个负数。
链式向前星的有点在于高效,访问速度较快,是图论算法的热门构建方法,这点在算法竞赛中体现尤为重要,缺点也很明显,不易理解和构造麻烦。
链式本身就有访问此结点会自动体现下一节点的效果,因此很适合遍历和访问的算法代码构建,这点在后文会提到。
注:建议初学者多次阅读本章内容
本文固定URL:https://www.dotcpp.com/course/147
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:
一点编程也不会写的:零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码?手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程