在Ada中实现Kruskal算法，不确定从何处开始。

Question

在Ada中实现Kruskal算法，不确定从何处开始。

algorithmgraphadaminimum-spanning-treekruskals-algorithm

7

关于使用Ada实现Kruskal算法，我不确定从哪里开始。在编写程序之前，我试图仔细考虑一切，但对于我应该使用哪些数据结构以及如何表示每个元素等问题感到相当迷茫。我的最初想法是用邻接列表表示完整树，但是阅读维基百科后，算法说明要创建一个森林F（一组树），其中图中的每个顶点都是单独的树，我不确定如何在不很快变得非常混乱的情况下实现这一点。接下来它说要创建包含图中所有边的集合S，但再次我不确定最好的方法是什么。我想到了一个记录数组，具有to，from和weight，但我对forest感到困惑。最后，我正在尝试弄清楚如何知道边连接两个树，但同样不确定完成所有这些工作的最佳方式是什么。

- cheezone

你只是在算法上遇到了困难，还是在 Ada 部分也有问题？除了维基百科，你还有其他的参考书或资料吗？ - hugomg

@BartKiers - 我的猜测是这是一份课程作业。许多大学在低级计算机科学课程中使用Ada语言，而这看起来非常像典型的学校编码项目。 - T.E.D.

@T.E.D.，啊，我明白了，谢谢。我不知道它在大学里被使用。在荷兰，我从未见过它作为计算机科学课程的一部分被使用。 - Bart Kiers

尝试查看http://cs.fit.edu/~ryan/ada/programs/access/tree-adb.html - 这应该会给你关于树部分的提示。至于森林，我不确定Ada是否具有可调整大小的列表，但如果这是一项作业，那么您可以选择一个常数作为任务大小的上限。 - alf

Ada通常不需要可调整大小的列表...它的数组功能可以涵盖大多数情况。在Ada的数组中有一些非常聪明的“解决方法”。这是一个适用于[长]字符串的示例：http://www.adapower.com/index.php?Command=Class&ClassID=Basics&CID=202 - Shark8

1

我认为在这种情况下，您确实需要一个可调整大小的“列表”；请尝试使用Ada.Containers.Vectors。 - Simon Wright

2个回答

2

"创建森林部分"实际上意味着：实现页面不相交集数据结构中的伪代码。如果您能够阅读C++，那么我在这里有一个非常简单明了的实现。（该实现可行，我已经用它来实现Kruskal算法 :)）

- Fred Foo

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- T.E.D. · Accepted Answer

我可以理解为什么他们的算法描述会让你不知从何处入手，因为它也让我感到困惑。我建议您阅读后面的示例部分。那部分非常清晰地展示了如何进行，您可能只需要从中推导出所需的数据结构即可。

基本思路如下：

- 取图形，找到引入至少一个新顶点的最短边，并将其放入"生成树"中。 - 重复上述步骤，直到每个顶点都包含在生成树中。