图论基础与邻接表存图

信息学奥赛入门讲义。本节课只解决两个问题：图是什么，以及怎样用邻接表把图存进程序。

一、图是什么

图用来表示“若干对象以及对象之间的关系”。

• 对象叫作顶点，也常简称为点；
• 对象之间的关系叫作边；
• 顶点数通常记为 $n$；
• 边数通常记为 $m$。

例如，在城市交通图中：

• 每座城市是一个顶点；
• 两座城市之间的道路是一条边；
• 道路长度可以作为边权。

做题时，首先要确定：题目中的什么事物是点，什么关系是边。

---

二、最重要的基本概念

1. 无向图和有向图

无向边没有方向。

1 -------- 2

它表示 1 和 2 直接相连，既可以从 1 到 2，也可以从 2 到 1。

有向边有明确方向。

1 -------> 2

它只表示可以从 1 直接到 2，不代表可以从 2 回到 1。

双向道路通常建成无向图；关注关系、任务先后关系通常建成有向图。

2. 无权图和带权图

无权图只关心两个点是否相连。

带权图的每条边还有一个数值，叫作边权。边权可以表示：

• 距离；
• 时间；
• 费用；
• 危险程度。

1 -------- 2
     7

可以表示 1 到 2 的道路长度为 7。

3. 度、入度和出度

无向图中，与顶点 $u$ 相连的边数叫作 $u$ 的度。

例如，顶点 2 分别与 1、3、4 相连，那么顶点 2 的度为 3。

无向图中，所有顶点的度数之和等于 $2m$。因为每条边会在两个端点各被计算一次。

有向图中：

• 指向顶点 $u$ 的边数叫作 $u$ 的入度；
• 从顶点 $u$ 出发的边数叫作 $u$ 的出度。

4. 路径、环和连通

沿着若干条首尾相接的边，从一个点走到另一个点，形成一条路径。

如果从一个点出发，沿着若干条边最后又回到起点，就形成了一个环。

无向图中，如果任意两个顶点之间都有路径，这张图就是连通图。

现阶段记住这些概念即可，后续学习图的遍历和最短路时还会反复使用。

---

三、为什么需要存图

人在纸上可以直接看出哪些点相连，但程序看不到图形。我们必须把每条边转换成程序能够保存的数据。

假设有下面这张无向图：

      1
     / \
    2---3
    |   |
    4   5

它有 5 个顶点和 5 条边：

1-2
1-3
2-3
2-4
3-5

我们暂时不考虑怎样搜索，只考虑一个最基本的问题：

对于每个顶点，它直接连接了哪些顶点？

逐个顶点列出来：

1 的邻居：2、3
2 的邻居：1、3、4
3 的邻居：1、2、5
4 的邻居：2
5 的邻居：3

这就是邻接表。

---

四、怎样理解邻接表

可以把邻接表理解为：

每个顶点都有一张自己的“邻居名单”。

对于上面的图：

顶点	邻居名单
1	2，3
2	1，3，4
3	1，2，5
4	2
5	3

程序中需要很多张长度不同的名单：

• 顶点 1 的名单长度是 2；
• 顶点 2 的名单长度是 3；
• 顶点 4 的名单长度是 1。

vector 正好可以保存一张长度不固定的名单。因此可以让每个顶点拥有一个 vector。

vector<vector<int>> graph(n + 1);

这行代码最容易让初学者觉得抽象，可以把它拆开理解：

• 外层 vector：保存所有顶点的邻居名单；
• 内层 vector<int>：保存某一个顶点的所有邻居；
• graph[u]：顶点 u 的整张邻居名单；
• graph[u][i]：顶点 u 的第 i 个邻居。

对于刚才的图，程序中的数据可以想象成：

graph[0] = { }        // 编号 0 不使用
graph[1] = {2, 3}
graph[2] = {1, 3, 4}
graph[3] = {1, 2, 5}
graph[4] = {2}
graph[5] = {3}

注意：graph[u] 不是一个整数，而是一个 vector<int>。

---

五、无向图怎样加边

假设读入一条无向边：

2 4

它表示 2 和 4 互相连接，所以：

• 4 是 2 的邻居；
• 2 也是 4 的邻居。

程序必须保存两个方向：

