前向星和链式前向星

前向星

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

前向星不需要像邻接表那样用指针指向下一条边，还是挺方便的。但是，由于前向星初始化需要快排一遍，相对邻接表要慢许多。考虑到一般图论题点数都不会很大，所以可以改为采用基数排序的思想对前向星进行排序。

一开始读入时，先算出每个点出去的边有多少条，然后计算出排序后每个点出去的第一条边位置应在哪里，最后把全部边扫一遍放到排序后应在的位置就好了。

这样排序的话初始化的时间复杂度就降到了O(m)，总体时间并不会逊色于邻接表。 ——百度百科

前向星是一种特殊的边集数组，我们把边集数组中的每一条边按照起点从小到大排序，如果起点相同就按照终点从小到大排序，并记录下以某个点为起点的所有边在数组中的起始位置和存储长度，那么前向星就构造好了。

通常，用 len[i] 来记录所有以 i 为起点的边在数组中的存储长度，用 head[i] 记录以 i 为边集在数组中的第一个存储位置。

链式前向星

用链式前向星，可以避免排序。

一篇比较详细的博客：

https://blog.csdn.net/acdreamers/article/details/16902023

代码实现如下：

//edge[i].v表示第i条边的终点，edge[i].next表示与第i条边同起点的下一条边的位置，edge[i].w为边权值
//数组head表示以i为起点的第一条边存储的位置，一般初始化为-1
//你会发现head表示的以i为起点的第一条边存储的位置，实际上是在以i为起点的所有边的最后输入的那个编号(因为cnt已经加过1了)
struct node{
    int v;
    int w;
    int next;
}edge[100001];
int cnt, head[100001];
void addEdge(int x, int y, int w){
    cnt++;
    edge[cnt].v = y;
    edge[cnt].w = w;
    edge[cnt].next = head[x];
    head[x] = cnt;
}