链式前向星图存储优化
1.前向星存储
前向星是一种特殊的边集数组,我们把边集数组中的每一条边按照起点从小到大排序,如果起点相同就按照终点从小到大排序,
并记录下以某个点为起点的所有边在数组中的起始位置和存储长度,那么前向星就构造好了.
比如有起点终点和权值为以下的边：
1 2 1 // 1->2 权值为1
2 3 2
3 4 3
1 3 4
4 1 5
1 5 6
4 5 7
重新排列以后就为：
1 2 1
1 3 4
1 5 6 // 以1为开头的集合
2 3 2 // 以2为开头的集合
3 4 3 // 以3为开头的集合
4 1 5
4 5 7 // 以4为开头的集合
由于排序需要nlogn时间，有些慢，可以优化为不需要排序的链式前向星
2.链式前向星
不排序我们就要对顺序做一个记录 ：
开辟一个last数组来保存以 i 开头集合最后一个元素的下标idx
举个例子 ：
1 2 1 // 1->2 权值为1 ，下标为1
2 3 2 // 下标为2
3 4 3 // 下标为3
1 3 4 // 4
4 1 5 // 5
1 5 6 // 6
4 5 7 // 7
上叙边中，以 1 开头集合最后一个边的下标为 6 (1 5 6 ) ,last[1] = 6;
为了便于后续遍历，last数组初始值赋值为-1
然后在边的存储设计中（结构体构造中），还需要加一个pr变量表示该元素的上一个元素的下标idx
举个例子，还是上叙边，边（1 3 4) 的 pr 就为 1 （1 2 1）
而由于last数组的存在，pr的值其实就是现在last[f]中的值（加入一个新元素此时该新元素就是集合最后一个，last[f]就为对应下标）
** 当然第一个元素的pr就为last[]中的初始值-1，表示为一个元素 **
版权声明：本文为yyghw原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。