边集数组

边集数组是由两个一维数组构成。

一个是存储顶点的信息，另一个是存储边的信息。边数组每个数据元素由一条边的起点下标 (begin)，终点下标 (end) 和权 (weight) 组成。

边集数组关注的是边的集合，对顶点的处理效率较低，例如查找某顶点的度，就需要扫描整个边数组。

链式前向星

链式前向星可用于存储图，本质上是一个静态链表，用边集数组和邻接表相结合，可用快速访问一个顶点所有邻接点。

链式前向星存储包括两种结构：

边数组：edge[] ，edge[i] 表示第 i 条边。
头结点数组：head[]，head[i] 存以 i 为起点的最后一条边的下标（在edge[]中的下标）。

**链式前向星本质上还是邻接表。**

使用链式前向星，储存 N 个顶点的有向有权图，边集数组对应的边数 M 未指定的情况下，要设置比 NN 大的数（无向图需要再 2 ）。

头结点数组 head[a]=i，表示顶点 a 的最后一个邻接边是 edge[i]。

链式前向星的特性:

和邻接表一样，因为采用头插法进行链接，所以边输入顺序不同，创建的链式前向星也不同。
对于无向图，每输入一条边，需要添加两条边，互为反向边。例如，输入第一条边 1 2 5，实际上添加了两条边，如图所示：

如果一条边的下标为 i，则其反向边为 i^1 。

链式前向星具有边集数组和邻接表的功能，属于静态链表，不需要频繁地创建结点，应用十分灵活。

struct Edge{
    int to, w, next;
}edge[M];

int h[N];
int cnt = 0;

void add(int a, int b, int c){
    edge[cnt].to = b;
    edge[cnt].w = c;
    edge[cnt].next = h[a];
    h[a] = cnt++;
}

memset(h, -1, sizeof h);

for(int i = h[x]; ~i; i = edge[i].next){
    int to = edge[i].to;
}