简介
是邻接表的静态实现。它的优点是节省了分配内存的时间，效率更高。
链式前向星的构成由一个结构体（包括目标点、边权值和下一个同起点的边）和 head 数组（用于存放某点的第一条出边）。链式前向星每添加一条边就会更新 head 数组，使得 head 数组存放的总是最新添加的某点的出边，此出边的 next 总指向 head 数组之前存放的出边的序号。
比喻
nxt：以本点为前驱点的下一条边的数组地址。
len：边权。
end：后继点。
cnt：计数，已加入多少边。
一些猴子们要放学回家，找妈妈。但猴子太多了，怎么办？
假设有 3 个家长，I，II，III。他们就挖三口井（head[4]）：
I II III
- - - - - -
来了一个 3 班的猴子，他妈妈叫 I。他先在身上（end）写上 3，手上写 0（nxt=0）。
来到 I 号井前，用轱辘上的绳子把自己放下去，在尾巴上挂一个牌 1号（head[1]=1，cnt++），即加入了第一条边：1-->3。
I II III
- - - - - -
1
| //把猴子身体长度当作len吧。。。
*_*3
|
W
0
又来了一个2班的猴子，他妈妈也叫 I。它在身上（end）写上 3，他就把 1 号猴的尾巴拉住，把自己向下放，手上写 1，即手里猴子的编号（nxt=1），在尾巴上挂一个牌 2号（head[1]=2，cnt++）。即加入第二条边：1-->2。
I II III
- - - - - -
2
|
*_*3
|
W
1
|
*_*2
|
W
那么，以下发生了什么？
I II III
- - - - - -
2 3
| |
*_*3 *_*1
| |
W W
1 0
|
*_*2
|
W
0
这是加入了前驱为 2 号节点，后继为 1 的第三条边：2-->1。
要是妈妈接孩子怎么办？把对应的井上的猴子提出来！
模板
建立
struct Graph
{
struct edge{int nxt,to,len;}e[M*2];
int head[N],cnt;
Graph(){memset(head,0,sizeof(head));cnt=0;}
void add(int a,int b,int c){e[++cnt]=(edge){head[a],b,c};head[a]=cnt;}
}G;
其中 add 是指连一条从 x 到 y 边权为 len 的边。
遍历
for(int i=G.head[...];i;i=G.e[i].nxt)
//do something...
本文作者：Yurchiu
本文链接：https://yz-hs.github.io/9429e4495977/
版权声明：本博客中所有原创文章除特别声明外，均允许规范转载，转载请注明出处。所有非原创文章，按照原作者要求转载。
