前向星(Forward Star)

一、简介

        前向星是以储存边的方式来存储图的数据结构。

        构造方法如下：读入每条边的信息，将边存放在数组中，把数组中的边按照起点顺序排序(可以使用基数排序，如下面例程)，前向星就构造完了。通常用在点的数目太多，或两点之间有多条弧的时候。一般在别的数据结构不能使用的时候才考虑用前向星。

        除了不能直接用起点终点定位以外，前向星几乎是完美的。

       前向星的时间复杂度为O(m)，m为边数。总体时间并不会逊色于邻接表。

二、代码

        其中A[i].to表示第i条边的终点，A[i].next表示与第i条边同起点的下一条边的存储位置，A[i].v为边权值。
        另外还有一个数组a[]，它是用来表示以i为起点的第一条边存储的位置，实际上你会发现这里的第一条边存储的位置其实在以i为起点的所有边的最后输入的那个编号。

#include 
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

2 1 30

2 3 20

4 2 30

4 3 20

        按照输入信息模拟一下：

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，所以就退出了，这样就遍历完成了