图的存储:链式向前星

点击打开在线编译器,边学边练

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个结点所需要访问的边

同样的我们以这个结构的图为例,链式向前星中需要存储如下内容:

386.png

(例图,并且假设所有边的权值均为1)

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


Edge[0].to2Edge[0].next-1Head[1]0
Edge[1].to3Edge[1].next0
Head[1]1
Edge[2].to4Edge[2].next-1Head[2]2
Edge[3].to5Edge[3].next2Head[2]3
Edge[4].to4Edge[4].next-1Head[3]4
Edge[5].to5Edge[5].next-1Head[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-123
结点2145
结点3-14
结点4-15
结点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. 优势

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

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

 

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


第一章 数据结构入门
第二章 链表
第三章 栈
第四章 队列
第五章 从C语言到C++
第六章 串,数组,矩阵,广义表
第七章 树
第八章 图
第九章 算法—查找
第十章 算法—排序
第十一章 算法&竞赛,思维培养
第十二章 后记