Как превратить алгоритм Прима в алгоритм Крускаля?

Question

Я внедрил Prim's algorithm в C (www.bubblellicious.es/prim.tar.gz), но мне просто интересно, как превратить это в Kruskal's algorithm.

Кажется, они очень похожи, но я не могу представить, как изменить свой старый код на новый. Было бы вкусно, если бы вы дали какие-то советы или что-то еще. Я знаю, что это легко, но я все еще n00b в программировании на C ...

Answer 1

Почему бы не просто написать Kruskal с нуля и посмотреть, как они сравниваются в ваших собственных решениях? Лучший способ учиться.

Answer 2

Для преобразования вам нужен лес (т. Е. Набор деревьев, где первоначально каждый узел является деревом), как ваша временная структура вывода, а не одно дерево. Затем, на каждом шаге, вместо того, чтобы находить самую дешевую вершину, которая добавляет в данный момент не связанный узел, вы найдете самое дешевое ребро в графе и, если оно создает новое дерево (т. Е. Соединяет два ранее несвязанных узла), добавьте это дерево к леса и удалить исходные деревья. В противном случае отбросьте край. Правильная реализация Kruskal более интенсивна в памяти, но меньше времени, чем правильная реализация Prim.

Но различия между ними довольно велики. Вероятно, все, что вы можете сохранить, - это некоторые вспомогательные функции и некоторые структуры данных. Не конверсия, больше переписывайте, используя более высокие строительные блоки.

Answer 3

Почему вы не переходите на C++ и используете библиотеку ускорителей (http://www.boost.org/)?

Он содержит очень хорошие реализации для обоих алгоритмов. Тип-безопасный и высокоэффективный. См. kruskal_minimum_spanning_tree и prim_minimum_spanning_tree