链式前向星详解（C语言高效图存储结构入门指南）

为什么选择链式前向星？

• ✅ 内存连续，缓存友好
• ✅ 不需要动态内存分配（malloc/free）
• ✅ 支持快速遍历一个顶点的所有出边
• ✅ 代码简洁，适合C语言实现

核心数据结构

链式前向星主要由三个数组组成：

• head[u]：记录顶点 u 的第一条出边在 edge 数组中的下标
• to[i]：第 i 条边指向的终点
• nxt[i]：第 i 条边的下一条边在 edge 数组中的下标（形成链表）

此外，我们通常还会有一个 w[i] 数组来存储边权（如果是带权图）。

C语言实现步骤

1. 定义全局变量

#define MAXN 100005  // 最大顶点数#define MAXM 200005  // 最大边数（无向图需×2）int head[MAXN];      // head[u] 表示顶点u的第一条边的索引int to[MAXM];        // to[i] 表示第i条边的终点int nxt[MAXM];       // nxt[i] 表示第i条边的下一条边索引int w[MAXM];         // 边权（可选）int cnt = 0;          // 边计数器

2. 添加边的函数

void add_edge(int u, int v, int weight) {    to[cnt] = v;    w[cnt] = weight;    nxt[cnt] = head[u];   // 新边的下一条边是原来u的第一条边    head[u] = cnt++;      // 更新u的第一条边为当前边}

注意：每次添加新边时，它会被插入到链表的头部，因此遍历时顺序是“后进先出”。

3. 遍历某个顶点的所有出边

void traverse(int u) {    for (int i = head[u]; i != -1; i = nxt[i]) {        int v = to[i];        int weight = w[i];        printf("Edge from %d to %d with weight %d\n", u, v, weight);    }}

4. 初始化

在程序开始前，必须将 head 数组初始化为 -1，表示每个顶点都没有出边：

#include <string.h>memset(head, -1, sizeof(head));

完整示例：构建并遍历一个有向图

#include <stdio.h>#include <string.h>#define MAXN 10#define MAXM 20int head[MAXN];int to[MAXM], nxt[MAXM], w[MAXM];int cnt = 0;void add_edge(int u, int v, int weight) {    to[cnt] = v;    w[cnt] = weight;    nxt[cnt] = head[u];    head[u] = cnt++;}int main() {    memset(head, -1, sizeof(head));    // 添加边：0→1 (权5), 0→2 (权3), 1→2 (权2)    add_edge(0, 1, 5);    add_edge(0, 2, 3);    add_edge(1, 2, 2);    // 遍历顶点0的所有出边    for (int i = head[0]; i != -1; i = nxt[i]) {        printf("0 -> %d (weight: %d)\n", to[i], w[i]);    }    return 0;}

应用场景与优势总结

链式前向星广泛应用于各种图的遍历算法中，如深度优先搜索（DFS）、广度优先搜索（BFS）、Dijkstra最短路径、拓扑排序等。相比传统的邻接矩阵，它节省了大量空间；相比标准邻接表，它避免了指针操作，更适合C语言环境。

掌握链式前向星，是你迈向高效图算法实现的重要一步。无论你是算法竞赛选手，还是系统编程开发者，这一结构都值得你熟练掌握。

结语

通过本文，相信你已经对链式前向星有了清晰的理解。记住：多写代码、多调试，是掌握数据结构的最佳方式。现在就动手试试吧！