Поиск минимального остова методом Краскала

Задача

Реализовать алгоритм поиска минимального остова на основе алгоритма Краскала (Крускала).

Цель

Продемонстрировать знания следующих вопросов:

  1. сортировка
  2. обход графов
  3. хранение графов
  4. построение системы непересекающихся множеств

Входные данные

Любой текстовый файл или введённый через консоль набор троек:

A B 3
B C 2
A C 1

Результат в виде отсортированных по имени пар и суммарный вес:

A C
B C
3

Максимальный размер входных данных: 50 вершин. Вершины могут быть заданы любой текстовой последовательностью без пробелов. Вес ребра ограничен интервалом от 0 до 1023 включительно.

Что нужно сдать

— Программный код с собственными реализациями всех предлагаемых структур и алгоритмов, описанных в целях курсовой работы.
— Отчёт по шаблону с описанием выбранных алгоритмов сортировки, обхода графов и СНМ.
— При защите курсовой работы необходимо ответить на 3 любых вопроса по программному коду или алгоритмам описанных в отчёте.

Примеры вопросов

— Какая сложность у предложенного алгоритма?
— Поясните конкретный блок кода и что он делает?
— Что такое обход графа в ширину/глубину и как они реализуются?

Сообщить об опечатке

Текст, который будет отправлен нашим редакторам: