链式前向星是一种用于表示图的数据结构，它能够有效地存储和访问图中的边信息。这种方法基于邻接表的思想，但使用数组而不是链表来实现，从而在某些情况下提供更快的访问速度和更小的空间消耗。下面是关于链式前向星的一些总结：

数据结构

h[N]：头节点数组，用于记录每个节点的第一条边在e数组中的位置索引。初始化时应全部设置为-1，表示没有边。 e[N]：存储每条边的终点节点编号。 ne[N]：存储与当前边同起点的下一条边的索引位置。 idx：计数器，用于给每条边分配一个唯一的索引。

加边操作

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

这段代码的意思是添加一条从节点a到节点b的有向边。具体过程如下：

将b存入e数组中当前idx的位置。 将该位置上的链表指针（即ne[idx]）指向当前a节点第一条边的位置（h[a]）。 更新a节点第一条边的位置为当前边的位置（idx），然后idx自增。

遍历操作

for (int i = h[t]; i != -1; i = ne[i])
{
    int j = e[i];
    // 在这里对边(i, j)进行处理
}

遍历时，从t节点出发，首先找到t节点的第一条边（通过h[t]）。然后沿着链式结构遍历所有以t为起点的边。对于每条边，可以获取其终点节点j，并对其进行相应的处理。

总结

这种方法使得加边和遍历边的操作都非常高效，时间复杂度均为O(1)。此外，由于它只使用了简单的数组，所以在内存占用方面也非常紧凑。链式前向星非常适合用于实现图的深度优先搜索(DFS)、广度优先搜索(BFS)以及其他需要频繁访问图中边的应用场景。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com