前向星

什么是前向星？
一种数据结构，以储存边的方式来存储图。构造方法如下：读入每条边的信息，将边存放在数组中，把数组中的边按照起点顺序排序(可以使用基数排序，如下面例程)，前向星就构造完了。通常用在点的数目太多，或两点之间有多条弧的时候。一般在别的数据结构不能使用的时候才考虑用前向星。除了不能直接用起点终点定位以外，前向星几乎是完美的

int m,cnt=0,head[MAXN];
//另外还有一个数组head[],它是用来表示以i为起点的第一条边存储的位置,实际上你会发现这里的第一条边存储的位置其实
//在以i为起点的所有边的最后输入的那个编号

struct edge{
    int to;//其中edge[i].to表示第i条边的终点
    int nxt;//edge[i].next表示与第i条边同起点的下一条边的存储位置
    int dis;//edge[i].dis为边权值
}e[MAXE];

void add(int u,int v,int dis){//加边
    e[cnt].dis=dis;
    e[cnt].to=v;
    e[cnt].nxt=head[u];
    head[u]=cnt++;
}