我正在尝试实现加权图。我知道有两种方法可以实现加权图。使用二维数组（邻接矩阵）或链表数组（邻接表）。两者中哪一个更高效、更快？
问问题
156 次
2 回答
2
两者中哪一个更高效、更快？
这取决于您的使用情况和要存储的图表类型。
设 n 为节点数，m 为边数。如果您想知道两个节点 u 和 v 是否连接（以及边的权重），邻接矩阵允许您在恒定时间内确定这一点（在O-notation中，O(1)），只需检索条目A[u,v]. 使用邻接列表，您将不得不查看 u 列表或 v 列表中的每个条目 - 在最坏的情况下，可能有 n 个条目。所以邻接列表的边缘查找在 O(n) 中。
邻接矩阵的主要缺点是所需的内存。总之，您需要存储 n^2 个条目。使用邻接表，您只需要存储实际存在的边（m 个条目，假设有向图）。因此，如果您的图是稀疏的，则邻接列表显然占用的内存要少得多。
我的结论是：如果您的主要操作是检索两个特定节点的边权重，请使用邻接矩阵；在您的图表足够小以使 n^2 个条目适合内存的条件下。否则，使用邻接表。
于 2012-05-10T08:46:45.067 回答
1
就我个人而言，我会选择链表方法，假设它通常是一个稀疏图（即大多数数组单元都是浪费空间）。
去维基百科阅读邻接列表（自从我使用图表以来已经很长时间了），它有一个很好的部分介绍了两种方法之间的权衡。最终，与许多非此即彼的选择一样，它会归结为“取决于”，具体取决于您的库的可能用例。
阅读 wiki 文章后，我认为支持使用列表的另一点是将数据附加到每个有向段（甚至不同的权重，想想 2 点之间的步行/自行车/汽车距离等）
于 2012-05-09T18:58:25.700 回答