Kruskal's Algorithm

Kruskal's Algorithm

Алгоритм Крускала

Алгоритм Крускала — популярный метод нахождения минимального остовного дерева (MST) графа.
Это жадный алгоритм, который строит остовное дерево, добавляя рёбра по одному из множества всех рёбер графа.

Ключевая идея заключается в том, чтобы:

• начать с того, что каждая вершина образует отдельное дерево;
• постепенно объединять эти деревья, добавляя рёбра минимального веса, не образующие циклов.

Шаги алгоритма

• Сортировка рёбер
  Отсортировать все рёбра графа в неубывающем порядке по их весу.

• Инициализация
  Создать лес $F$, состоящий из $n$ деревьев, где каждое дерево содержит ровно одну вершину.

• Выбор рёбер
  Повторять следующие действия, пока лес $F$ не станет одним деревом:

  • взять наименьшее по весу ребро, которое не создаёт цикл (его концы принадлежат разным деревьям);
  • добавить это ребро в лес $F$, объединив два дерева.

• Результат
  Полученный лес $$ является минимальным остовным деревом графа.