链式前向星，顾名思义，就是把链表和前向星的特点结合起来的产物：前向星需要排序，而链式前向星省去了这一步。

关于前向星的资料可以访问Acdreamer博客，http://blog.csdn.net/acdreamers/article/details/16902023

链式前向星相比于前向星，把len[i](以i为起点的边在边集数组中的存储长度)数组用next[i](以i为起点的边下一条边的存储位置)替代掉了，那么建立这个数据结构的基本组成如下：

int head[MAXN];//以i为起点的边在边集数组中的第一个存储位置；

int to[MAXN];//第i条边的终点(即 i -> to[i])；

int w[MAXN];//第i条边的权值；

int next[MAXN];//与第i条边同起点的下一条边的存储位置；

int cnt = 0;//边的数目

当然你可以把 to, w, next整合在一个struct中，这里不再赘述了。

那么怎么插边呢？首先我们要进行初始化，把head和next数组初始化为-1，分别表示没有以i为起点的边和第i条边是最后的一条边（也就是除了前面经过的边，再也没有与他同起点的边了）。

插边的话，首先，我们把权值还有终点存放在相应的数组里面，然后就是如何寻边的问题了。

我们说过，head数组的作用是记录以i为起点的边在边集数组中的第一个存储位置，而我们是一边输入一边插边的，那么，我们可以把当前起点的head数组更新为：

head[u] = cnt;

然后在这一步之前，把next[cnt] = head[u]就行了。

为什么要这样做呢？其实，这样实际上是让上一条同起点的边作为当前的head值，然后直到下面没有相同起点的边为止，一直都让下面的边继承上一级的“第一个”存储位置，也就是head[u]。

可能会有点晕，我们来看数据。

对于下图

我们输入边的顺序为:

1 2

2 3

3 4

1 3

4 1

1 5

4 5

首先，head[MAXN] = {-1}, next[MAXN] = {-1}(其实这个可以不用初始化的，保险起见)

cnt = 0

然后插入边（假设每条边的权值都为一）

那么对于第一条边操作如下;

1. 让w[cnt] = 1, to[cnt] = 2;
2. 让next[cnt] = head[u] (此时head[u]也就是head[1] = -1，所以next[cnt]也就是next[0] = -1，也就是除了前面经过的边，再也没有与他同起点的边了)
3. 让head[u] = cnt（此时head[1]是0，以1为起点的边在边集数组中的第一个存储位置是0）
4. cnt++;（当然可以整合在上一句，我只是为了让条理更清晰一点..）

第二、三条省略。。。

第四条操作如下；

1. 让w[cnt] = 1, to[cnt] = 3;
2. 让next[cnt] = head[u] (此时head[u]也就是head[1] = 0，所以next[cnt]也就是next[3] = 0！！继承了上次的head，成功指向了下一条边！)
3. 让head[u] = cnt++（此时head[1]是3，以1为起点的边在边集数组中的第一个存储位置是3）

其余的边数如此类推~真是好神奇的数据结构呢..

那么要怎么遍历呢？遍历以u为起点的边代码如下；

for (int i = head[u]; i != -1; i = next[i])

是跟输入顺序逆序遍历的，不过这样并不影响结果。

我也是刚学习的..来整理一下，有纰漏之处还请指出。