链式前向星
历史故事
* 在算竞的远古时代，那时的STLSTLSTL容器还是个蒟蒻的时候，邻接表（指的不是vector邻接表）是当时世界上效率最高但是不好写的存储图的数据结构，但一些特别边台的题目会存在卡内存导致无法AC的情况。
* 这个时候以为伪人站出来了，TATATA就是链式前向星。如果说邻接表效率高但会被卡，邻接矩阵好写但效率低的情况下前向星就是一个相对于邻接表和邻接矩阵来说比较中性的数据结构。但一开始前向星也是个蒟蒻，效率并不高，而在别申必人优化成链式前向星后，效率就得到了加大的提升。
浅谈链式前向星
在介绍链式前向星之前，我们来看看图
如果用邻接表来存储我们会得到这个表格
点 第一个与其相连的点 第二个与其相连的点 第三个与其相连的点 第四个与其相连的点 1 3 4 5 NULL（无） 2 5 4 NULL（无） 3 NULL（无） 4 5 NULL（无） 5 NULL（无）
链式前向星存储图的方式和邻接表很像，也是以一种链表的形式存储的，但邻接表存储的是点，而链式前向星存储的是边。
例如：存点111是就会存储1,2,6{ 1,2,6 }1,2,6这几条边（如图）
那就会得到这张表
点 第一条相连的边 第二条相连的边 第三条相连的边 第四条相连的边 1 1 2 6 NULL（无） 2 3 4 NULL（无） 3 NULL（无） 4 5 NULL（无） 5 NULL（无）
链式前向星有一个head[]head[]head[]数组，其作用是存储以该节点作为起点的所有边。
具体来讲，就是把从每个节点 uuu 出发的边用链表链起来，这样只要记录 head[u]head[u]head[u]表示节点 uuu 边表的第一条边是谁就可以了。
即下表
点 第一条相连的边 第二条相连的边 第三条相连的边 第四条相连的边 u head[u] next[head[u]] next[next[head[u]]] next[next[next[head[u]]]]
如果没有相连的边就写NULLNULLNULL，通常写一个取不到的数，如：−1145141919810-1145141919810−1145141919810？
具体实现
1. 首先我们要有一个边的结构体，因为我们存储的是边，所以我们要有：
* 记录这条边指向的点togotogotogo
* 边表中下一条边的编号
* 这条边的权值 www(最后一个看题目)
2. 然后我们要有一个添加边的函数
cntcntcnt是用来给边编号的
3. 在有了一个如此优秀的加边函数后，我们就可以轻松的读入边了
4. 点邻边的遍历
在图被建立好后，我们只需要读取每个节点 uuu 的head[u]head[u]head[u]，即从节点uuu 出发的第一条边，之后循环查找下一条边，直到遇到NULLNULLNULL
5. 组合一下
DFS 遍历图
遍历图就是需要记录每个点在当前递归中是否被走过。
DFS遍历树
我们只需要在遍历点的邻边的基础上加上dfsdfsdfs即可，函数中 uuu 为当前节点编号，fafafa 为父节点编号。无向图记得要需要判断下一个节点是否不为父节点。
链式前向星与邻接表对比
在了解了链式前向星以后，我们需要了解我们为什么要用它（而不是使用邻接表）。
网上很多资料都有做过比较，比如说这样的：
> 邻接表是用链表实现的，可以动态的增加边，
> 而链式前向星是用结构体数组实现的，是静态的，需要一开始知道数据范围，开好数组大小。
> 相比之下，邻接表灵活，链式前向星好写。
据大佬@LeeCarry说：vectorvectorvector邻接表与链式前向星有内存性能上的差异，因为vectorvectorvector扩充时是默认多申请2倍空间，所以一些特别变态的题目可能会卡内存只能用链式前向星写。他表示最近看STLSTLSTL源码剖析，vectorvectorvector每次扩充都要复制一遍元素到新内存块，肯定会慢很多的。
虽然前向星现在已经少有人用，但vector邻接表不论是在内存上还是在速度上都是略逊于链式前向星写法的，写法实现上也并没有简洁多少，所以能采用链式前向星的时候（即知道边数时）还是采用链式前向星写法吧。（bushi
666goose不要再蛊惑别人
