algorithm - 关联矩阵而不是邻接矩阵

Question

使用关联矩阵数据结构而不是更广泛的邻接矩阵可以更快地解决图上的哪种问题(就大 O 而言)？

Answer 1

结构的空间复杂度是:

邻接:O(V^2) 发生率:O(VE)

结果是，如果顶点比边多得多，则关联结构可以节省空间。

可以看看一些典型的图操作的时间复杂度:

找到与一个顶点相邻的所有顶点: 调整:O(V) 公司:O(VE)

检查两个顶点是否相邻: 调整:O(1) 公司:O(E)

计算顶点的价数: 调整:O(V) 公司:O(E)

等等。对于任何给定的算法，您都可以使用上述构建 block 来计算哪种表示可以为您提供更好的整体时间复杂度。

作为最后一点，使用任何类型的矩阵对于除了最密集的图形之外的所有图形来说都是极其低效的空间，我建议不要使用任何一种，除非你有意识地放弃了邻接列表等替代方案。