C++前向星图详解（高效图存储结构入门指南）

前向星的基本原理

前向星主要使用两个数组：head[] 和 edge[]（或称 e[]）。

• head[u]：表示顶点 u 的第一条出边在 edge 数组中的下标。
• edge[i]：是一个结构体，通常包含目标顶点 to、边权 w（如果有的话）以及指向下一条边的索引 next。

C++前向星图的实现步骤

下面我们一步步实现一个完整的前向星图结构。

1. 定义边结构体

struct Edge {    int to;      // 边的终点    int w;       // 边的权重（可选，无权图可省略）    int next;    // 指向下一条边的索引};

2. 声明全局变量

const int MAXN = 100005;  // 最大顶点数const int MAXM = 200005;  // 最大边数（有向图）或两倍（无向图）Edge edge[MAXM];          // 边数组int head[MAXN];           // head数组int cnt = 0;              // 当前边的计数器

3. 初始化图

void init() {    memset(head, -1, sizeof(head));  // 将head初始化为-1，表示没有出边    cnt = 0;}

4. 添加边

void addEdge(int u, int v, int w = 0) {    edge[cnt].to = v;    edge[cnt].w = w;    edge[cnt].next = head[u];  // 新边的next指向原来u的第一条边    head[u] = cnt;             // 更新u的第一条边为当前边    cnt++;                     // 边计数器加一}

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

void traverse(int u) {    for (int i = head[u]; i != -1; i = edge[i].next) {        int v = edge[i].to;        int weight = edge[i].w;        // 处理边 (u -> v)，权重为 weight        cout << "From " << u << " to " << v << ", weight: " << weight << endl;    }}

完整示例代码

下面是一个完整的可运行示例，演示如何构建并遍历一个简单的有向图。

#include <iostream>#include <cstring>using namespace std;const int MAXN = 1005;const int MAXM = 2005;struct Edge {    int to, w, next;};Edge edge[MAXM];int head[MAXN];int cnt;void init() {    memset(head, -1, sizeof(head));    cnt = 0;}void addEdge(int u, int v, int w = 0) {    edge[cnt].to = v;    edge[cnt].w = w;    edge[cnt].next = head[u];    head[u] = cnt++;}int main() {    init();        // 构建图：3个顶点，3条边    addEdge(1, 2, 5);    addEdge(1, 3, 10);    addEdge(2, 3, 3);        // 遍历顶点1的所有出边    cout << "Edges from vertex 1:" << endl;    for (int i = head[1]; i != -1; i = edge[i].next) {        cout << "1 -> " << edge[i].to << ", weight = " << edge[i].w << endl;    }        return 0;}

为什么选择前向星？

相比于传统的邻接表（使用 vector 或链表），前向星实现具有以下优势：

• 内存连续，缓存友好，访问速度快；
• 避免频繁动态内存分配（如 new 或 push_back）；
• 在竞赛编程中，常用于处理大规模稀疏图，效率极高。

总结

通过本教程，你应该已经掌握了 C++前向星图 的基本原理与实现方法。这种图的存储结构特别适合处理边数较多但顶点数相对较少的稀疏图，在算法竞赛和工程实践中都有广泛应用。希望你能将所学应用到实际的 C++图算法 编程中！