ЛР. Алгоритм Прима
Post date: Apr 18, 2011 8:50:13 AM
Эта ЛР является продолжением предыдущей. Написанная программа должна выполнять построение минимального остовного дерева как с помощью алгоритма Краскала, так и с помощью алгоритма Прима.
Эта ЛР является продолжением предыдущей. Написанная программа должна выполнять построение минимального остовного дерева как с помощью алгоритма Краскала, так и с помощью алгоритма Прима.
Постановка задачи
Постановка задачи
Необходимо разработать программу, реализующую алгоритм Прима для построения минимального остовного дерева.
Требования:
- для работы с графом необходимо реализовать класс, использующий одно из следующих представлений графа: матрица смежности, матрица инцидентности, список смежности (см. ниже);
- для реализации приоритетной очереди необходимо использовать: d-кучи, АВЛ-деревья, упорядоченные таблицы (см. ниже);
- после завершения работы алгоритма Прима с выбранной реализацией приоритетной очереди необходимо вывести суммарную трубоёмкость при выполнении операции обновления данных, добаления элементов и удаления элементов из приоритетной очереди;
- программа должна позволять задавать граф вручную (с помощью GUI или из файла);
- программа должна позволять генерировать графы автоматически с указанным количеством вершин (графы должны быть взвешенными связными неориентированными);
- программа должна визуально отображать граф и выделять цветом ребера, входящие в полученное минимальное остовное дерево (визуализация может быть выполнена любым образом, например с использованием библиотеки GLEE);
- программа должна предоставлять возможность работать "по шагам", подсвечивая текущее обрабатываемое ребро;
- программа должна иметь возможность построения минимального остовного дерева с помощью алгоритма Краскала.
Ищите свою фамилию в списке (82-02), порядковый номер - соответствует представлениям и арностям d-кучи, которые необходимо реализовать:
- Представление графа с помощью матрицы инцидентности. 2-кучи.
- Представление графа с помощью списка смежности. 3-кучи.
- Представление графа с помощью матрицы смежности. 4-кучи.
- Представление графа с помощью матрицы инцидентности. 5-кучи.
- Представление графа с помощью списка смежности. 2-кучи.
- Представление графа с помощью матрицы смежности. 3-кучи.
- Представление графа с помощью матрицы инцидентности. 4-кучи.
- Представление графа с помощью списка смежности. 5-кучи.
- Представление графа с помощью матрицы смежности. 6-кучи.
По лабораторной работе необходимо предоставить отчёт (шаблон отчёта).
Сдача отчёта должна быть осуществлена не позднее, чем через неделю после сдачи программы.
Для сдачи работы исходники работающего проекта и отчёт необходимо загрузить в "свою" директорию репозитория под "своим" аккаунтом (правила работы с репозиторием).
На выполнение лабораторной работы отводится 3 недели.
Dead Line: 23:59 30.04.2011