На вход алгоритма подаётся связный неориентированный граф.
Для каждого ребра задаётся его стоимость.
Выбираем произвольную вершину в качестве начальной.
Она будет первой вершиной, включенное в искомое остовное дерево.
Множество вершин графа можно разделить на два подмножества:
- подмножество состоящее из вершин уже построенного остовного дерева
- остальные вершины графа.
Сортируем массив рёбер по весу в порядке возрастания.
Каждый раз добавляем к остовнуму дереву ребро с минимальным весом,
одна вершина которого уже включена в остовное дерево, а вторая нет.
Ребро включается в остовное дерево, а вторая вершина переносится
в множество вершин остовного дерева. Рост дерева происходит до тех пор,
пока не будут исчерпаны все вершины исходного графа.
Алгоритм.
