链式前向星

链式前向星是 OI 里很经典的一种存图方式。第一次看到这几个数组的时候其实很容易懵：

head[u]
to[i]
next[i]
weight[i]

尤其是 next，看起来像链表，但代码里又没有任何指针。实际上链式前向星本质上就是用数组模拟邻接表中的链表，每一条边对应数组中的一个编号，再通过 head 和 next 把同一个起点出发的边串起来。

如果只记模板当然也能用，但图论后面 BFS、DFS、Dijkstra、SPFA、拓扑排序、网络流都会反复出现这种结构，因此最好真正理解这些数组各自在表示什么。

为什么需要存图

假设有一张有向图：

最容易想到的方式当然是邻接矩阵：

g[u][v] = 1;

如果有边权，也可以直接：

g[u][v] = w;

这种写法非常直观，但问题是空间复杂度为：

O(n²)

如果只有几百个点当然无所谓，但 OI 里经常出现十万甚至百万级的点，而实际边数可能只有几十万。这种图称为稀疏图，如果仍然开一个 n × n 的矩阵，大量空间都会浪费在根本不存在的边上。

所以更合理的方法是：对于每一个点，只保存真正从它出发的边。

这就是邻接表的基本思想。链式前向星做的事情，只不过是不用 STL 的 vector，而是自己拿几个数组把这张邻接表拼出来。

四个核心数组

先看一份最基本的模板：

const int N = 100005;
const int M = 200005;

int head[N];
int to[M];
int nxt[M];
int weight[M];

int idx = 0;

其中 idx 表示目前已经存了多少条边，每加入一条新边，就占用一个新的边编号。

四个数组分别表示：

head[u]
点 u 的第一条出边编号

to[i]
第 i 条边指向哪个点

weight[i]
第 i 条边的权值

nxt[i]
和第 i 条边拥有同一个起点的
下一条边编号

这里最容易混淆的是 to 和 nxt。

to[i]
回答：
这条边通向哪里？

nxt[i]
回答：
同一个起点还有哪条边？

所以 nxt 并不是“下一个节点”，而是下一条边的编号。

初始化时一般把所有 head 设置为 -1：

memset(head, -1, sizeof(head));

表示目前每个点都还没有任何出边。

加入一条边

假设现在需要加入一条：

u → v

权值为 w，代码通常写成：

void addEdge(int u, int v, int w)
{
    to[idx] = v;
    weight[idx] = w;

    nxt[idx] = head[u];
    head[u] = idx;

    idx++;
}

真正需要理解的其实只有下面两行：

nxt[idx] = head[u];
head[u] = idx;

它做的是一个非常简单的头插法。

假设点 1 现在还没有任何边：

head[1] = -1

先加入：

1 → 2

此时这条边编号为 0：

to[0] = 2

nxt[0] = -1

head[1] = 0

结构就是：

head[1]
   ↓
 edge 0
   ↓
   2

随后再加入：

1 → 3

新边编号为 1。先把原本的 head[1] 保存进 nxt[1]：

nxt[1] = head[1];

所以：

nxt[1] = 0

然后让新的边成为链表头部：

head[1] = 1;

于是：

head[1]
   ↓
 edge 1
   ↓
   3

nxt[1]
   ↓
 edge 0
   ↓
   2

如果继续加入：

1 → 4

这条边编号为 2，最终链条变成：

head[1] = 2

edge 2
to[2] = 4
nxt[2] = 1

        ↓

edge 1
to[1] = 3
nxt[1] = 0

        ↓

edge 0
to[0] = 2
nxt[0] = -1

所以点 1 的所有出边实际上被串成：

head[1]
   ↓
1 → 4
   ↓
1 → 3
   ↓
1 → 2
   ↓
  -1

因为使用的是头插法，所以遍历顺序正好和加入顺序相反。这通常没有任何影响，但某些特别依赖访问顺序的题目需要注意。

如何遍历

如果要遍历点 u 的全部出边，就从 head[u] 开始：

for (int i = head[u]; i != -1; i = nxt[i])
{
    int v = to[i];
    int w = weight[i];

    // u -> v
}

把这句话拆开其实就是：

i = head[u]

先找到 u 的第一条边。

v = to[i]

查看这条边通向哪里。

i = nxt[i]

跳到同一起点的下一条边。

一直走到：

i == -1

说明已经没有下一条边。

所以链式前向星最核心的结构其实可以压缩成：

点
↓
head
↓
边
↓
nxt
↓
下一条边
↓
nxt
↓
下一条边
...

而每一条边再通过 to 指向真正的终点。

