参考的博客：
链式前向星（加快图的搜索）
链式前向星,它是一种在时间和空间上最优的存图结构。无论是建图还是遍历图效率最高的存图的方式。
链式前向星的结构定义如下：

struct node{
    int to,next;
}edge[maxn];

链式前向星以边为单位进行储存。其中，成员to表示这条边的终点，而next就比较重要了，表示跟本条边的起点相同的前一条边，在edge数组中的下标，如果这条边的起点是第一次出现的，则置为0。也就是说，链式前向星的next属性，像链表一样，将图中起点相同的边连在了一起。例如下面这个图：

我们输入边的顺序为：
1 2
2 3
3 4
4 5
1 3
1 5
4 1

那么我们得到的edge数组为：

当我们想要得到一条边的终点时，就调用edge[i].to，当我们想得到这个起点连接的其他边时，就可以调用edge[i].next。那么现在的问题就是如何快速求next属性。

解决方法就是再定义一个数组head，head[i]表示最近一次输入的以i为起点的边在edge数组中的下标。

用链式前向星建图的整个过程并不复杂，下面来看建图的函数：

struct node
{
    int to;
    int next;
}edge[maxn];
int head[maxn];
int cnt=1;//表示edge数组的下标，也可以表示已经存入的边数
void add(int from,int t)
{
    edge[cnt].to=t;
    edge[cnt].next=head[from];
    head[from]=cnt++;
}

链式前向星遍历图的核心代码是：

for(int i=head[x];i!=0;i=edge[i].next)

在对某一点所连接的所有边的遍历过程中，调用edge[i].next，就像链表一样，将所有起点相同的边都串在了一起。而且，最先输入的边会最晚遍历到，这是由next的属性所造成的。

最开始觉得链式前向星很难，就是因为那个next和head太绕了。这里列出来一次存储的过程还是很舒服得。

赏