C++如何使用数组实现邻接表-C++-PHP中文网

因为需极致常数性能，vector的动态扩容、迭代器失效和内存不连续会拖慢遍历；数组模拟邻接表（链式前向星）通过head[]、to[]、next[]实现连续内存访问与零函数调用开销。

c++如何使用数组实现邻接表

为什么不用 vector 而用数组实现邻接表

因为需要极致的常数性能（比如 OI 高频图题），vector 的动态扩容、迭代器失效、内存不连续都会拖慢遍历；而静态数组配合链式前向星（即“数组模拟邻接表”）能保证所有边访问都是连续内存跳转，且无函数调用开销。

核心思路是：用两个全局数组 head[] 存每个点的“第一条边编号”，用 to[] 和 next[] 模拟单链表。每加一条边 u → v，就往数组末尾塞一个新节点，并更新 next[new_idx] = head[u]，再令 head[u] = new_idx。

关键数组定义和初始化怎么写

假设最多 N 个点、M 条边（有向），需提前开足够大的静态数组：

const int N = 1e5 + 5;
const int M = 2e5 + 5; // 注意：无向图边数×2
int head[N], to[M], next[M], idx;
// 初始化：memset(head, -1, sizeof head) 或 for(int i = 1; i 
<p>注意三点：</p>

head[] 初始必须为 -1，表示空链表；不能用 0，否则和合法下标混淆
idx 从 0 开始，所以 next[] 数组下标范围是 [0, M-1]
无向图要调用两次 add_edge(u, v) 和 add_edge(v, u)，别漏

add_edge 和遍历邻接表的写法

添加边就是头插法，保持插入顺序不影响正确性，但会影响遍历顺序（后加的边先被访问）：

C++ 算法竞赛自动化测试数据生成与校验框架

根据原题生成新题面、验证器及完整测试数据，自动套用 testlib 模板，用于用户要求生成测试数据时。

下载

void add_edge(int u, int v) {
    to[idx] = v;
    next[idx] = head[u];
    head[u] = idx++;
}

遍历点 u 的所有出边：

for (int i = head[u]; i != -1; i = next[i]) {
    int v = to[i]; // u → v 是一条边
    // ... 处理逻辑
}

常见错误：

循环条件写成 i —— 错，<code>idx 是总边数，但 head[u] 链只含部分下标
忘记在 add_edge 里更新 idx++，导致所有边都堆在 to[0]/next[0]
把 to[i] 误当成点编号而非目标点，尤其在重边/自环场景下容易逻辑错

空间和索引边界容易踩的坑

数组大小不是拍脑袋定的：

若题目说 n ≤ 10^5，边数 m ≤ 2×10^5，那 M 至少设为 200005，建议上浮 5% 避免 RE
head[] 下标是点编号，所以大小看点数上限，不是边数
多组数据时，idx 必须清零，head[] 必须重置为 -1；只清 idx=0 不清 head[] 会残留旧图指针
如果用结构体封装（如 struct Edge { int to, next; } e[M];），则 head[u] 存的是结构体下标，逻辑一致，但可读性略高