graph[2].push_back(4);
graph[4].push_back(2);

写成一般形式：

int u, v;
cin >> u >> v;

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

假设开始时所有名单都是空的，依次加入前面例图的 5 条边。

加入 1-2：

graph[1] = {2}
graph[2] = {1}

再加入 1-3：

graph[1] = {2, 3}
graph[3] = {1}

再加入 2-3、2-4、3-5，最终得到：

graph[1] = {2, 3}
graph[2] = {1, 3, 4}
graph[3] = {1, 2, 5}
graph[4] = {2}
graph[5] = {3}

一条无向边会在邻接表中出现两次。因此输入有 $m$ 条无向边时，所有邻居名单的长度之和是 $2m$。

---

六、有向图怎样加边

假设读入一条有向边：

2 4

表示 2 -> 4，只说明可以从 2 直接走到 4。

所以只保存一个方向：

graph[2].push_back(4);

一般形式：

int u, v;
cin >> u >> v;

graph[u].push_back(v);

此时 4 会出现在 graph[2] 中，但 2 不会自动出现在 graph[4] 中。

输入有 $m$ 条有向边时，所有邻居名单的长度之和是 $m$。

---

七、完整的无权无向图存图程序

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

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

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

    vector<vector<int>> graph(n + 1);

    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;

        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    // 输出每个顶点的邻居名单
    for (int u = 1; u <= n; ++u) {
        cout << u << ":";

        for (int v : graph[u]) {
            cout << ' ' << v;
        }

        cout << '\n';
    }

    return 0;
}

输入：

5 5
1 2
1 3
2 3
2 4
3 5

输出：

1: 2 3
2: 1 3 4
3: 1 2 5
4: 2
5: 3

邻接表中邻居的顺序通常就是加边顺序，不一定从小到大。

如果题目要求邻居按照编号从小到大排列，可以在建图后排序：

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

题目没有顺序要求时，不需要排序。

---

八、怎样遍历一个点的所有邻居

下面的循环表示：依次取出 graph[u] 中保存的每一个邻居。

for (int v : graph[u]) {
    cout << v << ' ';
}

例如：

graph[2] = {1, 3, 4}

执行：

for (int v : graph[2]) {
    cout << v << ' ';
}

会依次输出：

1 3 4

这里的 v 每次代表一个邻居，不是边的编号，也不是循环下标。

如果确实需要使用下标，也可以写：

for (int i = 0; i < graph[u].size(); ++i) {
    int v = graph[u][i];
    cout << v << ' ';
}

只需要访问邻居时，范围 for 更简洁。

---

九、怎样得到顶点的度

无向图中，顶点 u 的邻居数量就是它的度：

int degree = graph[u].size();

例如：

graph[2] = {1, 3, 4}

所以顶点 2 的度是 3。

有向图中，graph[u].size() 表示顶点 u 的出度，因为 graph[u] 保存的是从 u 出发的边。

如果还需要入度，应在读边时单独统计：

vector<int> inDegree(n + 1, 0);

graph[u].push_back(v);
++inDegree[v];

---

十、带权图怎样存

无权邻接表只需要记录邻居编号：

2 的邻居是 4

带权图还要记录边权：

2 到 4 的边权是 7

因此邻居名单中的每一项不能只有一个整数，而要同时保存：

• 边的终点 to；
• 边的权值 weight。

定义边结构体：

struct Edge {
    int to;
    long long weight;
};

邻接表改成：

vector<vector<Edge>> graph(n + 1);

无向带权边 u-v、边权为 w：

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

假设有边：

1 2 7
1 3 4

那么可以把 graph[1] 想象成：

graph[1] = {(2, 7), (3, 4)}

含义是：

• 1 可以直接到 2，边权为 7；
• 1 可以直接到 3，边权为 4。

遍历带权邻接表：

for (const Edge &edge : graph[u]) {
    int v = edge.to;
    long long w = edge.weight;

    cout << u << " -> " << v
         << ", weight = " << w << '\n';
}

---

十一、完整的带权无向图存图程序

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

