链式前向星

链式前向星是 OI 里面很常见的一种存图方式。

第一次看到这一套东西的时候其实很容易懵：

head[u]
to[i]
nxt[i]
weight[i]

尤其是：

nxt[i]

名字看起来像链表，但是代码里面又根本没有指针。

后来把它拆开以后就会发现，链式前向星本质上其实就是：

用数组下标代替指针，模拟一个邻接表。

每一条边都有一个编号，然后通过：

head
+
nxt

把从同一个点出发的边串起来。

所以它真正需要理解的不是模板怎么背，而是：

点怎么找到第一条边？
一条边怎么找到终点？
一条边怎么找到同一起点的下一条边？

把这三个问题搞明白以后，整个东西就没有那么绕了。

为什么需要存图

假设有一张有向图：

最直接当然可以用邻接矩阵：

g[u][v] = 1;

如果有边权：

g[u][v] = w;

这样非常直观。

但是邻接矩阵需要给任意两个点之间都留下一个位置。

如果有：

n 个点

那么矩阵需要：

$$ n^2 $$

个位置，空间复杂度就是：

$$ O(n^2) $$

如果图只有几百个点，这当然无所谓。

但是 OI 里面经常有：

10^5 个点

甚至更多。

如果：

$$ n=10^5 $$

那么邻接矩阵理论上需要：

$$ 10^{10} $$

个元素，显然不可能。

问题是，很多这样的图实际上只有：

几万
几十万

条边。

绝大多数：

u → v

其实根本不存在。

这种图就是稀疏图。

所以更合理的办法应该是：

一个点有什么边，就只存什么边。

例如：

这就是邻接表。

链式前向星做的事情，本质上也是邻接表，只不过没有给每一个点开一个真正的链表，而是把所有边统一放进几个数组里面。

边也可以有编号

假设一共有：

m 条边

那么完全可以把每一条边编号：

0
1
2
3
...
m-1

于是每一条边不再需要一个独立的结构指针。

只要知道边编号：

就可以用不同数组查这条边的信息。

最基本的一套：

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

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

int idx = 0;

其中：

idx

表示下一条新边应该使用哪个编号。

每调用一次 addEdge()：

idx++

就相当于新建了一条边。

四个核心数组

最重要的是先把几个数组分别是什么意思弄清楚。

head

head[u]

表示：

从点 u 出发的边链表，目前的头部边编号。

注意它保存的不是：

终点编号

而是：

边编号

例如：

head[1] = 7

意思不是：

1 → 7

而是：

点1当前首先要访问的是第7号边。

然后再通过：

to[7]

才能知道第7号边到底通向哪个点。

to

to[i]

表示：

第 i 条边的终点。

如果：

第5号边：

2 → 8

那么：

to[5] = 8;

所以 to 回答的问题就是：

这条边通向哪里？

weight

如果是带权图：

weight[i]

表示：

第 i 条边的权值。

例如：

第5号边：

2 --10--> 8

那么：

to[5] = 8;
weight[5] = 10;

nxt

最容易绕的就是：

nxt[i]

它不是：

下一个点。

而是：

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

所以这两个数组一定要分清：

to[i]
↓
这条边走到哪个点？

nxt[i]
↓
接下来还要看哪一条边？

链式前向星真正“链”起来的对象不是点，而是：

边

初始化

开始的时候，每个点都没有任何出边。

所以：

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

把所有：

head[u]

设成：

-1

表示：

这个点的边链表为空

也就是：

没有下一条边

加入第一条边

假设现在加入：

1 → 2

权值先不管。

初始：

head[1] = -1
idx = 0

新边编号为：

所以：

to[0] = 2;

然后：

nxt[0] = head[1];

因为：

head[1] = -1

所以：

nxt[0] = -1

最后：

head[1] = 0;

现在：

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

点1的边链表里面只有一条边。

再加一条边

现在再加入：

1 → 3

新边编号：

先：

to[1] = 3;

然后最关键的一步：

