作者：千秋 Lead | 原文：知乎专栏 现在有很多教程难以看懂的原因是因为用数组下标（数字）来同时给节点和边编号，又用做边权的类型，由于一个数字没有类型，所以读者经常容易混淆编号与对象的对应，所以本文用字母给节点编号，数字给边编号。

首先，我们要明确一点，链式前向星本质是一个存了一组边的数组，**基本等同于邻接表，**但是不同之处是：

邻接表存起点，终点指针（即数组索引），和可选的权重共三个值。

链式前向星只存终点指针，相同

的边归一类，同一类在一个链表内，后添加的边指向前添加的边，最先添加的指向空（这是其名中「前向」的由来），和可选的权重共两个值。

例如，这三条边在同一链表内

所以链式前向星有个优点是，可以方便地遍历一个点的出边，这在写BFS，DFS等算法时很方便。

那如何给节点编号呢？只需要添加几个就编几号好了，或者从0号开始也行。

以此图为例，我们先看一下存完后的样子。

next数组就是链表的实现，next[当前点]=指向点。每一个边的编号都指向着共起点的另一边的编号，最先加入或无共起点的边指向-1，所以最开始初始化为-1。

to 数组是此边指向的点编码。

lesfh (last edge starting from here)在大部分代码中又名head ，我认为我的名字更直观，作用是用来保存最后一个从某点开始的边的编号，输入点编号，输出边编号。它是用来让当前边查询上一个从同样点开始的边，以指向的。所以next会在每条边加入时，指向最后一个从现在起点开始的边，因此要初始为-1。听不明白？看个例子吧。

我们按照图中顺序存边。看表顺序：先上到下，后左到右，lesfh行单独看

next0 (A->B)1 (B->C)2 (A->C)3 (A->D)-1 （最开始没有从A开始的上一条边，故指-1）-10 （lesfh[A]=0，故指向0.）2 （lesfh[A]=2，故指向0.）to0 (A->B)1 (B->C)2 (A->C)3 (A->D)B （0号边指向B)CCDlesfhABCD-1-1-1-10 （最后的从A开始的边是0号）12 （因为2从A开始，改为2）2 （因为3从A开始，改为3）

相信现在看代码不难。

// 给顶点起别名方便观察

using

VIndex

=

size_t
;

using

EIndex

=

size_t
;

struct

Edge

{


// 指向的同起点的边


EIndex

next
;


// 指向的顶点


VIndex

to
;


// 权


int

weight
;

}

edges
[
N
];

EIndex

lesfh
[
N
];

// 自行初始为 -1

size_t

edge_now

=

-
1
;

// VIndex 代表顶点索引, EIndex 代表边索引

void

add_edge
(
VIndex

from
,

VIndex

to
,

int

weight
)

{


edge_now

+=

1
;


edges
[
edge_count
].
to

=

to
;


edges
[
edge_count
].
next

=

lesfh
[
from
];


lesfh
[
from
]

=

edge_count
;

}

若欲查两点A，B之间距离，遍历的A的出边，找到终点为B的边即可。

int

get_weight
(
VIndex

from
,

VIndex

to
)

{


// 遍历from的出边


for

(


EIndex

edge_index

=

lesfh
[
from
];

// 最后以from点作起点的边


edge_index

!=

-
1

;

// 后面没边了


edge_index

=

edges
[
edge_index
].
next

// 链表链接到的下一个同始边


)

{


if

(
edges
[
edge_index
].
to

==

to
)

{

// 此边终点是查询终点


return

edges
[
edge_index
].
weight
;


}


}


return

INFINITY
;


}

还不懂问我。