如何存图

· · 算法·理论

::::info[测试环境]{open} 本文在 Luogu IDE 进行测试，版本选择为 C++14 (GCC 9) O2。

编译开关为 g++ -x c++ -std=c++14 -fPIC -DONLINE_JUDGE -Wall -fno-asm -lm -march=native -O2。

洛谷评测机为 Intel(R) Xeon(R) Platinum 8369HC @ 3.30GHz（睿频 3.80GHz）。

测试方法为 5 次结果取平均。 :::: ::::info[测试代码]

#include <bits/stdc++.h>

constexpr int N = 1000000, M = 2000000;

struct Timer {
    std::chrono::high_resolution_clock::time_point beginTime;
    Timer() : beginTime(std::chrono::high_resolution_clock::now()) {}
    long long operator()() const { return std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::high_resolution_clock::now() - beginTime).count(); }
};

struct VectorList {
    std::vector<std::pair<int, int>> graph[N];
    inline void addEdge(int u, int v, int w) { graph[u].emplace_back(v, w); }

    long long build() {
        std::mt19937 rng;
        std::uniform_int_distribution<int> distribute(0, N - 1);
        Timer timer;
        std::for_each(graph, graph + N, [](std::vector<std::pair<int, int>>& i) { i.reserve(32); });
        for (int i = M; i--; addEdge(distribute(rng), distribute(rng), rng()));
        return timer();
    }

    long long traverse() {
        std::mt19937 rng;
        std::vector<int> order(N);
        std::iota(order.begin(), order.end(), 0);
        std::shuffle(order.begin(), order.end(), rng);
        int something = 0;
        Timer timer;
        for (int i : order)
            for (auto edge : graph[i])
                something ^= edge.first ^ edge.second & rng();
        return timer();
    }
};

struct ForwardStar {
    struct Edge { int destination, weight; Edge *next; } edges[M], *head[N], *current = edges - 1;
    inline void addEdge(int u, int v, int w) { *++current = Edge{v, w, head[u]}, head[u] = current; }

    long long build() {
        Timer timer;
        std::mt19937 rng;
        std::uniform_int_distribution<int> distribute(0, N - 1);
        for (int i = M; i--; addEdge(distribute(rng), distribute(rng), rng()));
        return timer();
    }

    long long traverse() {
        std::mt19937 rng;
        std::vector<int> order(N);
        std::iota(order.begin(), order.end(), 0);
        std::shuffle(order.begin(), order.end(), rng);
        int something = 0;
        Timer timer;
        for (int i : order)
            for (auto edge = head[i]; edge; edge = edge->next)
                something ^= edge->destination ^ edge->weight & rng();
        return timer();
    }
};

int main() {
    static VectorList vectorList;
    static ForwardStar forwardStar;
    std::cout << "N = " << N << ", M = " << M << '\n';
    std::cout << "vectorList: build time used: " << vectorList.build() << "ms.\n";
    std::cout << "vectorList: traverse time used: " << vectorList.traverse() << "ms.\n";
    std::cout << "forwardStar: build time used: " << forwardStar.build() << "ms.\n";
    std::cout << "forwardStar: traverse time used: " << forwardStar.traverse() << "ms.\n";
    return 0;
}

::::

前言

邻接表是处理稀疏图的首选数据结构，其性能优劣直接决定了图算法的整体效率。

在 OI 中，我们常面临两种主流实现的选择：传统的手工实现的链式前向星和利用 vector 构建的 vector 邻接表。

前者以其极致的低开销和紧凑存储著称，后者则凭借编码简洁、易用性与良好的缓存友好性受到青睐。关于“哪种实现更快”的讨论一直存在。

本文正是为了厘清这一疑问，通过设计严谨的基准测试，在多种图结构和操作负载下，系统性地评测并对比这两种邻接表实现的效率，揭示其各自的优势场景与潜在瓶颈。

以下用表指代 vector 邻接表，用星指代链式前向星。

1. 实现难度比较

构建简单，加边简单，遍历出边简单。由于部分编辑器可以在调试中直接读 STL 容器，所以它的调试也很简单。

vector<pair<int, int>> graph[Maxn];

void addEdge(int u, int v, int w) {
    graph[u].emplace_back(v, w);
}

void traverse(int u) {
    for (auto edge : graph[u])
        cout << edge.first << ' ' << edge.second << '\n';
}

相比表会困难一些，并且由于同一节点的出边存储并不一定连续，这使得我们必须手动追踪 next，增加了调试的难度。

struct Edge {
    int first, second;
    Edge *next;
} edges[Maxm << 1], *head[Maxn], *current = edges - 1;

void addEdge(int u, int v, int w) {
    *++current = Edge{v, w, head[u]}, head[u] = current;
}

void traverse(int u) {
    for (auto edge = head[u]; edge; edge = edge->next)
        cout << edge->first << ' ' << edge->second << '\n';
}

总结：如果题目不卡常，请使用表。它更好写，且可读性更高，好调试、不容易出错。

2. 空间占用比较

静态占用 \text{sizeof}(\text{vector})\cdot n=24n\text{ B}。

动态占用 \text{sizeof}(\text{pair})\cdot m=8m\text{ B}。由于 vector 的扩容特性，其可以达到 16m\text{ B}。

总空间为 24n+16m\text{ B}。

无动态占用。总空间为 8n+16m+8\text{ B}。

总结：如果空间过于紧张，请使用星。但是我没见过卡空间的图论。

3. 建图速度比较

稠密图 n=5\cdot10^5,m=10^7

表的用时是星的约 1.94 倍。

稀疏图 n=5\cdot10^5,m=2\cdot10^6

表的用时是星的约 2.27 倍。

总结：星的建图速度大大优于表。图越稀疏，这一优势越明显。这是因为在建图时，表会涉及大量的重分配内存，而星的内存并不需要动态分配。

但是因为每次加边触发重分配内存都会使得 vector 容量翻倍，所以到后面重分配触发次数会越来越少，这使得在稠密图中星的优势会小一些。

4. 遍历速度比较

稠密图 n=5\cdot10^5,m=10^7

星的用时是表的约 9.06 倍。

稀疏图 n=5\cdot10^5,m=2\cdot10^6

星的用时是表的约 2.91 倍。

总结：表的遍历速度碾压星。图越稠密，这一优势越明显。这是因为表中每个节点的出边在内存中是连续的，容易触发缓存命中，连续访问效率非常高，而星则需链式访问。

但是对于稀疏图来说，由于平均一个节点的出边数量偏少，可能小于缓存大小，所以效率差距不是那么明显了。

5. 高级特性比较

支持出边随机访问，使得它可以将出边按照一定方法排序（如字典序排序、边权排序等），这是星的前向访问所不支持的。

当然如果你硬要让星排序的话可以把出边遍历一遍全取出来扔到一个序列容器里然后排序再重新插回去。

由于所有边都在一整片连续的内存中，所以它在存储无向图时可以非常方便地查询一条边的反向边（异或 1 即可，这一特性常用于网络流算法中）而表需要繁琐地维护很多信息来完成这一功能。

总结：各有所长。

评价