nxt[1] = head[1];

此时旧的：

head[1] = 0

所以：

nxt[1] = 0

也就是让新边指向原来的链表头。

然后：

head[1] = 1;

把新边放到最前面。

现在变成：

head[1]
   ↓
 edge 1
   ↓
 to[1] = 3
   ↓
 nxt[1] = 0
   ↓
 edge 0
   ↓
 to[0] = 2
   ↓
 nxt[0] = -1

所以点1的出边现在是：

1 → 3
1 → 2

再加入1→4

继续：

1 → 4

这次：

idx = 2

于是：

to[2] = 4;
nxt[2] = head[1];
head[1] = 2;

因为原来：

head[1] = 1

所以：

nxt[2] = 1

最后整条链变成：

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

也就是：

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

所以：

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

其实就是最普通的：

头插法

addEdge

于是加边函数就很好理解了：

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

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

    idx++;
}

拆开就是：

to[idx] = v
↓
记录新边通向 v

weight[idx] = w
↓
记录新边权值

nxt[idx] = head[u]
↓
新边后面接原来的第一条边

head[u] = idx
↓
新边成为新的链表头

idx++
↓
准备下一条边

本质上完全就是链表的头插。

只不过：

指针

换成了：

数组下标

为什么顺序反过来了

假设输入：

1 → 2
1 → 3
1 → 4

因为每次都把新边插在最前面，所以最后遍历出来的是：

1 → 4
1 → 3
1 → 2

也就是：

输入顺序
2 3 4

遍历顺序
4 3 2

正好相反。

通常图论算法只关心：

有哪些邻边

并不关心按照什么顺序访问，所以没有影响。

但如果某一道题真的对访问顺序有要求，这一点就需要注意。

如何遍历一个点的所有出边

假设现在要遍历点：

的所有出边。

先：

int i = head[u];

得到第一条边编号。

然后：

to[i]

得到这条边的终点。

再：

nxt[i]

得到下一条边。

所以完整代码就是：

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

    // u -> v
}

整个循环其实就是：

i = head[u]
↓
找到第一条边

to[i]
↓
查看终点

nxt[i]
↓
找到下一条边

to[i]
↓
查看终点

nxt[i]
↓
继续

...

-1
↓
结束

所以最核心的链可以写成：

点 u
 ↓
head[u]
 ↓
边编号 i
 ↓
nxt[i]
 ↓
下一条边编号
 ↓
nxt[i]
 ↓
下一条边编号
 ↓
...

而每一条边再通过：

to[i]

指向真正的顶点。

一个完整例子

例如输入：

表示：

4 个点
5 条有向边

每条边有一个权值。

代码：

#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

原因就是后加入的边永远成为新的：

head[1]

空间复杂度

如果图有：

n 个点
m 条有向边

那么：

head

需要：

$$ O(n) $$

空间。

而：

to
nxt
weight

都是每条边保存一个元素，所以一共：

$$ O(m) $$

因此链式前向星的总空间复杂度是：

$$ O(n+m) $$

相比邻接矩阵：

$$ O(n^2) $$

对于稀疏图差别非常大。

遍历复杂度

如果只遍历点 u 的所有出边，那么循环：

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

只会访问真正存在的出边。

假设：

u 的出度 = deg(u)

那么遍历复杂度就是：

$$ O(\deg(u)) $$

如果把整张图所有点都遍历一遍，每一条边最多访问一次。

所以：

$$ O(n+m) $$

这也是邻接表适合稀疏图的原因。

不是去问：

u 和每一个 v 之间有没有边？

而是直接访问：

u 真正有哪些边？

无向图

有向图：

u → v

只需要存一次：

addEdge(u, v, w);

但是无向图：

u — v

实际上等于：

u → v
v → u

所以必须加入两条边：

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

如果题目有：

m 条无向边

那么数组真正需要保存：

$$ 2m $$

条有向边。

例如题目最多：

条无向边。

那么：

to
nxt
weight

至少应该开到：

以上。

例如：

const int M = 400005;

这个地方挺容易数组越界。

i xor 1

如果无向边、网络流之类的程序总是成对加边：

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

并且从：

开始编号，那么边编号会自然形成：

每一对边之间：

0 ↔ 1
2 ↔ 3
4 ↔ 5

这时可以利用：

i ^ 1

在一对边之间切换。

因为二进制最低位：

偶数 ^ 1 = 下一个奇数
奇数 ^ 1 = 前一个偶数

所以：

这种写法在网络流里面尤其常见。

因为正向边和反向边本来就需要频繁同时操作。

DFS里面怎么用

真正做题当然不是为了打印邻接表。

比如 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);
    }
}

这里：

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

其实就是：

枚举所有和 u 相邻的点。

换成邻接表的说法就是：

for each v in G[u]

只不过链式前向星把这个：

G[u]

自己用数组模拟出来了。

Dijkstra里面怎么用

最短路也是一样。

当 Dijkstra 已经取出当前点：

以后，需要枚举：

u 的所有出边

所以：

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;
    }
}

核心仍然完全一样：

head[u]
↓
第一条边

nxt[i]
↓
下一条边

不管外面是：

DFS
BFS
Dijkstra
SPFA
拓扑排序
树形DP
网络流

枚举邻边的时候，本质都还是这一套。

所以链式前向星真正需要熟练到的程度应该是：

看到：

int i = head[u];

脑子里直接知道：

开始枚举 u 的出边

看到：

i = nxt[i];

就知道：

跳到 u 的下一条出边

而不是每次重新背模板。

和vector邻接表相比

C++ 里面当然也可以直接写邻接表。

例如：

#include <vector>
using namespace std;

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

加入一条边：

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

然后遍历：

for (int i = 0; i < (int)g[u].size(); i++)
{
    int v = g[u][i].first;
    int w = g[u][i].second;

    // u -> v
}

从代码可读性来说，这确实更直观。

因为：

g[u]

本身就很像：

u 的所有邻边

而链式前向星需要：

head
to
nxt

来回跳。

但是链式前向星也有自己的特点。

所有边都连续存在数组里面：

edge 0
edge 1
edge 2
...

内存大小提前确定，也天然拥有边编号。

所以如果算法本身经常需要：

直接操作第 i 条边

这种结构就很方便。

尤其是网络流里面，经常需要同时修改：

正向边
反向边

配合：

i ^ 1

就很好用。

所以普通图论题里面，用什么存图其实可以根据习惯。

但是传统 OI 模板、数据规模比较大，或者需要频繁操作边编号的时候，链式前向星一直都很常见。

它其实就是链表

我最开始学链式前向星的时候，最难理解的就是：

为什么需要 head？
为什么有 to？
为什么还要 nxt？

感觉几个数组绕来绕去。

后来真正画出来以后其实特别简单。

如果真的用链表写，大概会是：

点 u

↓

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

↓

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

↓

...

链式前向星只是把：

指针

换成：

整数编号

于是：

next 指针

变成：

nxt[i]

原本：

指向第一条边的指针

变成：

head[u]

边本身的：

to
weight

则拆开放进数组：

to[i]
weight[i]

所以：

head[u]
↓
找到第一条边

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

weight[i]
↓
知道这条边多重

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

这就是全部。

最后

链式前向星这个名字听起来挺复杂，但是核心其实只有一句：

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

从数据结构上看，它就是：

邻接表
+
数组模拟链表

空间复杂度：

$$ O(n+m) $$

遍历整张图：

$$ O(n+m) $$

对于一个点：

$$ O(\deg(u)) $$

真正把：

head
to
nxt

这三个东西弄明白以后，后面的图论模板会一下顺很多。

因为不管是：

DFS
最短路
树
拓扑排序
网络流

看到：

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

其实都只是在做同一件事情：

把从 u 出发的边一条一条拿出来。

模板可以忘。

这个结构最好别忘。