图库实现

Question

我正在尝试实现一个加权图。我知道有两种方法可以实现加权图。使用二维数组(邻接矩阵)或使用链表数组(邻接表)。两者中哪一个更高效、更快？

Answer 1

Which one of the two is more efficient and faster?

这取决于您的使用情况和您想要存储的图表类型。

设 n 为节点数，m 为边数。如果您想知道两个节点 u 和 v 是否连接(以及边的权重)，邻接矩阵允许您在恒定时间(在 O-notation 中，O(1))中确定这一点，只需检索条目 A[u,v] .对于邻接列表，您必须查看 u 列表或 v 列表中的每个条目 - 在最坏的情况下，可能有 n 个条目。因此，邻接表的边缘查找在 O(n) 中。

邻接矩阵的主要缺点是所需的内存。总之，您需要存储 n^2 个条目。使用邻接表，您只需要存储实际存在的边(m 个条目，假设有向图)。因此，如果您的图形稀疏，则邻接列表显然占用的内存要少得多。

我的结论是:如果您的主要操作是检索两个特定节点的边权重，请使用邻接矩阵；在您的图形足够小以便 n^2 个条目适合内存的条件下。否则，使用邻接表。