ЛР. Алгоритм Краскала
Post date: Mar 16, 2011 1:43:25 PM
Постановка задачи
Постановка задачи
Необходимо разработать программу, реализующую алгоритм Краскала для построения минимального остовного дерева с использованием разделённых множеств.
Требования:
- для работы с графом необходимо реализовать класс, использующий одно из следующих представлений графа: матрица смежности, матрица инцидентности, список смежности (см. ниже);
- для работы с разделёнными множествами необходимо реализовать класс, использующий одно из следующих представлений разделённых множеств: с помощью массивов, с помощью древовидной структуры, с помощью древовидной структуры и использованием рангов вершин (см. ниже);
- программа должна позволять задавать граф вручную (с помощью GUI или из файла);
- программа должна позволять генерировать графы автоматически с указанным количеством вершин (графы должны быть взвешенными связными неориентированными);
- программа должна визуально отображать граф и выделять цветом ребера, входящие в полученное минимальное остовное дерево (визуализация может быть выполнена любым образом, например с использованием библиотеки GLEE);
- программа должна предоставлять возможность работать "по шагам", подсвечивая текущее обрабатываемое ребро;
- для сортировки ребёр необходимо использовать сортировку с помощью d-куч.
Ищите свою фамилию в списке (82-02), порядковый номер - соответствует представлениям, которые необходимо реализовать:
- Представление графа с помощью матрицы смежности. Представление разделённых множеств с помощью массива.
- Представление графа с помощью матрицы инцидентности. Представление разделённых множеств с помощью древовидной структуры.
- Представление графа с помощью списка смежности. Представление разделённых множеств с помощью древовидной структуры и использованием рангов вершин.
- Представление графа с помощью матрицы смежности. Представление разделённых множеств с помощью древовидной структуры.
- Представление графа с помощью матрицы инцидентности. Представление разделённых множеств с помощью древовидной структуры и использованием рангов вершин.
- Представление графа с помощью списка смежности. Представление разделённых множеств с помощью массива.
- Представление графа с помощью матрицы смежности. Представление разделённых множеств с помощью древовидной структуры и использованием рангов вершин.
- Представление графа с помощью матрицы инцидентности. Представление разделённых множеств с помощью массива.
- Представление графа с помощью списка смежности. Представление разделённых множеств с помощью древовидной структуры.
По лабораторной работе необходимо предоставить отчёт (шаблон отчёта).
Сдача отчёта должна быть осуществлена не позднее, чем через неделю после сдачи программы.
Для сдачи работы исходники работающего проекта и отчёт необходимо загрузить в "свою" директорию репозитория под "своим" аккаунтом (правила работы с репозиторием).
На выполнение лабораторной работы отводится 3 недели.
Dead Line: 23:59 05.04.2011