Поиск минимального остова методом Краскала
Задача
Реализовать алгоритм поиска минимального остова на основе алгоритма Краскала (Крускала).
Цель
Продемонстрировать знания следующих вопросов:
- сортировка
- обход графов
- хранение графов
- построение системы непересекающихся множеств
Входные данные
Любой текстовый файл или введённый через консоль набор троек:
A B 3 B C 2 A C 1
Результат в виде отсортированных по имени пар и суммарный вес:
A C B C 3
Максимальный размер входных данных: 50 вершин. Вершины могут быть заданы любой текстовой последовательностью без пробелов. Вес ребра ограничен интервалом от 0 до 1023 включительно.
Что нужно сдать
— Программный код с собственными реализациями всех предлагаемых структур и алгоритмов, описанных в целях курсовой работы.
— Отчёт по шаблону с описанием выбранных алгоритмов сортировки, обхода графов и СНМ.
— При защите курсовой работы необходимо ответить на 3 любых вопроса по программному коду или алгоритмам описанных в отчёте.
Примеры вопросов
— Какая сложность у предложенного алгоритма?
— Поясните конкретный блок кода и что он делает?
— Что такое обход графа в ширину/глубину и как они реализуются?