Реализация алгоритма Крускала в Аде, не знаю, с чего начать

Question

Ссылаясь на алгоритм Крускала в Аде, я не уверен, с чего начать.

Я пытаюсь все обдумать, прежде чем писать программу, но довольно растерялся относительно того, какие структуры данных мне следует использовать и как представлять все.

Моя первоначальная мысль состоит в том, чтобы представить полное дерево в списке смежности, но, читая Википедию, алгоритм утверждает, что 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

Я вижу, где их описание алгоритма могло бы вас запутать, как начать.Это оставило меня таким же образом.

Я бы посоветовал прочитать более позднюю Пример раздела .Это довольно ясно показывает, как действовать дальше, и вы, вероятно, можете придумать структуры данных, которые вам понадобятся для этого.

Похоже, основная идея заключается в следующем:

• Возьмите график, найдите самое короткое ребро, которое вводит хотя бы одну новую вершину, и поместите его в ваше "связующее дерево".
• Повторяйте шаг выше, пока у вас не будет каждой вершины.

Answer 2

«Создать часть леса» действительно означает: реализовать псевдокод со страницы Структура данных с несвязанным набором .Если вы можете читать C ++, то у меня есть довольно простая реализация здесь .(Эта реализация работает, я сам использовал ее для реализации алгоритма Крускала:)