链式前向星

链式前向星是一种以存边的方式储存图的数据结构,经常在各种竞赛中使用。

链式前向星储存的每个边由三个变量储存:totovvnxtnxt

其中,fromfromtoto代表这条边连接的两个点,vv代表这条边的权值,nxtnxt代表同一个fromfrom的下一条边

我们一般用一个headhead数组来储存每个点的最后输入的一条边的编号,每次添加新的边时将这个编号赋给这个边,然后再使用这个边的编号来更新headhead。通过这个编号我们就可以通过每个边的nxtnxt来找到下一条边。

假如我们存储这样的一个图:

一个有五条边四个点的有向图

那么它在链式前向星中可以表示为:

一个链式前向星的结构图

我们可以写一个add函数来帮助我们添加边

1
2
3
4
5
6
7
8
9
void add(const gg &from,const gg &to,const gg &v)
{
cnt++; //边的计数++
edge[cnt].to=to;
edge[cnt].v=v;
edge[cnt].nxt=head[from];
head[from]=cnt;
return;
}

对于链式前向星,我们经常使用这样的for循环来枚举边

1
2
3
4
for(gg i=head[n];i;i=edge[i].nxt) //n为from边
{
//此处添加枚举代码,i为边在edge数组中的编号
}