6255: 学习系列 —— 图论5：图的存储 4：链式前向星
[Creator : ]
Description
【方法】
本质上是用链表实现的邻接表。
【核心代码】
本质上是用链表实现的邻接表。
【核心代码】
// C++ Version
// head 和 cnt 的初始值都为 -1
void add(int u, int v) {
nxt[++cnt] = head; // 当前边的后继
head = cnt; // 起点 u 的第一条边
to[cnt] = v; // 当前边的终点
}
// 遍历 u 的出边
for (int i = head; ~i; i = nxt[i]) { // ~i 表示 i != -1
int v = to[i];
}
# Python Version
# head 和 cnt 的初始值都为 -1
def add(u, v):
cnt = cnt + 1
nex[cnt] = head # 当前边的后继
head = cnt # 起点 u 的第一条边
to[cnt] = v # 当前边的终点
# 遍历 u 的出边
i = head
while ~i: # ~i 表示 i != -1
v = to[i]
i = nxt[i]
【复杂度】
查询是否存在 $u$ 到 $v$ 的边：$O(d^+(u))$。
遍历点 $u$ 的所有出边：$O(d^+(u))$。
遍历整张图：$O(n+m)$。
空间复杂度：$O(m)$。
【应用】
存各种图都很适合，但不能快速查询一条边是否存在，也不能方便地对一个点的出边进行排序。
优点是边是带编号的，有时会非常有用，而且如果 cnt 的初始值为奇数，存双向边时 i ^ 1 即是 i 的反边（常用于 网络流）。