完整例子

例如输入：

表示四个点、五条有向边，每条边还有一个权值。

#include <iostream>
#include <cstring>
using namespace std;

const int N = 100005;
const int M = 200005;

int head[N];
int to[M];
int nxt[M];
int weight[M];
int idx;

void addEdge(int u, int v, int w)
{
    to[idx] = v;
    weight[idx] = w;

    nxt[idx] = head[u];
    head[u] = idx;

    idx++;
}

int main()
{
    memset(head, -1, sizeof(head));

    int n, m;
    cin >> n >> m;

    for (int i = 0; i < m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;

        addEdge(u, v, w);
    }

    for (int u = 1; u <= n; u++)
    {
        cout << u << ": ";

        for (int i = head[u]; i != -1; i = nxt[i])
        {
            cout << "(" << to[i]
                 << ", " << weight[i]
                 << ") ";
        }

        cout << '\n';
    }

    return 0;
}

由于链式前向星使用头插法，最终输出大致会是：

1: (4, 30) (3, 20) (2, 10)
2: (4, 40)
3: (4, 50)
4:

可以看到，虽然输入时是：

1 → 2
1 → 3
1 → 4

遍历时变成：

1 → 4
1 → 3
1 → 2

原因正是每次新边都插到了最前面。

无向图

有向图中的：

u → v

只需要加入一条边。

而无向图：

u — v

实际上需要存成两条有向边：

u → v
v → u

所以写成：

addEdge(u, v, w);
addEdge(v, u, w);

这时候边数组的空间也必须开两倍。例如题目最多有 200000 条无向边，那么实际需要保存：

条有向边。

因此常见写法会直接：

const int M = 400005;

这个地方是比赛里很常见的数组越界来源。

在图论算法中怎么用

真正做题的时候，一般不会为了“打印邻接表”而使用链式前向星。它最大的意义是给各种图论算法提供统一的遍历方式。

例如 DFS：

void dfs(int u)
{
    vis[u] = true;

    for (int i = head[u]; i != -1; i = nxt[i])
    {
        int v = to[i];

        if (!vis[v])
            dfs(v);
    }
}

Dijkstra 里也是一样：

for (int i = head[u]; i != -1; i = nxt[i])
{
    int v = to[i];
    int w = weight[i];

    if (dist[v] > dist[u] + w)
    {
        dist[v] = dist[u] + w;
    }
}

换成拓扑排序、SPFA、树形 DP、网络流，本质上仍然是在不断重复：

for (int i = head[u]; i != -1; i = nxt[i])

所以链式前向星真正需要熟练到的程度，并不是背下 addEdge，而是看到：

int i = head[u];

脑子里就能直接出现：

正在访问 u 的第一条出边

看到：

i = nxt[i];

就知道：

正在沿着边链表继续向后找

和 vector 邻接表相比

现在正常写 C++，当然也可以直接：

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

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

然后：

for (auto [v, w] : g[u])
{
    // ...
}

从可读性来说，这显然更加直观。

链式前向星的优势主要在于数据全部保存在连续数组中，内存结构固定，不需要为大量 vector 分别维护动态空间，而且边编号天然存在，因此在一些需要直接操作“第几条边”的算法里尤其方便。

例如网络流中经常利用：

i ^ 1

在一条边和它的反向边之间切换，这种写法和数组式存边天然配合。

所以在普通图论题中：

vector 邻接表

通常更容易写，也更容易读。

但在传统 OI 模板、数据规模很大、需要严格控制内存，或者网络流这类大量直接操作边编号的算法中：

链式前向星

仍然非常常见。

最后

我最开始学链式前向星的时候，最难理解的地方一直是为什么需要 head、to、next 三个数组绕来绕去。后来真正理解以后，其实它没有什么神秘的。

它只是在拿整数下标模拟指针：

head[u]
↓
找到第一条边

to[i]
↓
知道这条边通向谁

nxt[i]
↓
找到同一起点的下一条边

如果把它想成真正的链表，结构实际上就是：

u

↓

edge
{
    to = v
    weight = w
    next = 下一条边
}

↓

edge
{
    to = v
    weight = w
    next = 下一条边
}

↓

...

区别只是链表里原本应该保存的指针，被替换成了数组下标。

所以链式前向星这个名字听起来很复杂，真正的核心其实只有一句：

用数组保存所有边，再用边编号把同一个点的出边串成链表。

理解这一点以后，后面的 DFS、最短路、树论乃至网络流，看到这一套数组时就不会再觉得它是一堆需要死记的模板了。