图的存储
一、课上练习
编程练习
- 图的存储: L3321
二、知识总结
✨ 核心思想
在计算机科学中，图的存储是关键的一环，因为它直接影响到对图的操作，如遍历、查找和优化算法的效率。主要有三种方法来存储图：邻接矩阵、邻接表和边集数组。每种方法有其优势和特定使用场景。
✨ 邻接矩阵
邻接矩阵是一个二维数组，其中的元素 matrix[i][j] 表示顶点 i 和顶点 j 之间是否存在边。如果图是无向的，这个矩阵将是对称的。在有向图中，matrix[i][j] 表示从顶点 i 到顶点 j 的有向边。
下面的代码演示了使用邻接矩阵存储无向图的方式：
1#include<iostream>
2#include<vector>
3#include<algorithm>
4using namespace std;
5
6int main() {
7 int n = 0; // 图的顶点数
8 int m = 0; // 图的边数
9 cin >> n >> m; // 读取顶点数和边数
10 // 初始化邻接矩阵，大小为n*n，初始值为0
11 vector<vector<int>> adjMatrix(n, vector<int>(n, 0));
12
13 for (int i = 0; i < m; i++) { // 遍历所有的边
14 int u = 0, v = 0;
15 cin >> u >> v; // 读取每条边的两个顶点
16 adjMatrix[u][v] = 1; // 在邻接矩阵中标记顶点u和v是相连的
17 adjMatrix[v][u] = 1; // 无向图是双向的
18 }
19 // 打印邻接矩阵
20 for (int i = 0; i < n; i++) {
21 for (int j = 0; j < n; j++) {
22 cout << adjMatrix[i][j] << (j == n - 1 ? '\n' : ' ');
23 }
24 }
25 return 0;
26}优点：
- 简单直观，容易实现
- 访问任意两个顶点间是否存在边的操作非常快，时间复杂度为 O(1)
缺点：
- 对于稀疏图（边的数量远小于顶点对的数量），这种表示方法非常浪费空间
- 添加或删除顶点效率较低
适用场景：
- 当图比较密集，即边的数量接近顶点数的平方时
- 需要频繁检查两个顶点之间是否存在边的操作时
✨ 邻接表
邻接表使用一个数组或列表的数组来表示每个顶点的邻接顶点。数组的每个位置 i 包含一个列表，这个列表包含所有与顶点 i 直接相连的顶点。
优点：
- 空间效率更高，尤其适用于稀疏图
- 添加和删除边非常高效
缺点：
- 检查两个顶点之间是否存在边的操作较慢，需要 O(degree(v)) 时间
- 某些操作可能需要更复杂的数据结构来优化性能
适用场景：
- 稀疏图，即边的数量远小于顶点对的可能组合数
- 需要频繁地添加或删除边
下面的代码演示了使用邻接表存储无向图的方式：
1#include<iostream>
2#include<vector>
3#include<algorithm>
4using namespace std;
5
6int main() {
7 int n = 0; // 图的顶点数
8 int m = 0; // 图的边数
9 cin >> n >> m; // 读取顶点数和边数
10 // 初始化邻接表，大小为n
11 vector<vector<int>> adjList(n);
12 for (int i = 0; i < m; i++) { // 遍历所有的边
13 int u = 0, v = 0;
14 cin >> u >> v; // 读取每条边的两个顶点
15 // 在邻接表中添加顶点v到u的列表，以及u到v的列表
16 adjList[u].push_back(v);
17 adjList[v].push_back(u);
18 }
19 // 打印邻接表
20 for (int i = 0; i < n; i++) {
21 sort(adjList[i].begin(), adjList[i].end()); // 对邻接表进行排序
22 for (int j = 0; j < adjList[i].size(); j++) {
23 cout << adjList[i][j] << (j + 1 == adjList[i].size() ? '\n' : ' ');
24 }
25 }
26 return 0;
27}✨ 边集数组
边集数组是一个边的列表，每个边由一对顶点（或有向边的起点和终点）组成。这种表示方法简单列出了所有边的信息。
优点：
- 实现简单，直接列出所有边，容易理解和操作
- 对于所有与边相关的操作，如迭代所有边，都非常高效
缺点：
- 检查两个顶点间是否存在边非常低效，需要 O(E) 时间，其中 E 是边的数量
- 无法直接访问特定顶点的邻接信息，除非遍历整个边列表
适用场景：
- 当问题主要涉及边的迭代处理，而非顶点的直接操作
- 图的表示更偏向数据处理而非高效的图算法执行
下面的代码演示了使用边集数组存储带权图的方式：
1#include <iostream>
2#include <vector>
3using namespace std;
4
5// 定义一个结构体，用于表示图中的一条边
6struct Edge {
7 int from; // 边的起点
8 int to; // 边的终点
9 int weight; // 边的权重
10};
11
12// 主函数
13int main() {
14 // 创建一个vector来存储边
15 vector<Edge> edges;
16
17 // 添加边到图中
18 edges.emplace_back(Edge{0, 1, 10}); // 从顶点0到顶点1，权重为10
19 edges.emplace_back(Edge{0, 2, 5}); // 从顶点0到顶点2，权重为5
20 edges.emplace_back(Edge{1, 3, 6}); // 从顶点1到顶点3，权重为6
21 edges.emplace_back(Edge{2, 3, 15}); // 从顶点2到顶点3，权重为15
22
23 // 打印所有边的信息
24 for (int i = 0; i < edges.size(); ++i) {
25 cout << "Edge from " << edges[i].from << " to " << edges[i].to << " with weight " << edges[i].weight << endl;
26 }
27
28 return 0;
29}✨ 三种存储方式总结
每种图的存储方式都有其特定的优势和局限性。选择哪种方法取决于图的类型（稀疏或密集），以及你将要执行的操作类型（是否需要频繁地检查顶点间的连接，或是频繁地添加和删除边）。理解这些差异能帮助开发者根据实际需求选择最适合的存储方法，以优化性能和资源使用。
✨ 执行示例
下面用同一个图，展示三种存储方式的具体存储结果。
示例图（无向图）： 4 个顶点（0-3），5 条边
0 -- 1
| / |
| / |
2 -- 3边：(0,1), (0,2), (1,2), (1,3), (2,3)
邻接矩阵存储
0 1 2 3
0 [0, 1, 1, 0]
1 [1, 0, 1, 1]
2 [1, 1, 0, 1]
3 [0, 1, 1, 0]读入过程：
- 读入边 (0,1)：设 matrix[0][1]=1, matrix[1][0]=1
- 读入边 (0,2)：设 matrix[0][2]=1, matrix[2][0]=1
- 读入边 (1,2)：设 matrix[1][2]=1, matrix[2][1]=1
- 读入边 (1,3)：设 matrix[1][3]=1, matrix[3][1]=1
- 读入边 (2,3)：设 matrix[2][3]=1, matrix[3][2]=1
查询： 0 和 3 是否相邻？查看 matrix[0][3] = 0，不相邻。O(1) 时间。 空间： 4*4 = 16 个单元，但只有 10 个有效值（对称矩阵）。
邻接表存储
顶点 0: [1, 2]
顶点 1: [0, 2, 3]
顶点 2: [0, 1, 3]
顶点 3: [1, 2]读入过程：
- 读入边 (0,1)：在 adjList[0] 添加 1，在 adjList[1] 添加 0
- 读入边 (0,2)：在 adjList[0] 添加 2，在 adjList[2] 添加 0
- ...以此类推
查询： 0 和 3 是否相邻？遍历 adjList[0] = [1,2]，未找到 3，不相邻。O(degree) 时间。 空间： 存储了 2*5 = 10 个邻接关系，比邻接矩阵更节省。
边集数组存储
edges = [(0,1), (0,2), (1,2), (1,3), (2,3)]直接存储 5 条边。 查询： 0 和 3 是否相邻？遍历所有边查找，O(E) 时间，最慢。 空间： 只有 5 条边的信息，最节省。
✨ 解题步骤详解
以"图的存储"为例：
问题： 给定 n 个顶点和 m 条边，分别用邻接矩阵和邻接表存储图并输出。
解题步骤：
- 读入 n 和 m。
- 初始化数据结构：
- 邻接矩阵：声明
int matrix[n][n]，全部初始化为 0。 - 邻接表：声明
vector。
- 邻接矩阵：声明
- 读入每条边 (u, v)：
- 邻接矩阵：
matrix[u][v] = 1; matrix[v][u] = 1;（无向图需两个方向） - 邻接表：
adj[u].pushback(v); adj[v].pushback(u);
- 邻接矩阵：
- 输出：按题目要求格式输出。邻接表通常需要先排序再输出。
如何选择存储方式：
- n <= 1000 且需要频繁查询两点是否相邻 → 邻接矩阵
- n > 1000 或边数远小于 n^2 → 邻接表
- 需要对所有边排序或按权重处理 → 边集数组
✨ 常见错误
- 无向图只存了一个方向：读入边 (u,v) 时，忘记同时存储 (v,u)。这会导致从 v 出发找不到 u。
- 邻接矩阵空间开太大：如果 n = 10^5，邻接矩阵需要 10^10 个元素，内存会超限。此时必须用邻接表。
- 邻接表忘记排序：某些题目要求邻接点按编号顺序输出，邻接表中的顺序取决于读入顺序，需要手动排序。
- 顶点编号偏移：题目给的顶点编号从 1 开始，但数组索引从 0 开始。要么统一从 1 开始（数组多开一位），要么统一从 0 开始（读入时减 1）。
- 有向图和无向图处理方式混淆：有向图 (u,v) 只存
u->v，不存v->u。