邻接矩阵
较难3邻接矩阵：用“棋盘表格”存储图
想象你有一张班级座位表，每个同学都有一个学号。你想知道任意两个同学之间是不是好朋友（有没有直接联系）。最直接的办法就是画一张大表格：横排列出所有同学，竖排也列出所有同学，然后在交叉的格子里打个勾（1）表示他们是朋友，画个叉（0）表示不是朋友。这张表格就叫 邻接矩阵（adjacency matrix）。
在图论里，每个同学就是一个 顶点（vertex），朋友关系就是一条 边（edge）。如果有 n 个顶点，就需要一张 n 行 n 列的表格，每个格子记录两个顶点之间是否有边。
? 邻接矩阵长什么样？
假设我们有 5 个顶点（编号 0~4），边的情况是：
- 顶点 0 和 1 相连，1 和 2 相连，2 和 3 相连，3 和 4 相连，4 和 0 相连（形成一个五边形）。
那么邻接矩阵就是这样的 5×5 表格：
0 1 2 3 4
0: 0 1 0 0 1
1: 1 0 1 0 0
2: 0 1 0 1 0
3: 0 0 1 0 1
4: 1 0 0 1 0
把矩阵写出来就是：
| 行\列 | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 0 | 1 |
| 1 | 1 | 0 | 1 | 0 | 0 |
| 2 | 0 | 1 | 0 | 1 | 0 |
| 3 | 0 | 0 | 1 | 0 | 1 |
| 4 | 1 | 0 | 0 | 1 | 0 |
因为是无向图（朋友关系是双向的），所以矩阵关于对角线对称：adj[i][j] == adj[j][i]。
? 生活中的例子
例子1：班级友谊网络
全班 50 个同学，用邻接矩阵记录谁和谁是好友。如果有两个同学 A 和 B 放学一起走，就在 adj[A][B] 和 adj[B][A] 填 1。想查 A 和 C 是不是好友，直接看 adj[A][C] 的值就行，1 就是好友，0 就不是。
例子2：地铁线路图
把每个地铁站看作顶点，两个站之间有直接地铁线路就算一条边。用邻接矩阵可以快速判断从“人民广场”到“陆家嘴”有没有直达地铁。如果地铁线路很多（稠密图），邻接矩阵就很合适；但如果站点很多但线路很少（稀疏图），大部分格子都是 0，很浪费空间。
例子3：游戏地图传送门
在冒险游戏中，有 10 个房间，某些房间之间有传送门（可以双向传送）。用邻接矩阵存储，想从房间 3 传送到房间 7，直接查 adj[3][7] 是不是 1 就知道了。
? 如何用 C++ 实现邻接矩阵？
方法一：固定大小（数组大小必须是常量）
#include <iostream>
using namespace std;
int main() {
const int n = 5; // 顶点数，必须用 const 定义常量
// 定义邻接矩阵，n行n列，所有元素初始化为0
int adj[n][n] = {0}; // {0} 表示把所有元素都设为0
// 添加无向边：顶点0-1, 1-2, 2-3, 3-4, 4-0
adj[0][1] = 1; adj[1][0] = 1;
adj[1][2] = 1; adj[2][1] = 1;
adj[2][3] = 1; adj[3][2] = 1;
adj[3][4] = 1; adj[4][3] = 1;
adj[4][0] = 1; adj[0][4] = 1;
// 打印邻接矩阵
cout << "邻接矩阵（无向图）:" << endl;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << adj[i][j] << " ";
}
cout << endl; // 每打印完一行换行
}
return 0;
}
输出：
邻接矩阵（无向图）:
0 1 0 0 1
1 0 1 0 0
0 1 0 1 0
0 0 1 0 1
1 0 0 1 0
方法二：用 vector 动态创建（顶点数可变量）
如果顶点数 n 是变量（比如从键盘输入），就不能用固定数组了。我们可以用 C++ 的 vector（向量）来动态创建二维数组。
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n = 5; // 顶点数，可以是变量
// 创建 n 行 n 列的二维 vector，所有元素初始化为0
vector<vector<int>> adj(n, vector<int>(n, 0));
// 添加边：顶点0-1, 1-2, 2-3, 3-4, 4-0
adj[0][1] = 1; adj[1][0] = 1;
adj[1][2] = 1; adj[2][1] = 1;
adj[2][3] = 1; adj[3][2] = 1;
adj[3][4] = 1; adj[4][3] = 1;
adj[4][0] = 1; adj[0][4] = 1;
// 打印矩阵
cout << "邻接矩阵（用vector）:" << endl;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << adj[i][j] << " ";
}
cout << endl;
}
return 0;
}
? 邻接矩阵的优缺点
✅ 优点
- 查询速度快：想知道顶点
i和j之间有没有边，直接看adj[i][j]，时间是 O(1)，就像查字典一样快。 - 实现简单：二维数组的概念很直观，代码容易写。
- 适合稠密图：如果边很多（比如每个顶点都和大多数其他顶点相连），邻接矩阵的空间利用率很高。
❌ 缺点
- 浪费空间：如果有
n个顶点，矩阵就有n^2个格子。如果n=1000，矩阵有 100 万个格子，但边只有 2000 条，那么 99.8% 的格子都是 0，白白占用内存。 - 添加/删除边稍麻烦：虽然添加一条边只是
adj[i][j]=1，但如果要删除边，需要设为 0。不过对于图论算法来说，这通常不是瓶颈。 - 无法直接表示多条边：如果两个顶点之间有多条边（比如有两条不同的路），邻接矩阵只能存 1 或 0，不能记录边的数量（除非改成整数计数）。
⚠️ 新手常见错误
❌ 错误1：顶点编号从0还是1？
很多人会搞混顶点的编号。在代码中，我们通常用 0 到 n-1 表示顶点。但有时题目给的顶点编号是 1 到 n，这时需要做转换：把 adj[v-1][u-1] 赋值。
正确做法：统一用 0 开始，如果需要用 1 开始，可以定义 adj[n+1][n+1]，只使用下标 1~n 的位置。
❌ 错误2：忘记初始化数组
如果只声明 int adj[5][5] 而不初始化，里面的值是随机的（垃圾值），会导致判断边时出错。
正确做法：要么用 {0} 全部初始化为 0，要么用双重循环手动赋 0。
❌ 错误3：未考虑无向图对称性
如果是无向图，添加一条边时一定要同时设置 adj[i][j] 和 adj[j][i]。只设置一个，就变成有向图了。
❌ 错误4：数组大小是变量却用固定数组
在 C++ 中，数组的大小必须是编译期常量（比如 const int 或字面量），不能用普通变量。
正确做法：如果顶点数可变，用 vector<vector<int>>。
❌ 错误5：自环
如果题目允许顶点自己连自己（自环），adj[i][i] = 1 是合理的。但一般简单图没有自环，此时对角线上全是 0。
? 完整可运行示例（带输入输出）
下面的程序让用户输入顶点数和边数，然后输入每条边的两个端点，最后输出邻接矩阵，并询问两个顶点之间是否有边。
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, m; // n: 顶点数, m: 边数
cout << "请输入顶点数和边数: ";
cin >> n >> m;
// 创建 n 行 n 列的矩阵，全部初始化为0
vector<vector<int>> adj(n, vector<int>(n, 0));
cout << "请输入每条边的两个顶点（编号从0到" << n-1 << "）:" << endl;
for (int i = 0; i < m; i++) {
int u, v; // u: 边的起点, v: 边的终点
cin >> u >> v;
// 如果是无向图，两条方向都要设置
adj[u][v] = 1;
adj[v][u] = 1;
}
// 打印邻接矩阵
cout << "\n邻接矩阵:" << endl;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << adj[i][j] << " ";
}
cout << endl;
}
// 查询两个顶点之间是否有边
int a, b;
cout << "\n请输入要查询的两个顶点: ";
cin >> a >> b;
if (adj[a][b] == 1)
cout << "顶点" << a << "和顶点" << b << "之间有边。" << endl;
else
cout << "顶点" << a << "和顶点" << b << "之间没有边。" << endl;
return 0;
}
运行示例：
请输入顶点数和边数: 4 3
请输入每条边的两个顶点（编号从0到3）:
0 1
1 2
2 3
邻接矩阵:
0 1 0 0
1 0 1 0
0 1 0 1
0 0 1 0
请输入要查询的两个顶点: 1 3
顶点1和顶点3之间没有边。
? 相关知识点
- 邻接表：当图很稀疏（边很少）时，推荐用邻接表存储，它只记录存在的边，节省空间。
- 图的遍历：有了邻接矩阵，就可以实现深度优先搜索（DFS）和广度优先搜索（BFS）来走遍所有顶点。
- 最短路径：Floyd 算法可以直接在邻接矩阵上计算任意两点之间的最短路径。
- 有向图：邻接矩阵同样可以表示有向图（边有方向），此时矩阵不一定对称。
邻接矩阵是图论中最基础的数据结构之一，就像你学习数字时先学整数一样，掌握它之后，学习更高级的图算法会轻松很多。试着用邻接矩阵画出你自己班级的朋友关系，写一个程序来打印吧！
例题精讲
对于一个具有n个顶点的无向图，使用邻接矩阵存储时，其空间复杂度是多少？
邻接矩阵特别适合存储稀疏图，因为它可以高效地表示大量顶点之间的边。
以下函数用于判断无向图中两个顶点u和v之间是否有边（假设邻接矩阵为int adj[N][N]，N为顶点数，有边时adj[u][v]和adj[v][u]均为1）。请补全代码。
bool hasEdge(int adj[][N], int u, int v) {
return ___;
}关于无向图的邻接矩阵，以下哪个说法是正确的？
在带权图中使用邻接矩阵时，常用元素值表示边的权值，若两顶点之间没有直接边，则对应位置可以设置为一个特殊值（如0或INF）。