01 图的概念与建图

userId_undefined
吴老师
7月全勤卷王8月全勤卷王10月全勤卷王倔强青铜时间刺客空间掌握者

2026-06-30 18:47:55

发布于：广东

7阅读
0回复
0点赞

01 图的概念与建图

一、本阶段目标

学完本阶段，学生要能做到：

1. 知道什么是点、边、有向图、无向图、带权图。
2. 能判断一道题是否可以建图。
3. 会使用邻接矩阵、邻接表、带权邻接表。
4. 能根据数据范围选择存图方式。
5. 会解释“题目中的对象如何变成点，关系如何变成边”。

二、什么是图

图由两部分组成：

点 vertex：研究对象
边 edge：对象之间的关系

例如：

题面 点 边
城市道路 城市 道路
迷宫 格子 相邻可走关系
课程安排 课程 先修关系
朋友关系 人 认识关系
数字变换 每个数字 一次操作

图论题最核心的第一步：

把题目中的对象变成点，把对象之间的关系变成边。

三、有向图与无向图

1. 无向图

如果从 A 到 B 可以走，那么从 B 到 A 也可以走。

例如：双向道路、朋友关系、同学关系。

加入无向边：

vector<int> g[N];

g[u].push_back(v);
g[v].push_back(u);

2. 有向图

如果从 A 到 B 可以走，不一定能从 B 到 A。

例如：单行道、引用关系、先修课程关系。

加入有向边：

g[u].push_back(v);

3. 判断方向的小技巧

问自己一句：

这条关系能不能反过来用？

如果能，就是无向边；如果不能，就是有向边。

四、带权图

边上有数值，称为权值。

常见权值：

距离
时间
费用
风险
消耗
得分

带权邻接表：

vector<pair<int, int>> g[N]; // {终点, 边权}

g[u].push_back({v, w});

如果是无向带权边：

g[u].push_back({v, w});
g[v].push_back({u, w});

五、三种常见存图方式

1. 邻接矩阵

适合：点数小，或者需要快速判断两点是否有边。

int g[105][105];

初始化：

memset(g, 0, sizeof(g));

如果有边：

g[u][v] = 1;
g[v][u] = 1; // 无向图

优点：

判断 u 和 v 是否相连很快：O(1)
写法直观

缺点：

空间 O(n^2)
n 很大时不能用
遍历一个点的所有邻居需要扫一整行

适合数据：

n <= 1000 勉强可以
n <= 500 很舒服
n >= 10000 通常不能用邻接矩阵

2. 邻接表

适合：边数不太密，竞赛中最常用。

vector<int> g[N];

输入 m 条无向边：

for (int i = 1; i <= m; i++) {
    int u, v;
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
}

遍历 u 的所有邻居：

for (int v : g[u]) {
    // v 是 u 的一个邻居
}

优点：

空间 O(n + m)
遍历所有边总复杂度 O(n + m)
适合大多数图论题

缺点：

判断 u 和 v 是否直接相连不如邻接矩阵方便

3. 链式前向星

这是更传统的竞赛写法，适合边数很大、需要极致性能的题。但对深圳自招入门来说，先掌握 vector 邻接表即可。

了解即可：

struct Edge {
    int to, next, w;
} e[M];

int head[N], idx;

void add(int u, int v, int w) {
    e[++idx] = {v, head[u], w};
    head[u] = idx;
}

六、建图四步法

每道图论题都按这四步分析：

1. 点是什么？
2. 边是什么？
3. 边有没有方向？
4. 边有没有权值？

例 1：城市道路

点：城市
边：道路
方向：如果道路双向，就是无向图；如果单行，就是有向图
权值：道路长度或时间

例 2：迷宫

点：每个可走格子
边：上下左右相邻且都可走的格子之间连边
方向：通常无向
权值：每走一步代价为 1

例 3：课程安排

点：课程
边：如果 A 必须先于 B，则 A -> B
方向：有向
权值：通常没有；如果有学习时间，可以作为点权或边权

例 4：数字操作

题目：从数字 x 可以变成 x+1、x-1、2x，问从 A 到 B 最少几步。

点：每一个可能出现的数字
边：一次操作形成一条边
方向：如果操作可逆，不一定仍然直接建无向；通常按题目允许的操作建有向边
权值：每次操作代价为 1

这就是状态图。

七、模板：普通邻接表

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
vector<int> g[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u); // 无向图；有向图删掉这一行
    }

    for (int u = 1; u <= n; u++) {
        cout << u << ":";
        for (int v : g[u]) cout << ' ' << v;
        cout << '\n';
    }

    return 0;
}

八、模板：带权邻接表

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
vector<pair<int, int>> g[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }

    for (int u = 1; u <= n; u++) {
        for (auto [v, w] : g[u]) {
            cout << u << " -> " << v << ", weight = " << w << '\n';
        }
    }

    return 0;
}

九、排序邻接表

有些题要求“编号小的先访问”，例如 P5318 查找文献。

做法：建完图后排序。

for (int i = 1; i <= n; i++) {
    sort(g[i].begin(), g[i].end());
}

注意：不要每插入一条边就排序，那样会很慢。

十、课堂例题设计

例题 1：朋友关系

有 n 个学生，m 对朋友关系，朋友关系是双向的。请输出每个学生的朋友编号。

建模：

点：学生
边：朋友关系
图：无向图
权值：无

例题 2：博客引用

文章 A 引用了文章 B，读 A 后可以继续读 B。

建模：

点：文章
边：A -> B
图：有向图
权值：无

例题 3：城市道路

每条路有长度，问如何存储。

建模：

点：城市
边：道路
图：可能无向，也可能有向
权值：长度

十一、练习题

题号 题名 训练点 建议
B3643 图的存储 邻接矩阵 + 邻接表 必做
B3600 图的代数表示 图的表示方式 选做
P5318 查找文献 建图 + DFS/BFS 顺序 必做
P3916 图的遍历 反向建图思想 提高

链接：

https://www.luogu.com.cn/problem/B3643
https://www.luogu.com.cn/problem/B3600
https://www.luogu.com.cn/problem/P5318
https://www.luogu.com.cn/problem/P3916

十二、本阶段小结

本阶段不要急着追求算法。学生必须先形成图论建模意识：

对象是点
关系是边
限制决定方向
代价决定权值
数据范围决定存图方式

只要这一步做对，后面的 DFS、BFS、最短路才有意义。

userId_undefined
去预览
0/2000
暂无数据

这里空空如也

热门讨论