链式前向星介绍

什么是链式前向星？

链式前向星是一种常用的图存储结构，其思路类似于邻接链表法，只是实现方式有所不同，链式向前星更像是用数组模拟链表。

与一般的邻接链表法不同，链式向前星储存的图的每条边都有编号。

以下是链式前向星的存储结构：

• cnt ：用来记录当前所有边的数量

• first 数组：用来存储从某个节点出发的第一条边，例如 first[0] == 3 可以得出从 0 号节点出发的第一条边的编号为 3

• edges 数组：用来记录每条边的信息，对于每个 edges[i] 都有 3 个域：

  • to ：记录边的终点
  • weight ：记录边的权重
  • next ：记录从当前起点出发下一条边的编号，例如：若 edges[i] 的起点为 j 号节点，则 edges[i].next 表示从 j 出发的下一条边

示例：

如上图，这就是链式向前星存储图的方式了，其中编号为 -1 的边表示不存在，即没有其他的出边。

若我们需要新增一条从 i 到 j 的边，只需更新在 edges 数组内增加元素并且使其新增边的 next 等于 first[i] ，然后更新 first[i] 为新增的边的编号即可。

代码

#define MAX_VERTEX 100000
#define MAX_EDGE 100000

int cnt; // 边的数量

int first[MAX_VERTEX]; // first 数组

struct {
    int to;
    int weight;
    int next;
} edges[MAX_EDGE]; // 记录边

void initEdge() {
    cnt = 0;
    // 初始化，将 first 数组全初始化为 -1
    memset(first, 0xff, sizeof(first));
}

void addEdge(int from, int to, int weight) {
    edges[cnt] = {to, weight, first[from]}; // 新增边
    first[from] = cnt; // 更新 first 数组
    cnt++; // 边数增加
}

void traverseEdgeFrom(int v) {
    // 遍历从 v 出发的所有边
    for (int p = first[v]; p != -1; p = edges[p].next) {
        std::cout << "eNo: " << p << " to: " << edges[p].to << " weight: " << edges[p].weight << std::endl;
    }
}