图有哪些基本概念？邻接矩阵和邻接表怎么选？
简化版
图由顶点（vertex）和边（edge）组成，边分有向/无向、带权/无权。两种主流存储：邻接矩阵——一个 V×V 的二维数组，matrix[i][j] 表示 i 到 j 有没有边，空间 O(V²)、判断两点是否相邻 O(1)，适合稠密图；邻接表——每个顶点存一个邻居列表，空间 O(V+E)、遍历邻居快，适合稀疏图（大多数实际图都用它）。
详细版
基本概念：
- 顶点 / 边：图 = (V 顶点集, E 边集)。
- 有向图 / 无向图：边有没有方向。无向边 (a,b) 双向可达；有向边 a→b 只能单向。
- 带权 / 无权：边上有没有权重（距离、花费）。
- 度：无向图中一个顶点连的边数；有向图分入度（指向它的边）和出度（它指出的边）。
- 连通：无向图任意两点可达叫连通；有向图任意两点互相可达叫强连通。
两种存储对比：
| 维度 | 邻接矩阵 | 邻接表 |
|---|---|---|
| 结构 | V×V 二维数组 | 每个顶点一个邻居链表/数组 |
| 空间 | O(V²) | O(V + E) |
| 判断 i、j 是否相邻 | O(1) | O(该点的度) |
| 遍历一个点的所有邻居 | O(V) | O(该点的度) |
| 适合 | 稠密图、频繁查两点是否相邻 | 稀疏图（多数场景） |
完整版教学
一、图是最通用的数据结构
树是特殊的图（无环连通），链表是更特殊的图。图能表示任意「实体 + 关系」：社交网络（人 + 好友）、地图（地点 + 道路）、依赖关系（任务 + 先后）、网页（页面 + 链接）。正因为通用，图算法（遍历、最短路、拓扑排序等）是面试重点。理解图先抓住四个维度：有向还是无向、带权还是无权——它们决定了用什么算法。
二、邻接矩阵：用二维数组存边
matrix[i][j] 记录顶点 i 到 j 的关系：无权图存 0/1（有没有边），带权图存权重（无边用 0 或无穷大表示）。
- 优点：判断「i 和 j 相不相邻」是 O(1)（直接查数组）；实现简单；适合稠密图。
- 缺点：空间恒为 O(V²)，即使边很少也占满整个矩阵，稀疏图极浪费；遍历一个点的邻居要扫一整行 O(V)。
- 无向图的矩阵是对称的（
matrix[i][j] == matrix[j][i]）。
三、邻接表：每个点存自己的邻居
每个顶点维护一个列表，存它能直接到达的邻居（带权图还存权重）。
- 优点：空间 O(V+E)，只存实际存在的边；遍历某点的邻居只需 O(该点的度)，非常高效——图遍历、最短路等算法大多按邻居展开，所以邻接表最常用。
- 缺点：判断「i、j 是否相邻」要遍历 i 的邻居列表 O(度)，不如矩阵 O(1)。
四、怎么选：看稀疏还是稠密
关键看边的数量：
- 稀疏图（E 远小于 V²，如社交网络、路网）→ 邻接表。空间省、遍历快，是绝大多数场景的选择。
- 稠密图（E 接近 V²）或频繁查询「两点是否相邻」 → 邻接矩阵。O(1) 判断相邻、O(V²) 空间也不亏。
经验法则：不确定就用邻接表，它是通用默认；只有稠密或需要 O(1) 判相邻时才上矩阵。
五、其它表示
- 边集数组：直接存所有边 (u, v, w) 的列表。Kruskal 最小生成树、Bellman-Ford 按边松弛时用它很方便。
- 链式前向星：邻接表的数组紧凑实现，竞赛常用，缓存友好。
按算法需要选表示：按邻居展开用邻接表，按边处理用边集数组。
六、常见误区与追问
| 考点 | 正确口径 |
|---|---|
| 邻接矩阵 | O(V²) 空间，查边 O(1) |
| 邻接表 | O(V+E) 空间，遍历邻居高效 |
| 边集数组 | 适合 Kruskal 等按边处理算法 |
sparse graph: E << V^2 -> adjacency list
dense graph: E close V^2 -> matrix may be acceptable图的存储选择先看稀疏还是稠密，再看算法需要“查边”还是“遍历邻居”。
- 误区：邻接矩阵总是最快。 查某条边快，但遍历一个点所有邻居要扫整行，稀疏图会浪费大量时间和空间。
- 误区：邻接表不能存权重。 邻接表元素可以是
(to, weight)，完全能表示带权图。 - 误区：无向图只存一条边。 邻接表通常两边都存，
u->v和v->u都要加入。 - 追问：稀疏图为什么用邻接表？ 边远少于 V² 时，邻接表空间 O(V+E) 明显小于矩阵 O(V²)。
- 追问：什么时候矩阵更合适？ 点数较小、稠密图、频繁判断两点是否有边时矩阵方便。
- 追问：Kruskal 为什么常用边集？ 它要按边权排序并逐条合并端点，边集数组最直接。
七、加强记忆
图 = 顶点 + 边，分有向/无向、带权/无权；度分入度出度。两种存储：邻接矩阵（V×V 数组，空间 O(V²)、判相邻 O(1)，适合稠密图）、邻接表（每点存邻居，空间 O(V+E)、遍历邻居 O(度)，适合稀疏图、最常用）。选择看边多不多：稀疏用邻接表、稠密用邻接矩阵，不确定就用邻接表。按边处理的算法（Kruskal）用边集数组。