一种高效的存图方式——数组前向星

发表于 分类于

此数据结构的正确名字为前向星，为了与链式前向星区别，本文中将其称为数组前向星。

数组前向星是一个特殊的边集数组。将边按照起点排序，那么每个点的所有出边都存储在一个区间中，记下区间的范围即可。排序方式使用计数排序，时间复杂度为线性。

其同时具备 vector 和链式前向星的优点，既能保证遍历时内存访问连续，又不需要动态分配内存。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int to[MAXM];
int head[MAXN], tail[MAXN];
void build(int n, int m) {
    static std::pair<int, int> edge[MAXM];
    static int cnt[MAXN];
    for (int i = 1, u, v; i <= m; i++) {
        std::cin >> u >> v;
        edge[i] = {u, v};
        cnt[u]++;
    }
    for (int i = 1; i <= n; i++) {
        cnt[i] += cnt[i - 1];
        head[i] = cnt[i - 1] + 1;
        tail[i] = cnt[i];
    }
    for (int i = 1; i <= m; i++) {
        to[cnt[edge[i].first]--] = edge[i].second;
    }
}

另外，如果再写一个辅助结构体 Edge，便可以使用 for (auto& v : Edge{u}) 遍历点 u 的所有出边。

1
2
3
4
5
struct Edge {
    int u;
    int* begin() const {return to + head[u];}
    int* end() const {return to + tail[u] + 1;}
};