图库实现

我正试图实现一个加权图。我知道有两种方法来实现加权图。可以使用二维数组（邻接矩阵），也可以使用链表（邻接列表）。哪一个更高效，更快？图库实现

2012-05-09 Rontogiannis Aristofanis

两者中哪一个更高效，更快？

这取决于您的使用情况以及要存储的图表种类。

设n是节点的数量，m是边的数量。如果您想知道两个节点u和v是否连接（以及边的权重），则只需通过检索条目A[u,v]即可在相邻矩阵的恒定时间内（在O-notation，O（1））确定此值。在邻接列表中，您必须查看u列表中的每个条目，或v的列表 - 最坏的情况下，可能有n个条目。因此，邻接列表的边缘查找在O（n）中。

邻接矩阵的主要缺点是需要的内存。总而言之，您需要存储n^2个条目。使用邻接列表时，只需要存储实际存在的边（m个条目，如有向图）。所以如果你的图很稀疏，邻接列表显然会占用更少的内存。

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

来源

2012-05-10 08:46:45 clstaudt

非常好的答案。非常感谢你。 –

就我个人而言，我会去链接列表方法，假设它通常是一个稀疏图（即大多数数组单元是浪费空间）。

去维基百科阅读adjacency lists（自从我使用图表以来已经过了很长时间），并且在两种方法之间的权衡方面有一个很好的部分。最终，与许多/或选择一样，它将归结为“取决于”，这取决于图书馆可能的用例。

读取wiki文章后，我认为有利于使用列表的另一点是附加数据到每个向线段（或甚至不同的权重，2点之间等认为步行/自行车/车距离的）

来源

2012-05-09 18:58:25 Alok

回答

相关问题