「链式前向星」笔记

链式前向星

链式前向星是前向星的链表优化版，作为一种存图的方式，相较于$n^2$的邻接矩阵，它记录每条边的信息，在稀疏图中有更优秀的时空复杂度。

原理

对于每一条边，我们需要知道它从哪来，到哪去，有多长这三个信息。

模拟链表：我们用$head_i$表示以从结点i出发的最后一条边。而对于每一条从结点$i$出发的边，用$next$记录它的前一条边。从而形成$n$条链表，分别为从每一结点出发的边集。

实现

1.我们需要做以下定义：

1 int haed[MAXN]；//链表头
2 int cnt;//计数
3 struct Edge {
4     int to;//到达点
5     int val;//边权
6     int next;//前一条边
7 }edge[MAXN<<1];

 2.加边（链式前向星存的是有向边，特殊的，对于无向边需要加两次）

1 void add(int from,int to) {//加from到to的边
2     edge[++cnt].to=to;
3     edge[cnt].next=head[from];
4     head[from]=cnt;
5  }

3.遍历从结点$x$出发的边

1 for(int i=head[x];edge[i].next!=0;i=edge[i].next) {
2     //edge[i]
3 }

模拟样例（注意对照代码）

对于这张图，边权都为$1$

n=6,m=6
1 3
1 2
1 4
2 5
4 3
5 6

$add(1,3);$  开一个新的edge，to=3;  next指向head[1]为空;  head[1]跳过去。

$add(1,2);$  同上，开个edge，to=2;  next指向head[1];  head[1]跳过去。

$add(1,4);$  一样

$add(2,5); $  加入从$2$出发的边集链表

「链式前向星」笔记

原文：https://www.cnblogs.com/JHTBlog/p/11222840.html