链式前向星我学到的时候是用于存图的，但事实上它的用途还是非常广泛的，在其他很多的题目中都会用到。

作为一种工具，它可以模拟链表的功能并且不需要使用指针，因此是链式的，而由于每个根节点直接挂的是最后挂上取的结点，访问时是按挂的结点的逆序访问，昂```比较像尾巴在前面的彗星吧，所以就是前向星啦（雾，吹脑洞各种开```）。

在存图时可以当成邻接表来使用。

 

其基本的原理是使用 head 、 nxt 、 point 、（0个或多个val ） 数组模拟链表：

head 数组的长度是根的个数，其下标就是根的数字，head数组用于记录每个根上最后一个挂载的结点的 size 值；

变量 size 记录的是总结点数，每一个 size 值就是一个结点；

对于每一个结点有 nxt 、point 、以及 val 值，因此这三个数组的下标都是其 size 值，表示当前 size 的结点的不同信息；

nxt 数组记录的是该数组是挂在哪个结点上的，其值就是它的根上所挂的上一个结点的 size 值，因此访问某个结点的 nxt 值就是访问到它之前的一个结点；

point 数组和 val 数组都是记录一些结点的信息的，比如在存图的时候，point 数组就可以记录和根相连的点，而 val 可以记录其边权。

 

创建和访问：

创建时初始化只要将 size 定为 0 ，head 数组全部赋值为 -1 即可，每加入一个结点，先记录该结点的 point 、 val 等信息，再记录下 nxt 信息，最后将 head 值改变，size ++ ；

访问某个根 a 时首先访问 size 值等于 head [ a ] 的结点，即最后一个挂载上去的结点，然后依次访问 size 等于当前结点 nxt 值的结点，直到访问到 i 等于 -1 为止；

 

1 //添加结点： 2 void add(int a,int b,int v){ 3     for(int i=head[a];~i;i=nxt[i]){    //这个循环是判断重复的，比如存图时的重边 4         if(point[i]==b){ 5             if(val[i]>v)val[i]=v; 6             return; 7         } 8     } 9     val[size]=v;    //首先记录下结点的 val 和 point 信息10     point[size]=b;11     nxt[size]=head[a];    //将该结点的 next 指向之前这个根挂载的最后一个结点的 size 值12     head[a]=size++;    //将该结点的根的 head 值指向当前结点的 size （即最后一个挂上去的结点的 size 值），并将 size ++ 用于下一个结点。13 }14 15 //访问结点：这里就是访问根 a 下挂的所有结点，从最后一个挂的结点一直访问到第一个挂的结点，这里的 i 就是该结点的 size 值。16 for(int i=head[a];~i;i=nxt[i]){17 18 }