前向星和链式前向星

前向星

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

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

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

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

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

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

链式前向星

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

一篇比较详细的博客:

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

代码实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//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;
}