稀疏图和稠密图有什么区别？会影响图算法选择吗？

简化版

稀疏图边数远小于点数平方，稠密图边数接近点数平方。

这个区别会影响存储结构和算法选择。稀疏图通常用邻接表，遍历边更省；稠密图可以考虑邻接矩阵，判断两点是否有边更快。

同一个算法在不同图密度下表现也不同，比如 Dijkstra 用堆优化更适合稀疏图，邻接矩阵朴素实现有时适合稠密图。

详细版

对有 V 个点的无向简单图，最多边数约是：

V * (V - 1) / 2

如果 E 远小于 V^2，通常称为稀疏图；如果 E 接近 V^2，称为稠密图。

图类型	常用存储	原因
稀疏图	邻接表	只存真实边
稠密图	邻接矩阵	边几乎都存在，查询快

选择算法时不能只背复杂度，还要把 E 和 V^2 的关系代进去看。

完整版教学

1. 稀疏和稠密是相对概念

图的最大边数和点数平方相关。

对于无向简单图：

maxEdges = V * (V - 1) / 2

对于有向简单图：

maxEdges = V * (V - 1)

如果实际边数 E 很小，就是稀疏图；如果接近最大边数，就是稠密图。

2. 为什么存储方式会受影响

邻接矩阵需要 V x V 空间。

即使只有很少边，也要分配完整矩阵。

邻接表只保存真实存在的边，空间大约是：

O(V + E)

图越稀疏，邻接表越有空间优势。

3. 查询边是否存在的差异

邻接矩阵判断 u 到 v 是否有边：

matrix[u][v]

复杂度是 O(1)。

邻接表需要在 u 的邻居列表里找 v，复杂度和 u 的度数有关。如果用哈希集合存邻居，可以接近 O(1)，但空间常数更高。

4. 遍历邻居的差异

邻接表遍历 u 的邻居，只访问真实边。

邻接矩阵遍历 u 的邻居，需要扫描整行 V 个位置。

操作	邻接表	邻接矩阵
遍历所有边	O(V + E)	O(V^2)
判断是否有边	取决于实现	O(1)
空间	O(V + E)	O(V^2)

这就是稀疏图更偏邻接表的原因。

5. 对 Dijkstra 的影响

Dijkstra 有不同实现。

实现	复杂度	更适合
邻接矩阵朴素版	O(V^2)	稠密图
邻接表 + 堆	O((V + E) log V)	稀疏图

如果 E 很接近 V^2，堆优化的优势可能没那么明显。

如果 E 远小于 V^2，邻接表加堆通常更合适。

6. 对 Floyd 和全源最短路的影响

Floyd 是 O(V^3)，主要看点数，不直接看边数。

如果图点数小但查询任意两点很多，Floyd 可以接受。

如果图很大但稀疏，反复跑 Dijkstra 可能更合适。

场景	选择
点少、查询多	Floyd
稀疏大图、多源但不是全量	多次 Dijkstra
有负权边	Bellman-Ford 或 Johnson 等

7. 面试中怎么表达

回答图算法时，可以主动补一句：

如果图是稀疏图，我会用邻接表；如果是稠密图且需要快速判断边是否存在，可以考虑邻接矩阵。

这句话能体现你不是机械背算法，而是在根据输入规模做取舍。

8. 常见误区与追问

• 误区：邻接矩阵一定比邻接表快。 它查询边快，但遍历邻居和空间成本高。
• 误区：稀疏图和稠密图有严格统一阈值。 它们是相对概念，要结合 E 和 V^2 看。
• 误区：堆优化 Dijkstra 永远更好。 在非常稠密的图上，朴素 O(V^2) 实现也可能有竞争力。
• 追问：无向图最大边数是多少？ 简单无向图是 V*(V-1)/2。
• 追问：为什么邻接表空间是 O(V + E)？ 需要保存点集合和每条真实边的邻接记录。