Курсовая работа

Задание на курсовую работу

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

Цель

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

• сортировка
• обход графов (в глубину и в ширину)
• хранение графов (списки смежности, матрицы смежности, инцидентности)
• построение системы непересекающихся множеств

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

Любой текстовый файл, содержащий матрицу смежности графа в виде:

 A  B  C
 0  3  1
 3  0  2
 1  2  0

где первая строка содержит через пробел список всех рёбер, за которым следует матрица смежности. В матрице значение 0 стоит, если ребра между вершинами нет, и положительное число, которое соответствует весу, когда ребро между вершинами существует.

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

A C
B C
3

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

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

• Программный код с собственными реализациями всех предлагаемых структур и алгоритмов, описанных в целях курсовой работы.
• Отчёт по шаблону https://etu.ru/assets/files/3004_3_ShABLON-kursovika.doc с описанием выбранных алгоритмов сортировки, обхода графов и СНМ.
• При защите курсовой работы необходимо ответить на 3 любых вопроса по программному коду или алгоритмам описанных в отчёте.

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

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