什么是链式前向星

 Tags: OI  图论  Categories: 学习 

首先我们要明确链式前向星到底存的是什么。我们知道，邻接表存的是一个点相邻的所有点，而链式前向星是以 链表 为数据结构存放的 与某个点相邻的边。

举个例子，

这里面的每一项存放的都是以 为起点的所有边，其中 为第一个边， 为第二个边，以此类推。

一般来说，我们使用结构体来定义一个边，

struct Edge {
  int to; // 这个边指向的下一个点；
  int next; // 同一起点的下一个边。
};

Edge edge[10005];

这里的 edge[i].next 便是我们上面的 next[] 数组。

那么我们该如何加边呢？

int cnt = 0;
void addEdge(int u, int v) {
  cnt += 1;
  edge[cnt].to = v;
  edge[cnt].next = head[u];
  head[u] = cnt; // 需要注意的是这里的 head[u] 被更新了。
}

上面的 head[u] 被更新为了这一条边，即为我们之前说到的 next[head[u]]。也不难发现，head[u] 实际存放的是最后加入的边，即边是被倒序加入的。

那么，遍历也便水到渠成了，

// i 为边的编号。
for (int i = head[u]; i != 0; i = edge[i].next) {
  ...
}

当此时的 edge[i].next 为 0 时，说明边 i 即为这个点所连的最后一个边，也就是遍历完毕。当然我们也可以把 next[] 数组初始化为其它值比如 -1，其本质是一样的。

Last updated: 2025-01-29