графы и деревья

Специальность : Информатика и вычислительная техника

Предмет :алгоритмитизация

Сама работа

Методические рекомендации:

1. Графы

Задание:

1.1 Вид графа для примера представлен в файле

1.2 Варианты заданий по графам представлены в методичке - это файл

Задания по Деревьям - Лаб работа N 2 и Графам - Лаб работа N 2. Выполняем по своим вариантам согласно порядковому номеру в списке.

1.3 Реализовать Алгоритмы на C++:

1)Обход в ширину.

2)Обход в глубину.

3)Алгоритм Дейкстры.

1.4 Требования:

1) Пользовательский интерфейс - инструменты по решению разработчика (Windows Forms, например).

2) Визуализация графа с использованием любой доступной графической библиотеки – SFML(Предпочтительно), SDL, OpenGL ( пример реализации представлен в файле:

3) Реализованные алгоритмы должны справляться не только с графом, представленным автором, а также применяться к другим Графам.

4) Необходимы функции для редактирования графа: Создание(добавление) и удаление вершины и ребра. Редактирование весов ребер. Редактирование матрицы смежности (или инцидентности - в зависимости от реализации).

1.5 Выполнить отчет:

- постановка задачи;

-анализ задачи с разбором применения используемых структур данных, функций;

- код программы на C++ с подробными комментариями;

- скриншоты работы программы;

- визуализация решения.

БЛОК-СХЕМ НЕ НАДО.

2. Деревья

2.1 Требуется реализовать бинарное дерево поиска.

2.2 Реализовать допустимые операции для дерева:

- Вставка узла.

- Удаление узла.

- Поиск элемента по ключу.

2.3 Реализовать алгоритмы обхода дерева:

1) Прямой

2) Симметричный

3) Обратный

2.4 Реализовать алгоритм балансировки дерева.

2.5 Реализовать вертикальную и горизонтальную печать.

2.6 Визуализация дерева с использованием любой доступной графической библиотеки – SFML(Предпочтительно), SDL, OpenGL…

2.7 Пользовательский интерфейс – на усмотрение разработчика.

2.8 Выполнить отчет:

- постановка задачи;

-анализ задачи с разбором применения используемых структур данных, функций;

- код программы на C++ с подробными комментариями;

- скриншоты работы программы;

- визуализация решения;

БЛОК-СХЕМ НЕ НАДО.

Методические пособия и задания:

Теория по графам и деревьям:

Постановка задач по деревьям и графам: (выше в задании упомянута).

Теория по графам:

Визуализация деревьев” (выше в задании упомянута) и “Графы”.

Презентация по графам - теория:

Варианты заданий по графам: (выше в задании упомянута).

Моделирование на UML пособие:

76606