图的存储¶
链式前向星¶
如果说邻接表是不好写但效率好，邻接矩阵是好写但效率低的话，前向星就是一个相对中庸的数据结构。前向星固然好写，但效率并不高。而在优化为链式前向星后，效率也得到了较大的提升。
本质上是用链表实现的邻接表
实现¶
数据结构¶
- 头结点数组：
head[]，head[i]存以i为起点的第一条边的下标(在edge[]中的下标) - 边集数组：
edge[ ]，edge[i]表示第i条边；
struct node{
int to, nxt, w;
}edge[MAXN];
int head[MAXN]; // 一般初始值为-1
加边¶
void add_edge(int u, int v, int w){
edge[cnt].to = v; // 当前边的终点
edge[cnt].w = w; // 当前边的权重
edge[cnt].nxt = head[u]; // 当前边的下一条边
head[u] = cnt++; // 更新u结点的第一条边
}
遍历¶
for(int i = 1; i <= n; i++){ // 遍历起点
for(int j = head[i]; j != -1; j = edge[j].nxt){ // 遍历边
cout << i << " " << edge[j].to << " " << edge[j].w << endl;
}
}
案例¶
对于下面的数据，第一行5个顶点，7条边。接下来是边的起点，终点和权值
5 7
1 2 1
2 3 2
3 4 3
1 3 4
4 1 5
1 5 6
4 5 7
链式前向星存的是以【1，n】为起点的边的集合，对于上面的数据输出就是：
1 //以1为起点的边的集合
1 5 6
1 3 4
1 2 1
2 //以2为起点的边的集合
2 3 2
3 //以3为起点的边的集合
3 4 3
4 //以4为起点的边的集合
4 5 7
4 1 5
5 //以5为起点的边不存在
复杂度¶
查询是否存在\(u\)到\(v\)的边：\(O(d^+(u))\)
遍历点\(u\)的所有出边：\(O(d^+(u))\)
遍历整张图：\(O(n+m)\)
空间复杂度：\(O(m)\)
应用¶
存各种图都很适合，但不能快速查询一条边是否存在，也不能方便地对一个点的出边进行排序。
优点是边是带编号的，有时会非常有用，而且如果 cnt 的初始值为奇数，存双向边时 i ^ 1 即是 i的反边（常用于 网络流）。