我已经在 C (www.bubbllellicious.es/prim.tar.gz) 中实现了Prim 的算法，但我只是想知道如何将其转换为Kruskal 的算法。
看起来它们非常相似，但我无法想象如何将旧代码修改为新代码。给点建议什么的就好了。我知道这很容易，但我仍然是 C 编程的 n00b ......
bubblellicious
问问题
1956 次
3 回答
5
为什么不直接从头开始编写 Kruskal，看看它们在您自己的解决方案中如何比较？最好的学习方式。
于 2009-09-03T09:04:10.557 回答
1
要进行转换，您需要一个森林（即一组树，其中最初每个节点都是一棵树）作为您的临时输出结构，而不是一棵树。然后在每一步，而不是找到将当前未连接节点添加到树中的最便宜的顶点，而是在图中找到最便宜的边，如果它创建一棵新树（即连接两个先前未连接的节点），则将该树添加到森林并移除源树。否则丢弃边缘。Kruskal 的正确实现比正确的 Prim 实现更占用内存，但耗时更少。
但是两者之间的差异是相当大的。可能您只能保留一些辅助函数和一些数据结构。不是转换，而是使用更高级别的构建块进行重写。
于 2009-09-03T09:11:17.187 回答
0
为什么不考虑切换到 C++ 并使用 boost 图形库（http://www.boost.org/）？
它包含两种算法的非常好的实现。类型安全且高性能。参见kruskal_minimum_spanning_tree和prim_minimum_spanning_tree
于 2009-09-03T10:25:48.770 回答