图形库实现

Question

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

Answer 1

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

去维基百科阅读邻接列表（自从我使用图表以来已经很久了），它有一个关于两种方法之间权衡的很好的部分。最终，就像许多非此即彼的选择一样，它将归结为“视情况而定”，这取决于你的库的可能用例。

在阅读了维基文章之后，我认为使用列表的另一个好处是将数据附加到每个定向段（甚至不同的权重，想想步行/自行车/汽车在2个点之间的距离等等）

Answer 2

这两种方法中哪一种效率更高、速度更快？

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

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

相邻矩阵的主要缺点是需要内存。总之，您需要存储n^2个条目。对于邻接列表，您只需要存储实际存在的边（m个条目，假设有向图）。因此，如果你的图是稀疏的，邻接列表显然占据更少的内存。

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