如何将Prim算法转化为Kruskal算法？
我已经用 C 实现了 Prim 算法 (www.bubbllellicious.es/prim.tar .gz），但我只是想知道如何将其转换为 Kruskal 算法。
看起来它们非常相似，但我无法想象如何将旧代码修改为新代码。如果您能提供一些建议或其他什么，那就太好了。我知道这很简单，但我在 C 编程方面仍然是个菜鸟......
I've implemented Prim's algorithm in C (www.bubblellicious.es/prim.tar.gz) but I was just wondering how to transform this into Kruskal's algorithm.
It seems they're quite similar, but I can't imagine how can I modify my old code into that new one. It'd be delicious if you give some advices or something. I know that's easy, but I'm still a n00b in C programming ...
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
为什么不从头开始编写 Kruskal 的解决方案，然后看看它们在您自己的解决方案中的比较情况如何？最好的学习方式。
Why not just write Kruskal's from scratch and see how they compare in your own solutions? Best way to learn.
要进行转换，您需要一个森林（即一组树，其中最初每个节点都是一棵树）作为临时输出结构而不是一棵树。然后在每一步中，您不是找到将当前未连接的节点添加到树中的最便宜的顶点，而是找到图中最便宜的边，并且如果它创建了一个新树（即连接两个先前未连接的节点），则将该树添加到森林并移除源树。否则丢弃边缘。
与正确的 Prim 实现相比，Kruskal 的正确实现需要更多内存，但时间消耗更少。
但两者之间的差异是相当大的。也许您可以保留的只是一些辅助函数和一些数据结构。不是转换，更多的是使用更高级构建块的重写。
To convert you need a forest (i.e. a set of trees where initially each node is a tree) as your temporary output structure rather than a single tree. Then on each step, rather than finding the cheapest vertex that adds a currently unconnected node to your tree, you find the cheapest edge in the graph and, if it creates a new tree (i.e. connects two previously unconnected nodes) add that tree to the forest and remove the source trees. Otherwise discard the edge.
A proper implementation of Kruskal is more memory intensive but less time intensive than a proper Prim implementation.
But the differences between the two are quite large. Probably all you can keep between are some helper functions and some data structures. Not a conversion, more a rewrite using more high level building blocks.
为什么不考虑切换到 C++ 并使用 boost 图形库
（http://www.boost.org/）？
它包含两种算法的非常好的实现。类型安全且高性能。
请参阅 kruskal_minimum_spanning_tree 和 prim_minimum_spanning_tree
Why dont you consider switching to C++ and using the boost graph library
(http://www.boost.org/)?
It contains very well implementations for both algorithms. Type-safe and highly performant.
See kruskal_minimum_spanning_tree and prim_minimum_spanning_tree