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

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