图论基础

存图

邻接矩阵

实现：

int g[N][N];

g[u][v] = w;

for (int v = 1; v <= N; v++) {
    if (!g[u][v]) continue;
    // ...
}

空间复杂度：$O(n^2)$

优点

• 配合Floyd算法，效果嘎嘎好
• 支持随机访问，即直接查询某条边是否存在
• 代码好写

缺点

• 空间复杂度太高，是个硬伤

邻接表

实现：

vector<pair<int, int>> g[N];

g[u].push_back({v, w});

for (pair<int,int> i : g[u]) {
    int v = i.first, w = i.second;
    // ...
}

空间复杂度：$O(m)$

优点

• 空间复杂度小
• 同一个点空间连续，有效降低Memory Cache带来的时间花销
• 写循环遍历 $u$ 边时可以少写点代码：for (pair<int,int> i : g[u])

缺点

• 由于 vector ，空间复杂度要翻个倍，在卡空间的题目中它不是好选择
• 莫名其妙TLE（STL造成的）

链式前向星

实现：

struct node{
    int to, nxt, w;
}g[M];
int head[N], cnt;

void add(int u, int v, int w) {
    g[++cnt] = {v, head[u], w};
    head[u] = cnt;
}

for (int i = head[u]; i; i = g[i].nxt) {
    int v = g[i].to, w = g[i].w;
    // ...
}

空间复杂度：$O(m)$

优点

• 空间复杂度真的小，没有 vector 的两倍空间限制

缺点

• Memory Cache耗时极高，尤其是完全图