ЛР. Алгоритм Краскала

Post date: Mar 16, 2011 1:43:25 PM

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

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

Требования:

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

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

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

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

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

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

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

Dead Line: 23:59 05.04.2011