链式前向星(详细解)到)传送门
先看看什么是前方星吧。
正向星形是一种特殊的边集数组，它按起点从小到大的顺序对边集数组中的每条边进行排序，如果起点相同，则按终点从小到大的顺序进行排序。
然后，记录以某一点为起点的所有边的排列中的开始位置和存储长度，就构建了前方星。
使用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]=3
head[2]=4 len[2]=1
head[3]=5 len[3]=1
head[4]=6 len[4]=2
但是，利用正向星的话有排序操作，在高速排序的情况下至少是o(nlog ) ) n ) )
使用链式前向星，可以避免排序。
使边缘结构体为：
结构边缘
{
下一步；
int to；
int w；
(；
其中，edge[i].to表示第I条边的终点，edge[i].next表示与第I条边相同起点的下一边的存储位置，edge[i].w是边权值。
另一个数组head[]用于表示存储以I为起点的第一边的位置。 实际上，这里的第一边的存储位置实际上是
在以I为起点的所有边的最后输入的编号。
head[]数组通常初始化为-1，对于带边的add函数是这样的：
voidadd(intu，int v，int w ) { edge[cnt].w=w； edge[cnt].to=v； edge[cnt].next=head[u]； head[u]=cnt； 初始化cnt=0。 因此，现在仍用上图和输入来模拟：
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的最初开始边的位置。
这样，在遍历时反而进行遍历，也就是说与输入顺序相反，但这不影响结果的正确性。
例如，在上图中，以节点1为起点的边有3条，各自的编号为0、3、5，head[1]=5
当我们扫描所有以u节点为起始位置的边时，就是这样的：
for(intI=head[u]； ~i； i=edge[i].next )
首先遍历编号为5的边，即head[1]，然后遍历edge[5].next，即编号为3的边，然后继续遍历edge[3].next
在编号0的边上，可以看到是逆序的。