在Ada中实现Kruskal的算法,不知道从哪里开始

Question

参考Ada中的Kruskal算法,我不知道从哪里开始.

在我实际编写程序之前,我正在考虑所有内容,但我很遗憾我应该使用什么数据结构以及如何表示所有内容.

我最初的想法是在邻接列表中表示完整的树,但是阅读维基百科的算法说明create a forest F (a set of trees), where each vertex in the graph is a separate tree并且我不确定如何实现它而不会很快变得非常混乱.

它接下来create a set S containing all the edges in the graph要说的是,但我不知道最好的方法是做什么.我在想记录的数组,具有to,from和weight,但我失去了对forest.

最后,我试图弄清楚我是如何知道边缘是否连接两棵树,但我不知道最好的方法是做什么.

Answer 1

我可以看到他们的算法描述会让你对如何开始感到困惑。它给我留下了同样的方式。

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

看起来基本思想如下：

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