C语言前向星图详解（小白也能学会的高效图存储方法）

前向星的核心结构

要实现前向星，我们需要定义以下几个关键数组：

• head[u]：表示顶点 u 的第一条出边在 edge 数组中的下标。
• edge[i].to：第 i 条边指向的终点。
• edge[i].next：与当前边起点相同的上一条边在 edge 数组中的下标。
• edge[i].w（可选）：边的权重（用于带权图）。

C语言实现前向星

下面我们用 C 语言完整实现一个前向星图结构，并演示如何添加边和遍历邻接点。

#include <stdio.h>#include <string.h>#define MAXN 1000   // 最大顶点数#define MAXM 10000  // 最大边数// 边结构体struct Edge {    int to;         // 终点    int next;       // 下一条边的索引    int w;          // 权重（可选）} edge[MAXM];int head[MAXN];     // 每个顶点的第一条边索引int cnt = 0;        // 边计数器// 添加一条从 u 到 v 的有向边（权重为 w）void addEdge(int u, int v, int w) {    edge[cnt].to = v;    edge[cnt].w = w;    edge[cnt].next = head[u];    head[u] = cnt;    cnt++;}// 遍历顶点 u 的所有邻接点void printAdj(int u) {    printf("顶点 %d 的邻接点：", u);    for (int i = head[u]; i != -1; i = edge[i].next) {        printf("%d(权:%d) ", edge[i].to, edge[i].w);    }    printf("\n");}int main() {    // 初始化 head 数组为 -1（表示无出边）    memset(head, -1, sizeof(head));    // 添加几条测试边    addEdge(1, 2, 5);    addEdge(1, 3, 10);    addEdge(2, 4, 3);    addEdge(3, 4, 1);    // 打印邻接信息    printAdj(1);    printAdj(2);    printAdj(3);    return 0;}  

代码解析

在上述代码中：

• 我们用 head 数组记录每个顶点的第一条出边位置。
• 每次调用 addEdge 时，新边被插入到链表头部（头插法），并更新 head[u]。
• 遍历时，从 head[u] 开始，通过 edge[i].next 依次访问所有出边，直到 -1（表示链表结束）。

为什么选择前向星？

相比其他图存储方式，前向星存图具有以下优势：

• 内存连续：全部使用静态数组，缓存友好。
• 无需指针：适合 C 语言环境，尤其在 ACM/ICPC 等竞赛中广泛使用。
• 高效遍历：每个顶点的出边可以 O(degree) 时间内遍历完毕。

需要注意的是，前向星通常用于有向图。若需存储无向图，只需对每条无向边 (u, v) 调用两次 addEdge：一次 u→v，一次 v→u。

总结

通过本教程，你应该已经掌握了 C语言图存储 中非常实用的前向星方法。无论是学习前向星算法，还是准备算法竞赛，这种结构都能为你提供高效、稳定的图表示能力。建议你动手敲一遍代码，加深理解！

关键词回顾：C语言前向星、前向星存图、C语言图存储、前向星算法