一、简介
前向星是以储存边的方式来存储图的数据结构。
构造方法如下：读入每条边的信息，将边存放在数组中，把数组中的边按照起点顺序排序(可以使用基数排序，如下面例程)，前向星就构造完了。通常用在点的数目太多，或两点之间有多条弧的时候。一般在别的数据结构不能使用的时候才考虑用前向星。
除了不能直接用起点终点定位以外，前向星几乎是完美的。
前向星的时间复杂度为O(m)，m为边数。总体时间并不会逊色于邻接表。
二、代码
其中A[i].to表示第i条边的终点，A[i].next表示与第i条边同起点的下一条边的存储位置，A[i].v为边权值。
另外还有一个数组a[]，它是用来表示以i为起点的第一条边存储的位置，实际上你会发现这里的第一条边存储的位置其实在以i为起点的所有边的最后输入的那个编号。
#include <bits/stdc++.h>
using namespace std;
struct Node
{int v, next;
}A[100001];
int a[100001],k=0;
inline void insert(int i, int j)
{k++;A[k].v=j;A[k].next=a[i];a[i]=eid;
}
以上图为例，输入：
1 3 30
按照输入信息模拟一下：
A[0].v=3; A[0].next=-1; head[1]=0;
A[1].v=1; A[1].next=-1; head[2]=1;
A[2].v=3; A[2].next=1; head[2]=2;
A[3].v=2; A[3].next=-1; head[4]=3;
A[4].v=3; A[4].next=3; head[4]=4;
head[i]保存的是以i为起点的所有边中编号最大的那个，而把这个当作顶点i的第一条起始边的位置。这样在遍历时是倒着遍历的,也就是说与输入顺序是相反的,不过这样不影响结果的正确性。
比如以上图为例,以节点2为起点的边有2条,它们的编号分别是1,2 而head[2]=2，我们在遍历以u节点为起始位置的所有边的时候是这样的:
for(int i=head[u] ; i!=-1; i=A[i].next)那么就是说先遍历编号为2的边,也就是head[2],然后就是A[2].next,也就是编号1的边。然后因为A[1],next==-1，所以就退出了，这样就遍历完成了
