C++链式前向星详解（图的高效存储方法入门教程）

链式前向星的核心结构

要实现链式前向星，我们需要定义两个核心部分：

1. head[] 数组：记录每个顶点第一条出边在边数组中的下标
2. 边结构体数组 edge[]：每条边包含目标顶点、边权（可选）、指向下一条边的索引

下面是一个完整的 C++ 实现示例：

#include <iostream>#include <cstring>using namespace std;const int MAXN = 100010;  // 最大顶点数const int MAXM = 200010;  // 最大边数（无向图需 ×2）struct Edge {    int to;       // 边的终点    int w;        // 边的权重（可选，若无权图可省略）    int next;     // 指向下一条边的索引} edge[MAXM];int head[MAXN];   // head[i] 表示顶点 i 的第一条出边在 edge 中的下标int cnt = 0;      // 边的计数器// 添加一条从 u 到 v 的有向边，权重为 wvoid addEdge(int u, int v, int w = 0) {    edge[cnt].to = v;    edge[cnt].w = w;    edge[cnt].next = head[u];  // 新边的 next 指向原来的头边    head[u] = cnt;             // 更新 head[u] 为新边的索引    cnt++;}// 遍历从顶点 u 出发的所有边void traverse(int u) {    for (int i = head[u]; i != -1; i = edge[i].next) {        int v = edge[i].to;        int w = edge[i].w;        cout << "从 " << u << " 到 " << v << "，权重为 " << w << endl;    }}int main() {    // 初始化 head 数组为 -1（表示没有出边）    memset(head, -1, sizeof(head));        // 示例：构建一个简单图    addEdge(1, 2, 5);    addEdge(1, 3, 3);    addEdge(2, 4, 2);        // 遍历顶点 1 的所有出边    traverse(1);        return 0;}

关键点解析

1. 初始化：必须将 head[] 数组初始化为 -1，表示每个顶点初始时没有出边。

2. 插入顺序：新加入的边会插入到链表头部，因此遍历时边的顺序与输入顺序相反。但这通常不影响算法正确性。

3. 无向图处理：若要表示无向图，只需对每条边调用两次 addEdge，例如 addEdge(u, v, w); addEdge(v, u, w);。

为什么选择链式前向星？

对于刚接触C++图论基础的新手来说，链式前向星可能看起来比 vector 邻接表复杂，但它在以下场景中表现优异：

• 处理百万级边的稀疏图（如网络拓扑、社交关系）
• 需要极致性能的算法竞赛（如 ACM/ICPC）
• 内存受限环境（避免 vector 动态扩容带来的碎片）

掌握链式前向星实现，不仅能提升你的 C++ 编程能力，还能为后续学习 Dijkstra、SPFA、DFS 等图算法打下坚实基础。

总结

本文详细介绍了C++链式前向星的原理、实现方式和使用技巧。作为一种高效的图的存储方法，它在实际开发和算法竞赛中被广泛应用。希望这篇教程能帮助你轻松入门，不再对图的存储感到困惑！

动手试试吧！修改上面的代码，构建你自己的图结构，体验链式前向星的强大之处。