Описание тега kruskals-algorithm

Алгоритм, впервые описанный Джозефом Крускалом, для поиска минимального остовного дерева для связного взвешенного графа с использованием жадного поиска.

Общее описание алгоритма, взятое из Википедии, выглядит следующим образом:

• Создайте лес F (набор деревьев), где каждая вершина в графе представляет собой отдельное дерево
• Создайте набор S, содержащий все ребра в графе
• Пока S непусто, а F еще не охватывает
  • Удалите кромку с минимальным весом из S
  • Если это ребро соединяет два разных дерева, добавьте его в лес, объединив два дерева в одно дерево.

По завершении алгоритма лес образует минимальный остовный лес графа. Если граф связан, лес состоит из одного компонента и образует минимальное остовное дерево.