Студент

Бурдастых Андрей

Задача

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

Состояние

Завершено

Баллов

5

Дедлайн

Назначено

29.09.2014, 12:05

Завершено

27.10.2014, 16:14

Построить минимальное остовное дерево из точек на плоскости.

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

Текстовый файл с набором пар координат на плоскости.

<pont_id1>, <x1>, <y1>
<pont_id2>, <x2>, <y2>
...

Пример:

1, 7, 5
2, 3, -11
3, 2, -2
4, -1, -8
5, 14, -14

Файл может содержать пустые и невалидные строки. Программа должна корректно это обрабатывать.

Задача

Необходимо связать множестве точек на плоскости таким образом, чтобы сумма длин рёбер была минимальна. Для решения задачи необходимо использовать Алгоритм Крускала. Длинна ребра между любой парой точек вычисляется стандартно, как геометрическое расстояние между точками.

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

Текстовый файл, описывающий ребра построенного дерева:

<pont_id1> - <pont_id2>
...

Пример:

1 - 3
2 - 4
2 - 5
3 - 4

Тестирование

Для всех разработанных модулей должны быть созданы наборы unit тестов. Функций ввода/вывода нужно тестировать с помощью std::stringstream.