前向星和链式前向星
参考博客：深度理解链式前向星
什么是前向星
前向星是一种特殊的边集数组,我们把边集数组中的每一条边按照起点从小到大排序,如果起点相同就按照终点从小到大排序，并记录下以某个点为起点的所有边在数组中的起始位置和存储长度,那么前向星就构造好了。
用len[i]来记录所有以i为起点的边在数组中的存储长度。
用head[i]记录以i为边集在数组中的第一个存储位置。
样例：
其中边的输入顺序：
1 2
2 3
3 4
1 3
4 1
1 5
4 5
我们对其中的边按照定义排序完后：
编号: 1 2 3 4 5 6 7
起点u: 1 1 1 2 3 4 4
终点v: 2 3 5 3 4 1 5
head[1] = 1，len[1] = 3head[2] = 4，len[2] = 1head[3] = 5，len[3] = 1head[4] = 6，len[4] = 2
那么，前向星存图有什么优势吗？利用前向星，我们可以在O(1)的时间内找到以i为起点的第一条边以O(len[i])的时间找到以i为起点的所有边。前向星特别适合用来优化SPFA、DFS以及BFS。
但是，在这里有一个问题，就是前向星还是需要加上排序的时间，如果是快排大概是O(n*log(n))；而链式前向星则不需要排序也能得到。
链式前向星
我觉得，直接不好理解链式前向星，我们先来看其代码，然后通过其代码来体味其中的道理：
struct NODE{int w;int to;int next; //next[i]表示与第i条边同起点的上一条边的储存位置}edge[MAXN];int cnt = 0;int head[MAXN]; //head初始化为-1void add(int u,int v,int w){edge[cnt].w=w;edge[cnt].to=v; //edge[i]表示第i条边的终点 edge[cnt].next=head[u]; //head[i]表示以i为起点的最后一条边的储存位置 head[u]=cnt++;}
其中：
edge[i].to表示第i条边的终点
edge[i].next表示与第i条边同起点的下一条边的存储位置
edge[i].w为边的权值。
**数组head[]**它是用来表示以i为起点的第一条边存储的位置
注意head[]数组一般初始化为-1
给出代码我们可能还是很难理解，我们用前面那个例子模拟一遍就会有所理解了：
样例：
其中边的输入顺序：
1 2
2 3
3 4
1 3
4 1
1 5
4 5
edge[0].to = 2; edge[0].next = -1; head[1] = 0;
edge[1].to = 3; edge[1].next = -1; head[2] = 1;
edge[2].to = 4; edge[2],next = -1; head[3] = 2;
edge[3].to = 3; edge[3].next = 0; head[1] = 3;
edge[4].to = 1; edge[4].next = -1; head[4] = 4;
edge[5].to = 5; edge[5].next = 3; head[1] = 5;
edge[6].to = 5; edge[6].next = 4; head[4] = 6;
这里我们可以看出来，head[i]保存的是以i为起点的所有边中编号最大的那个，而把这个当作顶点i的第一条起始边的位置。而head[i]中的值，就是代表以i为起点的所有边中编号最大的那条边在edge[]数组中的下标。
我们再来看看怎么遍历：
for(int i=head[u];~i;i=edge[i].next)
比如这里u=1，指的是我们遍历所有以1为起点的边，首先是编号为5的边（edge[5]），其中点是5（edge[5].to = 5），下一个是编号为3的边（edge[5].next = 3）…直到edge[].next = -1。至此就遍历完了所有以1为起点的边。
这会，我们再来回过头看链式前向星的代码就很好理解了：
首先，对于add函数中前两行代码，其目的就是为了保存该条边的权值及其终点。关键在于下面两行代码：在更新head[u]之前我们需要先保存当前的head[u]，然后再更新head的编号（cnt）。
SPFA+链式前向星建图
/******链式前向星建图********/struct NODE{int w;int to;int next; //next[i]表示与第i条边同起点的上一条边的储存位置}edge[MAXN];int cnt = 0;int head[MAXN]; //head初始化为-1void add(int u,int v,int w){edge[cnt].w=w;edge[cnt].to=v; //edge[i]表示第i条边的终点 edge[cnt].next=head[u]; //head[i]表示以i为起点的最后一条边的储存位置 head[u]=cnt++;}/***************/int dis[MAXN];//dis[i]=源点s->i最短路径bool vis[MAXN];//vis[i]表示i是否在队列void spfa(int s){for(int i=1;i<=MAXN;i++)//初始化{dis[i]=INF;vis[i]=true;}dis[s]=0;//源点到自身距离为0queue<int>q;//使用c++自带队列q.push(s);//源点入队vis[s]=false;while(!q.empty())//若队列不为空{int u=q.front();//取出队首元素弹出q.pop();vis[u]=true;for(int i=head[u];~i;i=ed[i].next){int v=ed[i].to;if(dis[u]+ed[i].w<dis[v]){dis[v]=dis[u]+ed[i].w;if(vis[v])//如果终点不在队列{q.push(v);vis[v]=false;}}}}}
