GESP 7级

图的存储

7级 · DP/图论/搜索

📖 图是什么？

图（Graph）由节点（顶点）和边组成。节点代表事物（城市、人物、网页），边代表事物之间的关系（道路、友谊、链接）。
📝 生活中的图
  • 社交网络：人是节点，好友关系是边
  • 城市地图：城市是节点，公路是边（边有权重=距离）
  • 网页链接：网页是节点，超链接是边
  • 课程依赖：课程是节点，"先修关系"是有向边
💡 为什么重要？
图是计算机科学中最重要的数据结构之一。社交网络分析、地图导航、网络路由……都基于图。学会图的存储，才能学习图上的搜索、最短路、最小生成树等算法。GESP 7级中，图论是核心考点。
📋 前置知识
  • 二维数组：int g[N][N] 的声明和使用
  • vector：vector<int>、vector<pair<int,int>> 的使用
  • pair：pair<int,int> 存储两个值

📐 两种存储方式

邻接矩阵

用二维数组 g[i][j] 存边

空间 O(n²)，查边 O(1)

适合：稠密图（边很多）

邻接表

每个节点存一个链表/向量

空间 O(n+m)，查边 O(degree)

适合：稀疏图（边较少）

🔢 方式1：邻接矩阵

用一个二维数组，g[i][j] = 从节点i到节点j的边的权重。如果没有边，值为0或无穷大。

💻 邻接矩阵代码（逐行注释）
#include <iostream>
#include <cstring>  // memset
using namespace std;

const int N = 105;
int g[N][N];  // 邻接矩阵：g[i][j] = 从i到j的边权
              // g[i][j] = 0 表示没有边（或用INF表示无边）
              // g[i][j] = w 表示i到j有一条权为w的边

int main() {
    int n, m;  // n个节点，m条边
    cin >> n >> m;

    // 初始化：memset将所有字节设为0
    memset(g, 0, sizeof(g));

    // 读入m条边
    for (int i = 0; i < m; i++) {
        int u, v, w;    // 从u到v，权为w
        cin >> u >> v >> w;
        g[u][v] = w;    // 在矩阵中记录这条边
        // 如果是无向图，还要加：g[v][u] = w;
    }

    // 查找从u出发的所有邻居
    for (int v = 1; v <= n; v++) {
        if (g[u][v] != 0) {   // 如果u到v有边
            cout << "u到" << v << "的边权: " << g[u][v] << endl;
        }
    }

    return 0;
}

🔢 方式2：邻接表（推荐）

每个节点维护一个列表，存储它所有邻居和对应的边权。

💻 vector邻接表代码（逐行注释）
#include <iostream>
#include <vector>
using namespace std;

const int N = 105;
vector<pair<int,int>> adj[N];  // adj[u] = 节点u的所有邻居
                                  // pair{v, w} 表示u到v有一条权为w的边

int main() {
    int n, m;  // n个节点，m条边
    cin >> n >> m;

    // 读入m条边
    for (int i = 0; i < m; i++) {
        int u, v, w;    // 从u到v，权为w
        cin >> u >> v >> w;
        adj[u].push_back({v, w});   // u的邻居列表中加入v
        // 如果是无向图，还要加：adj[v].push_back({u, w});
    }

    // 遍历节点u的所有邻居
    // C++17结构化绑定写法
    for (auto [v, w] : adj[u]) {
        cout << "u到" << v << "的边权: " << w << endl;
    }

    // 传统写法（C++11兼容）
    // for (auto& edge : adj[u]) {
    //     int v = edge.first;   // 邻居节点编号
    //     int w = edge.second;  // 边权
    //     cout << "u到" << v << "的边权: " << w << endl;
    // }

    return 0;
}

🔢 方式3：链式前向星（竞赛常用）

💡 什么是链式前向星？
链式前向星是邻接表的数组实现，用数组模拟链表。在竞赛中因为速度快、内存可控而被广泛使用。考试中用vector邻接表更直观，但了解链式前向星有助于理解底层原理。
💻 链式前向星代码
const int N = 105, M = 10005;
int head[N];    // head[u] = 节点u的第一条边的编号
int to[M];      // to[e] = 第e条边的终点
int w[M];       // w[e] = 第e条边的权值
int nxt[M];     // nxt[e] = 与第e条边同起点的下一条边的编号
int cnt = 0;    // 边的计数器

void add(int u, int v, int weight) {
    to[cnt] = v;          // 记录终点
    w[cnt] = weight;      // 记录权值
    nxt[cnt] = head[u];   // 新边的next指向旧的第一条边
    head[u] = cnt++;      // 更新head为新边
}

// 遍历节点u的所有邻居
for (int e = head[u]; e != -1; e = nxt[e]) {
    int v = to[e];        // 邻居节点
    int weight = w[e];    // 边权
}

📊 三种方式对比

📝 选哪个？
  • 考试/平时练习：用 vector邻接表，代码简洁、直观
  • n很小（≤100）且图很密：用邻接矩阵，代码最简单
  • 竞赛/追求速度：用链式前向星，常数最小

🚨 易错点

⚠️ 常见错误汇总
  1. 无向图忘记加反向边：无向图的边要加两次！比如 u→v 和 v→u 都要记录。
  2. 邻接矩阵初始化：如果用0表示"无边"，那边权不能是0。通常用-1或INF表示无边。
  3. 节点编号从0还是1开始：看清题目！有些题目节点从1编号，有些从0。
  4. 遍历邻居时用auto [v,w]：确保编译器支持C++17。如果不支持，用 pair 的 first/second。
  5. 链式前向星head初始化为-1：不是0！-1表示"没有边"。
  6. 数组大小：N要开够（通常105或1005），M是边数（通常2*M因为无向图要存两次）。

🎯 练习建议

📝 循序渐进练习路径
  1. 先掌握vector邻接表：这是最常用的，能解决大部分题目。
  2. 做图的入门题：
    • P5318 查找文献（DFS/BFS遍历图）
    • P3366 最小生成树（Kruskal，需要并查集）
  3. 理解无向图和有向图的区别：无向图的边是双向的，有向图的边是单向的。
  4. 尝试链式前向星：如果想参加竞赛，可以学习这种写法。
← 上一个：贪心策略 📖 返回主目录 下一个：图的DFS/BFS →