引言
假设你正在玩《星际争霸2》，需要分析虫族巢穴之间的最短补给路线。如果巢穴数量是100个，用邻接矩阵存储能秒算任意两点距离；但如果只有50条实际通路，邻接表会省出4950个无用空间——这就是竞赛中图的存储选择直接影响性能的关键！邻接矩阵和邻接表就像数据结构的「双雄」，各有各的江湖地位，今天咱们掰扯掰扯它们到底怎么用。
核心概念讲解
邻接矩阵（Adjacency Matrix）
原理：用二维数组
matrix[i][j]表示顶点i到j是否有边。无向图对称，有向图不对称。图示：
顶点 A B C
A [0,1,1]
B [1,0,0]
C [1,0,0]
（1表示有边，0表示无边）
邻接表（Adjacency List）
原理：每个顶点存一个链表，记录它的邻居。像朋友圈的「好友列表」，只存真实关系。
图示：
A: B -> C -> nullptr
B: A -> nullptr
C: A -> nullptr
C++代码示例
#include <bits/stdc++.h>
using namespace std;
// 邻接矩阵实现（带权）
const int N = 101;
int matrix[N][N];
void buildMatrix(int n) {
memset(matrix, 0, sizeof(matrix)); // 初始化为0
for (int i=0; i<n; ++i) {
int u, v, w;
cin >> u >> v >> w;
matrix[u][v] = matrix[v][u] = w; // 无向图需双向赋值
}
}
// 邻接表实现（无向图）
vector<int> adj[N];
void buildList(int n) {
for (int i=0; i<n; ++i) {
int cnt;
cin >> cnt;
for (int j=0; j<cnt; ++j) {
int v;
cin >> v;
adj[i].push_back(v);
adj[v].push_back(i); // 无向图双向添加
}
}
}
int main() {
int n, m;
cin >> n >> m;
buildMatrix(n); 或 buildList(n); // 按需调用
return 0;
}
算法分析
| 维度 | 邻接矩阵 | 邻接表 |
|————–|—————————–|—————————|
| 时间复杂度 | 查询边O(1)，遍历所有边O(V²) | 查询边O(degree(V))，遍历所有边O(E) |
| 空间复杂度 | O(V²) | O(V+E) |
| 适用场景 | 稠密图（E≈V²）、频繁查边 | 稀疏图（E≪V²）、DFS/BFS |
| 缺点 | 浪费空间、修改边慢 | 查边慢（需遍历链表） |
经典例题
1. P3367【模板】图的存储与遍历（洛谷）
- 思路：邻接矩阵适合快速判边，邻接表适合DFS遍历。输入图后，分别用两种方式输出邻接关系，对比结果。
2. CF833D Maximum Submatrix（Codeforces）
- 关键：用邻接表存储稀疏图，避免O(N⁴)暴力枚举。
推荐练习
- 【入门】P1916 关路灯（邻接矩阵求最短路）
https://www.luogu.com.cn/problem/P1916
- 【进阶】CF1083D The Minimum Score on the Tree Path（邻接表+树形DP）
https://codeforces.com/contest/1083/problem/D
- 【挑战】P4779 [NOI2018] 冒泡排序（邻接表模拟拓扑序）
https://www.luogu.com.cn/problem/P4779
小结
邻接矩阵适合「查快」的稠密图，邻接表适合「存省」的稀疏图。下篇文章带你实战用邻接表解决「最短路径」问题——别担心，到时候你会笑着发现：「原来Dijkstra和邻接表才是绝配！」 🚀