ЛР. Алгоритм Прима

Post date: Apr 18, 2011 8:50:13 AM

Эта ЛР является продолжением предыдущей. Написанная программа должна выполнять построение минимального остовного дерева как с помощью алгоритма Краскала, так и с помощью алгоритма Прима.

Постановка задачи

Необходимо разработать программу, реализующую алгоритм Прима для построения минимального остовного дерева.

Требования:

• для работы с графом необходимо реализовать класс, использующий одно из следующих представлений графа: матрица смежности, матрица инцидентности, список смежности (см. ниже);
• для реализации приоритетной очереди необходимо использовать: d-кучи, АВЛ-деревья, упорядоченные таблицы (см. ниже);
• после завершения работы алгоритма Прима с выбранной реализацией приоритетной очереди необходимо вывести суммарную трубоёмкость при выполнении операции обновления данных, добаления элементов и удаления элементов из приоритетной очереди;
• программа должна позволять задавать граф вручную (с помощью GUI или из файла);
• программа должна позволять генерировать графы автоматически с указанным количеством вершин (графы должны быть взвешенными связными неориентированными);
• программа должна визуально отображать граф и выделять цветом ребера, входящие в полученное минимальное остовное дерево (визуализация может быть выполнена любым образом, например с использованием библиотеки GLEE);
• программа должна предоставлять возможность работать "по шагам", подсвечивая текущее обрабатываемое ребро;
• программа должна иметь возможность построения минимального остовного дерева с помощью алгоритма Краскала.

Ищите свою фамилию в списке (82-02), порядковый номер - соответствует представлениям и арностям d-кучи, которые необходимо реализовать:

1. Представление графа с помощью матрицы инцидентности. 2-кучи.
2. Представление графа с помощью списка смежности. 3-кучи.
3. Представление графа с помощью матрицы смежности. 4-кучи.
4. Представление графа с помощью матрицы инцидентности. 5-кучи.
5. Представление графа с помощью списка смежности. 2-кучи.
6. Представление графа с помощью матрицы смежности. 3-кучи.
7. Представление графа с помощью матрицы инцидентности. 4-кучи.
8. Представление графа с помощью списка смежности. 5-кучи.
9. Представление графа с помощью матрицы смежности. 6-кучи.

По лабораторной работе необходимо предоставить отчёт (шаблон отчёта).

Сдача отчёта должна быть осуществлена не позднее, чем через неделю после сдачи программы.

Для сдачи работы исходники работающего проекта и отчёт необходимо загрузить в "свою" директорию репозитория под "своим" аккаунтом (правила работы с репозиторием).

На выполнение лабораторной работы отводится 3 недели.

Dead Line: 23:59 30.04.2011