邻接矩阵用二维数组存边，适合稠密图，需初始化全0或INF，顶点编号从1开始时数组大小应为N+1；邻接表用vector<vector>存邻居，适合稀疏图，无向图须双向添加边，有权边需用pair存储。
邻接矩阵：用二维数组存边，适合稠密图
邻接矩阵本质是 vector<vector>></vector> 或 int[N][N]，索引 i 和 j 对应顶点编号，matrix[i][j] 表示从 i 到 j 是否有边（或边权）。无向图需对称赋值，有向图单向即可。
常见错误是初始化不全：忘记把所有元素设为 0（无边）或 INF（表示不可达），导致后续 if (matrix[u][v]) 判断失效。另外，顶点编号若从 1 开始，数组得开 N+1 大小，否则访问 matrix[N][N] 越界。
适用场景：图中边数接近顶点数的平方（比如网格图、完全图），或频繁查两点间是否有边 / 边权（O(1) 查询）。
示例初始化（无权无向图，顶点数 n）：
立即学习“C++免费学习笔记（深入）”；
vector<vector<bool>> adj(n, vector<bool>(n, false)); // 添加边 u-v adj[u][v] = adj[v][u] = true;
邻接表：用 vector of vector 存邻居，适合稀疏图
邻接表核心是 vector<vector>></vector>（无权）或 vector<vector int>>></vector>（有权），其中 adj[u] 存所有与 u 相连的顶点（或 {v, weight} 对）。比邻接矩阵省空间，增删边也更灵活。
容易踩的坑：
- 忘记无向图要双向添加：adj[u].push_back(v) 和 adj[v].push_back(u) 缺一不可；
- 用 list 或 set 替代 vector——除非真需要去重或动态插入中间，否则 vector 的缓存友好性和遍历速度明显更好；
- 权重边误用 int 存 {v, w}，必须用 pair<int int></int> 或自定义结构体，否则编译报错。
示例（有权有向边 u→v 权重 w）：
vector<vector<pair<int, int>>> adj(n); adj[u].emplace_back(v, w); // 推荐 emplace_back 避免临时对象
怎么选：看边密度和操作模式
判断依据不是“听起来高级”，而是实际数据特征和使用方式：
- 边数
m接近n²/2？选邻接矩阵；m小于3n？邻接表更稳； - 算法需要反复查“是否存在边
u→v”？矩阵快； - 要遍历顶点
u的所有出边？邻接表天然支持，矩阵得扫整行； - 内存受限（比如嵌入式或大
n小m）？邻接表空间是O(n + m)，矩阵固定O(n²)。
没有“通用最优”，同一个项目里甚至可能混用：建图用邻接表，预处理后导出矩阵做 Floyd。
常见运行时错误和调试提示
两种表示法都容易在边界上翻车：
- 访问 adj[u][i] 前没检查 u 且 <code>i ，尤其在循环邻居时写成 <code>for (int i = 0; i （多跑一次）；<br>
- 读入边时顶点编号从 1 开始，但数组按 0 开始索引，忘了减 1，结果全偏移；<br>
- 初始化邻接矩阵用 <code>vector<vector>>(n, vector<int>(n))</int></vector> 没问题，但若写成 vector<vector>>(n, vector<int>(n, 0))</int></vector> 是冗余的——默认构造就是 0；
- 邻接表中某顶点没连边，adj[u] 是空 vector，直接 .front() 或下标访问会崩溃。
调试时先打印 adj.size() 和几个 adj[i].size()，确认规模符合预期，比硬看逻辑更快定位越界或漏建。
真正麻烦的从来不是“怎么写出来”，而是“怎么确保它在所有边界输入下不崩、不漏、不慢”。邻接矩阵和邻接表只是工具，它们的正确性取决于你怎么初始化、怎么索引、怎么遍历。
