图的表示——邻接矩阵
困难5图的表示——邻接矩阵
上一节课我们知道了图由顶点和边组成。那么，如何让计算机记住这些关系呢？最直接的方法就是画一张表格：邻接矩阵。
什么是邻接矩阵？
邻接矩阵就像一个同学通讯录：假设班级里有 个同学，你拿出一张 行 列的表格。行和列都按学号来编号。如果第 行第 列写 1，就表示学号 的同学有学号 的微信号（有单向关系）；如果写 0，就没有。对于无向图（比如两人互相认识），表格会关于对角线对称——因为如果 认识 ，那么 也认识 。
所以，邻接矩阵的核心思想就是：用一个 的表格记录每对顶点之间是否有边。如果有权重（比如距离、花费），就把 1 换成具体的数值。
生活中的例子：城市交通图
假设有三个城市：北京（编号0）、上海（编号1）、广州（编号2）。
- 北京到上海有高铁（单向）
- 上海到广州有高铁（单向）
- 北京到广州没有直达
用邻接矩阵表示（行 → 列，从出发城市到到达城市）：
北京 上海 广州
北京 0 1 0
上海 0 0 1
广州 0 0 0
看表格第0行第1列是1，说明北京→上海有路；第1行第2列是1，说明上海→广州有路；其他地方都是0。
用 C++ 的二维数组存储邻接矩阵
在代码里，我们用一个二维数组 int graph[n][n] 来存放这个表格。数组元素 graph[i][j] 的值表示从顶点 到顶点 的边是否存在（1表示是，0表示否）。
下面的代码演示了如何创建并打印上面的城市图：
#include <iostream>
using namespace std;
int main() {
const int n = 3; // 顶点数（城市个数）
int graph[n][n] = {0}; // 把表格所有格子初始化为0
// 添加边：北京(0) -> 上海(1) ，上海(1) -> 广州(2)
graph[0][1] = 1;
graph[1][2] = 1;
// 打印邻接矩阵
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << graph[i][j] << " ";
}
cout << endl; // 每行打印完换行
}
return 0;
}
输出结果：
0 1 0
0 0 1
0 0 0
如何添加边和判断边？
- 添加一条有向边：
graph[起点][终点] = 1; - 添加一条无向边：需要同时写两处，因为无向边双向都通。
graph[起点][终点] = 1; graph[终点][起点] = 1; - 判断两点之间是否有边：直接看
graph[i][j]的值，如果是1就有边，是0就没有。这个判断只需要 一次数组访问，所以非常快，时间复杂度 O(1)。
生活中的例子：朋友关系
假设4个同学：张三(0)、李四(1)、王五(2)、赵六(3)。他们是好朋友关系（无向图）：
- 张三和李四是好朋友
- 李四和王五是好朋友
- 王五和赵六是好朋友
邻接矩阵应该是对称的：
0 1 2 3
0 0 1 0 0
1 1 0 1 0
2 0 1 0 1
3 0 0 1 0
代码中这样建图：
int n = 4; // 4个顶点
int graph[4][4] = {0}; // 初始化为0
// 添加无向边
graph[0][1] = 1; graph[1][0] = 1; // 张三-李四
graph[1][2] = 1; graph[2][1] = 1; // 李四-王五
graph[2][3] = 1; graph[3][2] = 1; // 王五-赵六
很多同学容易只写
graph[i][j] = 1而忘记写另一方向，导致图变成有向图，查半天查不到错误。
邻接矩阵的优缺点
| 优点 ✅ | 缺点 ❌ |
|---|---|
| 判断两点是否有边 超级快（O(1)） | 太占内存！顶点数 大时，需要 个格子 |
| 代码简单，容易理解 | 即使只有几条边，也要创建整个大表格 |
| 适合 稠密图（边数接近顶点数的平方） | 对于稀疏图（边很少），比如10000个顶点只有10000条边，矩阵里99%都是0，白浪费空间 |
生活类比：如果全班50个同学，你画一张50×50的表（2500个格子），记录谁有谁的联系方式，用起来很方便。但如果全校10000人，这张表就有1亿个格子，大多数格子都是空的，太浪费纸了！
常见错误提醒 ?
- 忘记初始化：直接定义
int graph[n][n];而不给初值，里面可能是一些乱码。一定要赋初值{0}或用循环清零。 - 无向图只写一边：只写
graph[i][j] = 1忘了graph[j][i] = 1，会导致朋友关系变成单相思。 - 数组下标越界：顶点编号从0到，如果用了
graph[n][0]，程序会崩溃。 - 顶点数太大时直接开大数组：比如
int graph[100000][100000]会内存溢出。解决办法：改用邻接表（见文末指引）。
完整可运行的示例（含输入输出）
下面这个程序让你自己输入顶点数和边，然后添加边，并查询任意两点是否有边。
#include <iostream>
using namespace std;
int main() {
int n, m; // n=顶点数, m=边数
cout << "请输入顶点数和边数: ";
cin >> n >> m;
// 创建邻接矩阵，大小为 n x n，全部初始化为0
int graph[100][100] = {0}; // 这里假设 n<=100，避免数组过大
cout << "请输入 " << m << " 条边，每条边两个顶点编号(0开始)" << endl;
for (int i = 0; i < m; i++) {
int u, v; // u=起点, v=终点
cin >> u >> v;
graph[u][v] = 1; // 有向边：u→v
// 如果是无向图，需要加上这一行：
// graph[v][u] = 1;
}
cout << "\n邻接矩阵如下：" << endl;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << graph[i][j] << " ";
}
cout << endl;
}
// 查询功能：询问任意两点是否有边
int q; // 查询次数
cout << "\n请输入要查询的次数: ";
cin >> q;
while (q--) {
int a, b;
cout << "输入两个顶点编号: ";
cin >> a >> b;
if (graph[a][b] == 1)
cout << "有边 (" << a << "->" << b << ")" << endl;
else
cout << "没有边" << endl;
}
return 0;
}
运行示例：
请输入顶点数和边数: 3 2
请输入 2 条边，每条边两个顶点编号(0开始)
0 1
1 2
邻接矩阵如下：
0 1 0
0 0 1
0 0 0
请输入要查询的次数: 2
输入两个顶点编号: 0 2
没有边
输入两个顶点编号: 1 2
有边 (1->2)
相关知识点指引
学会了邻接矩阵，下一步可以学习：
- 邻接表：用链表或 vector 存储每个顶点的邻居，适合稀疏图，节省内存。
- 图的遍历：深度优先搜索（DFS）、广度优先搜索（BFS），都需要依赖图的结构来访问每个顶点。
- 最短路径：比如 Dijkstra 算法，邻接矩阵可以直观地表示带权图。
如果想挑战自己，可以尝试用邻接矩阵实现一个简单的社交网络，比如朋友推荐系统（找到两人共同好友的数量）。祝学习愉快！
例题精讲
对于一个具有 n 个顶点的图，使用邻接矩阵表示法，其空间复杂度为多少？
在无向图的邻接矩阵中，若顶点 i 与顶点 j 之间存在一条边，则矩阵元素 A[i][j] 和 A[j][i] 的值均为 1（或权值）。
以下代码实现了一个 n 个顶点的无向图邻接矩阵的初始化，所有边权值初始化为 0。请补全横线处的代码。
int graph[100][100];
int n; // 顶点数
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
___ = 0;
}
}对于一个有 n 个顶点、e 条边的无向图，其邻接矩阵中非零元素的个数是多少？
邻接矩阵比较适合存储稀疏图，因为它的存储效率高。