struct Edge {
    int to;
    long long weight;
};

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

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

    vector<vector<Edge>> graph(n + 1);

    for (int i = 0; i < m; ++i) {
        int u, v;
        long long w;
        cin >> u >> v >> w;

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

    for (int u = 1; u <= n; ++u) {
        cout << "vertex " << u << ":\n";

        for (const Edge &edge : graph[u]) {
            cout << "  to = " << edge.to
                 << ", weight = " << edge.weight
                 << '\n';
        }
    }

    return 0;
}

这里使用 long long 保存边权，是为了避免边权或以后计算的路径长度超过 int 范围。

---

十二、另一种常见声明方式

个人代码中还经常出现：

const int MAX_N = 200000 + 5;
vector<int> graph[MAX_N];

它同样表示“每个顶点有一张邻居名单”。区别是：

vector<vector<int>> graph(n + 1);

按照本次输入的 n 动态确定顶点数量；而：

vector<int> graph[MAX_N];

提前按照最大数据范围开好数组。

两种写法都可以。课堂入门更推荐 vector<vector<int>> graph(n+1)，因为它更直接体现“外层是所有顶点，内层是每个点的邻居名单”。

---

十三、邻接表的复杂度

1. 空间复杂度

邻接表需要保存：

• $n$ 个顶点的名单；
• 所有边对应的邻接记录。

所以空间复杂度是：

O(n + m)

无向边虽然存两次，但 $2m$ 在复杂度中仍写作 $O(m)$。

2. 枚举邻居的复杂度

枚举顶点 u 的所有邻居，需要的时间与 u 的度数有关：

O(degree(u))

邻居少就遍历得快，不需要检查与 u 不相连的顶点。

3. 查询某条边是否存在

普通邻接表不能直接在 $O(1)$ 时间内判断 u-v 是否存在。通常需要遍历 graph[u]：

bool found = false;

for (int v : graph[u]) {
    if (v == target) {
        found = true;
        break;
    }
}

这也是邻接表“适合枚举邻居，但不擅长直接查询任意两点”的特点。

---

十四、重边和自环

1. 重边

如果输入中多次出现同一对顶点，就会在邻接表中保存多次：

graph[1] = {2, 2, 2}

这表示 1 和 2 之间有三条边。很多图论算法允许邻接表直接保留重边，不要在题目没有要求时擅自去重。

2. 自环

自环是起点和终点相同的边，例如 3-3。

题目通常会说明是否可能出现自环。如果不保证没有，就要根据具体问题判断自环是否需要保留。

---

十五、最常见的错误

1. 无向边只存一次

错误：

graph[u].push_back(v);

正确：

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

2. 有向边错误地存成两个方向

如果题目给的是 u -> v，就不能擅自添加 v -> u。

3. 顶点编号越界

顶点编号是 1..n 时，邻接表要开到 n+1：

vector<vector<int>> graph(n + 1);

4. 混淆 graph[u] 和 graph[u][i]

• graph[u] 是一整张邻居名单；
• graph[u][i] 才是其中的一个邻居编号。

5. 带权图只保存终点，忘记边权

带权图应保存 {终点, 边权}，不能只保存终点。

6. 认为邻接表会自动排序

邻接表默认按照加边顺序保存。需要编号有序时，应主动排序。

7. 把邻居编号当成循环下标

for (int v : graph[u])

这里的 v 是邻居编号，不是 0,1,2... 这样的下标。

---

十六、课堂检查题

给出无向图：

6 6
1 2
1 4
2 3
2 5
3 5
5 6

让学生完成：

1. 画出这张图；
2. 手写 graph[1] 到 graph[6]；
3. 写出每个顶点的度；
4. 检查所有度数之和是否等于 2*m；
5. 写出无向图邻接表建图代码；
6. 把每条边改成有向边后，重新写邻接表；
7. 给每条边增加边权，再改成带权邻接表。

---

十七、本节课必须掌握的内容

1. 图由顶点和边组成；边可能有方向，也可能有权值。
2. 邻接表就是“每个顶点的一张邻居名单”。
3. graph[u] 保存顶点 u 的所有邻居。
4. 无向边存两个方向，有向边只存一个方向。
5. 带权邻接表中的每一项要同时保存终点和边权。
6. 使用范围 for 可以枚举一个顶点的所有邻居。
7. 邻接表空间复杂度为 $O(n+m)$。

学生如果能够不看模板写出无权和带权邻接表，并能解释每一行代码的含义，就达到了本节课的目标。