关联矩阵代替邻接矩阵

结构的空间复杂性如下:

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

如果顶点多于边,则关联结构可以节省空间。

您可以查看一些典型图形操作的时间复杂性:

查找与某个顶点相邻的所有顶点:

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

计算顶点的价: 公司:O(E)

等等。对于任何给定的算法,您都可以使用像上面这样的构建块来计算哪种表示方式可以提供更好的总体时间复杂度。

最后一点,除了最密集的图之外,使用任何类型的矩阵都是非常没有空间效率的,我建议不要使用任何一种,除非你有意识地忽略了邻接列表之类的替代方法。

这种表示法的另一个问题是,存储它毫无意义,因为从边列表中动态计算它(回答给定单元格包含的内容)非常容易。

所以我的观点是-它只对理论工作有用。