链式前向星可以作为 vector 的优化。

vector 变长是直接把空间乘 2（例如里面有 17 个元素，那么大小是 32），会浪费大量空间，且推入的时间较大，数据多的时候会占用很多时间，所以有了链式前向星。

链式前向星是用数组存链表，数组存的是一个链表的结尾的位置；链表节点的指针域存的是该节点的前一个节点。

下面拿有向有权图举例。

vector：

u：起始节点 v：目标节点 w：边权
 u    v w
---  -----
|1|--|2|3|
---  ----- -----
|2|--|3|2|-|1|1|
---  ----- -----
|3|--|1|3|
---  -----

链式前向星：

u：起始节点 v：目标节点 w：边权
i：节点编号 prev：前一个节点的位置（i）
 u    i v w prev
---  ------------
|1|--|1|2|3|NULL|
---  --------- ------------
|2|--|3|1|1|3|-|2|3|2|NULL|
---  --------- ------------
|3|--|4|1|3|NULL|
---  ------------

模板

// 链式前向星
struct edge{
	int u,v,w,prev;
}edges[M];
int tail[N],tot;
void add_edge(int u,int v,int w){
	edges[++tot] = {u,v,w,tail[u]};
	tail[u] = tot;
}

$N$：节点个数；$M$：边个数