SummerPractice

Репозиторий для летней практики 2020

Спецификация:

Описание задачи:

Визуализация работы алгоритма построения минимального остовного дерева (алгоритм Краскала).

Теория

Жадный алгоритм - на каждом шаге делается лучшая для данного момента операция.

Идея алгоритма в следующем - в множество E' остовного дерева G' = (V, E') графа G = (V, E) в порядке невозростания весов добавляются рёбра.

• Если очередное ребро соединяет вершины одной компоненты связности G', то добавление его создаст цикл.

• Если же оно соединяет вершины разных компонент, то по теореме о минимальном ребре оно безопасно и может быть включено в граф.

Псевдокод

G = (V, E)      // исходный граф
G' = (V', E')   // результат алгоритма
V' ← V
E' ← ∅
for (uv ∈ E ordered by w(u,v))
	if (Component(u) ≠ Component(v))
        E' ← uv

План разработки

План выполенния

• Обсуждение задания, распределение ролей, выбор необходимых средств разработки и структур данных
• Реализация структур данных
• Реализация алгоритма Краскала
• Реализация прототипа GUI
• Реализация графического ввода графа
• Реализация основного GUI
• Реализация дополнительного функционала GUI
• Тестирование

Распределение ролей

• Крыжановский Кирилл, гр. 8303
  • разработка алгоритма
  • gui
• Кибардин Антон, гр. 8303
  • расширение возможностей gui
  • оптимизирование алгоритмов
• Спирин Никита, гр. 8303
  • тестирование
  • слияние наработок

---

Информация по ведению проекта

• Делаем pull-request и описание к нему на русском языке (чтобы нам легче понимать друг друга).
• Commit'ы делать осмысленными. Чтобы не было что-то вроде fix, some fixes, и другое
• Текущие задачи отображаются в Issue. В них же указываются ошибки программы.
• Pull-request отображает выполнение одного (в некоторых случаях нескольких) пункта задач