java - Java：最小生成树的数据结构

Question

我的项目是使用java实现最小生成树。我的目标是使用 Prim 的算法来完成这项任务。

该图的定义是 G = (V, E) 其中 V 是引脚集合，E 是引脚对之间可能互连的集合，对于 E 中的每条边 (u,v)，我们有一个权重 w( u,v) 指定连接 u 和 v 的成本。

我的想法是使用两个哈希图。首先将 pin 作为键，将邻居列表作为值。第二个哈希图将边缘列表（u，v）作为键，值将是它的权重。

您认为存储图表的最佳方式是什么？

Answer 1

图通常（不考虑与这些图一起使用的算法）存储为：

• 邻接列表，
• 邻接矩阵，
• 发病名单，
• 发生矩阵。

在内存使用和遍历它们所需的时间方面，它们都有其优点和缺点。维基百科对计算机中的图形表示有很好的描述。

Answer 2

看看维基百科。您有不同的数据结构可用以及继承的复杂性

Answer 3

对于 Kruskal 和 Prim 的最小生成树算法，图的邻接表表示就足够了。它在内存使用方面比矩阵的方法更有效。因此，在您的情况下，这是一个不错的选择。