很久以前看过一遍链式前向星 的存图方法，一知半解。最近几天详细学习了一波，感觉非常有用。所以，那就开始吧。 链式前向星自然是链表的方法。它需要构建3个数组，next[],head[],to[] 所有的数据都在这3个数组里面。 每个边都有一个序号，假设我们存储的是有向图嘛，比如由结点1出发，分别指向4，3，2三个结点。我们先找到head[1],它告诉我们1这个结点怎么找寻它指出的第一个结点，head[1]=1给出了一个索引，告诉在to[]数组的第6个位置记录了1结点指向的4to[6]=4:， 然后，我们通过next[]数组找到1结点指向的第二个结点，next[6]=3，告诉我们要访问to数组的第3个，就能找到1结点指向的3 最后，我们通过next[]数组找到1结点指向的第二个结点，next[3]=0，告诉我们要访问to数组的第0个，就能找到1结点指向的2

1
2
3
4
5

     int u=1;
     for (int i = head[u]; i!=-1; i = nxt[i]) {  
         int v = to[i];
         System.out.println(v);
     }

可以看到head和to数组都记录的是索引，to才记录了指向的结果。 那么，这3个数组是怎么构造的呢？

1
2
3
4
5
6

//head[]和cnt初始化为-1
void add(int u,int v){
    next[++cnt]=head[u];
    head[u]=cnt;
    to[cnt]=v;
}

cnt是索引，head和next是根据遍历的逆过程来构造的，head后于next更新，且head每次用cnt更新，cnt是next数组的索引值，那么我们知道head[u]，就知道next的第几个存储这上一个head[u]（它之后被cnt更新了，但它没有丢失，它被next存起来了），递归向上查找，最后一个是head是-1，由于他被next替代了，所以最后一个找到的结点next的值是-1

为了方便，我们看一个例子

1
2
3
4
5
6
7

add(1,2);// cnt=0 next[0]=-1 head[1]=0 to[0]=2
add(2,4);// cnt=1 next[1]=-1 head[2]=1 to[1]=4
add(3,4);// cnt=2 next[2]=-1 head[3]=2 to[2]=4
add(1,3);// cnt=3 next[3]=0  head[1]=3 to[3]=3
add(4,3);// cnt=4 next[4]=-1 head[4]=4 to[4]=3
add(3,2);// cnt=5 next[5]=2  head[3]=5 to[5]=2
add(1,4);// cnt=6 next[6]=3  head[1]=6 to[6]=4

可以看到，cnt不断增加，一直在前进，因为cnt记录了下标，而to和next每次都更新cnt下标对应的值，head的某个索引值被改写成了cnt。是不是head 的某个索引(也就是起始点)的值恰好是next的索引呢？next的索引到了上一个同样的起始点是那个位置。

不懂？我们看最后一行，1->4结点

add(1,4);// cnt=6 next[6]=3 head[1]=6 to[6]=4

head[1]=6告诉我们next[6]能找到1->x这个结点，x是多少？next[6]=3，我们最想知道的x答案就隐藏在3这个数里，我们看这一行：

add(1,3);// cnt=3 next[3]=0 head[1]=3 to[3]=3，是不是表示1->3啊，通过next[6]=3我们要跳转到第3行（从0数的第三行），因为第三行to[3]记录着x的答案。

想知道以1出发还有没有指向其他结点？看next[3]是几嘛，因为next[3]会告诉我们索引值的。