7

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

在实际编写程序之前，我试图仔细考虑所有内容，但是对于我应该使用哪些数据结构以及如何表示所有内容，我非常迷茫。

我最初的想法是在邻接列表中表示完整的树，但是阅读 Wikipedia 中的算法状态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.

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

4

2 回答 2

3

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

我建议改为阅读后面的示例部分。这使得如何进行非常清楚，并且您可能会从中提出您需要的数据结构。

看起来基本思想如下：

  • 拿这张图，找到引入至少一个新顶点的最短边，然后把它放在你的“生成树”中。
  • 重复上述步骤，直到拥有每个顶点。
于 2011-10-17T12:57:06.500 回答
2

“创建森林部分”真正的意思是：从页面Disjoint-set data structure实现伪代码。如果您可以阅读 C++，那么我在这里有一个非常简单的实现。（该实现有效，我自己用它来实现 Kruskal 的算法 :)

于 2011-10-17T13:21:41.917 回答