链式前向星是一种时空复杂度都比较优秀, 适合存各种图的储存方式。
阅读本算法笔记需要一定的图论基础
算法详解
假设: 某个图中有N个点, M条边.
A. 边的储存
设一条有向边edge的两端点为u和v, 则我们可以用以下结构体来存储他:
struct EDGE{
int u, v;
};那么, 我们只需要一个EDGE的数组, 即可储存该图的所有边, 且每条边都有自己的编号.
但是直接这样存肯定是不行的, 因为无法快速的找到与某一点相连的边: 全部扫一遍的时间复杂度是O(M), 太高了.
那么, 很容易就能想到, 我们可以使用N个动态数组作为索引, 对于第i个动态数组, 存储所有与第i点相连的边的编号, 即上文中EDGE数组的编号.
vector<int> p[N];但是很明显, 太费空间了, 会MLE的.
因此, 我们可以选用链表的形式来储存这个索引.
对于结构体EDGE, 我们增加一个变量next, 来储存下一条与u点相连的边的编号, 则我们遍历与u点相连的边时, 可以用当前边的next来快速获取下一条与u点相连的边的编号.
struct EDGE{
int u, v, next;
} E[M];那么, 我们该怎么知道与u点相连的第一条边的编号呢? 只要找到了第一条, 便找到了拉链的最上端, 可以一口气遍历所有与u相连的边.
和next的原理一样, 我们再开一个p[N]数组来存储第一条边的索引, 即对于p[u], 表示与u相连的第一条边的编号.
int p[N];B. 边的插入
知道了以什么格式存储, 现在来考虑改如何存.
我们创建一个insert(u, v)函数, 表示插入一条由u到v的单向边; 创建一个eid变量, 表示当前插入到第i条边, 显然的:
int eid = 0;
void insert(int u, int v){
E[eid].u = u;
E[eid].v = v;
}现在来考虑如何存这个next链表.
p[u]存储的是u的第一条边, 每当我们增加一条边时, 我们便把他作为新的第一条边, 原先的第一条边变为第二条边, 以此类推. 同时, next储存的是下一条边, 即第一条储存第二条, 第二条储存第三条等等...
则, 插入新边时, 原先的p[u]存储的是当前边的下一条边的编号, 我们只需要另当前新边的next = p[u], 就表示了当前新边的下一条边是原先的第一条边. 同时, 由于第一条边更新了, 所以我们需要更新p[u]为当前新边的编号.
int eid = 0;
void insert(int u, int v){
E[eid].u = u;
E[eid].v = v;
E[eid].next = p[u];
p[u] = eid ++;
}这样一条新边就插入成功了.
但是, 还有一个重要的问题, 遍历边时, 我们需要让程序知道当前遍历到最后一条了, 否则就会死循环.
因此, 我们令最后一条边的next为-1, 当遍历到next为-1时我们便停止遍历.
由于我们输入边的顺序和遍历边的顺序是相反的, 所以只要令每个点第一条插入的边的next为-1即可, 即我们令p[N]的初始值为-1即可.
void init(){
eid = 0;
memset(p, -1, sizeof(p))
}同理, 对于双向边, 执行两遍就好了: insert(u, v); insert(v, u);
来看一个单向边图的例子:
比如3号点, 我们就会从4号边开始遍历, 发现next数组不为-1, 那么继续向后, 来到1号点, 此时next数组为-1, 结束遍历.
这个是这张图的p[u]数组.
C. 边的遍历
读懂了上面的算法, 遍历就不是问题了, 我们只要从编号i = p[u]开始, 每次的下一条边是i = p[i].next即可, 当i == -1时表示结束, 跳出即可.
for(int i = p[u]; i = p[i].next; i != -1){
// do sth.......
}板子
const int MAXN = 1e3 + 10;
const int MAXM = 1e5 + 10;
struct EDGE{
int u, v, next;
} E[MAXM];
int eid, p[MAXN];
void init(){
eid = 0;
memset(p, -1, sizeof(p));
}
void insert(int u, int v){
E[eid].u = u;
E[eid].v = v;
E[eid].next = p[u];
p[u] = eid ++;
}
void insert2(int u, int v){
insert(u, v);
insert(v, u);
}
其他性质
对于无向图, 我们需要插入两次, 由于这两次插入的编号是相邻的, 所以当初始边的编号为0(偶数)时, 我们可以用i ^ 1快速获取到第i条边的反向边.