目录
  1. 前向星
  2. 链式前向星
链式前向星【存图模板】

存图方式主要有:邻接矩阵($m[i][j]$为w(w!=0),表示i点到j点有一条w权值的路)、邻接表($m[u][i]$记录的值为v、w,表示u到v点有一个w权值的路)
用邻接矩阵非常浪费空间,有一种效率高且省空间的存图方法叫链式前向星。

前向星

前向星就是一种邻接表。它是一个边集数组,先将起点按从小到大顺序排列,如果相同则按终点从小到大排序,并记录下以某个点为起点的所有边在数组中的起始位置和权值,那么前向星就构造好了。

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

譬如下图:
在这里插入图片描述
可以得到:

0: 1 2
1: 1 3
2: 1 5
3: 2 3
4: 3 4
5: 4 1
6: 4 5

head[1] = 0, len[1] = 3
head[2] = 3, len[2] = 1
head[3] = 4, len[3] = 1
head[4] = 5, len[4] = 2
head[5] = -1, len[5] = 0

因为前向星需要一个排序操作,效率不是很高,而链式前向星可以避免排序。

链式前向星

建立结构体:

1
2
3
4
5
struct edge { 
int v; //终点
int w; //权值
int next; //下一个同起点的边的下标
} e[maxm];

添加边的操作:

1
2
3
4
5
6
7
void add(int u, int v, int w)
{
e[cnt].v = v;
e[cnt].w = w;
e[cnt].next = head[u];
head[u] = cnt++;
}

依然是上面的图,可得到:

e[0]: v = 2, next = 1 head[1] = 0
e[1]: v = 3, next = 2
e[2]: v = 5, next = -1
e[3]: v = 3, next = -1 head[2] = 3
e[4]: v = 4, next = -1 head[3] = 4
e[5]: v = 1, next = 6 head[4] = 5
e[6]: v = 5, next = -1
head[5] = -1

遍历的操作:

1
for(int i=head[u];i!=-1;i = e[i].next)

因为插入边的方法是头插法,所以遍历时的操作是根据读入顺序的逆序来的。

文章作者: Irimsky
文章链接: /2019/10/12/链式前向星【存图模板】/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Irimsky's Blog

评论