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

关于前向星的资料可以访问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])

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

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