algorithm - 在 Ada 中实现 Kruskal 算法，不知道从哪里开始

Question

引用Kruskal's algorithm在 Ada 中，我不确定从哪里开始。

在我实际编写程序之前，我试图仔细考虑所有事情，但是对于我应该使用什么数据结构以及如何表示所有事情我感到很迷茫。

我最初的想法是在邻接表中表示整棵树，但阅读维基百科时算法指出创建一个森林 F(一组树)，其中图中的每个顶点都是一棵单独的树，我不确定如何在不很快变得非常困惑的情况下实现它。

接下来要做的是创建一个包含图中所有边的集合 S，但我还是不确定最好的方法是什么。我在想一个记录数组，带有 to、from 和 weight，但我迷失在 forest.

最后，我试图弄清楚如何知道一条边是否连接了两棵树，但我还是不确定完成所有这一切的最佳方法是什么。

Answer 1

我可以看到他们的算法描述会从哪里开始让您感到困惑。它以同样的方式离开了我。

我建议阅读后面的 Example section反而。这使得如何继续进行变得非常清楚，您可能可以从中想出执行此操作所需的数据结构。

看起来基本思路如下:

• 获取图形，找到引入至少一个新顶点的最短边，并将其放入您的“生成树”。
• 重复上述步骤，直到您拥有每个顶点。