(Росдистант). Алгоритмы и структуры данных. Практическое задание 4

ВНИМАНИЕ! Работа в своем роде уникальна, выполнена на отлично, НО! ДАННАЯ РАБОТА ЯВЛЯЕТСЯ ШАБЛОНОМ! Не стоит переписывать ее слово в слово! Ведь Вы не единственный скачавший ее!

Вся работа отталкивается от первого графа (рисунок 1). Он взят произвольно. Соответственно все дальнейшие решения идут от него! Постройте свой граф на примере моего и, воспользуясь учебными материалами, переделайте данную работу под себя. Измените текстовые формулировки всего текста своими словами, измените начертание рисунка 1 (перекрасьте, вытяните, и т.д.). Исходя из данных вашего измененного графа, измените при помощи паинта или другого редактора рисунки 2, 3, 4, 5, 6, 7… Ведь данные не могут быть одинаковыми у нескольких человек…

ИНАЧЕ ПРЕПОДАВАТЕЛЬ РАБОТУ ПРОСТО НЕ ПРИМЕТ.

В конце задачи есть "исходный код программы" - сама программа на пару листов. Удалите его, чтобы отличаться от того, кто Вас опередил (он не обязателен). Предъявите преподавателю, если потребует.

Тема 4.4. Остовные деревья. Остовные деревья в графе. Минимальное остовное дерево: алгоритмы Прима и Крускала

Формулировка задания № 4

1. Реализуйте программу, в которой выполняется алгоритм обхода графа на основе поиска в глубину.

2. Реализуйте программу, в которой выполняется алгоритм обхода графа на основе поиска в ширину.

3. Используйте обход графа в ширину для определения всех вершин графа, находящихся на фиксированном расстоянии d от данной вершины.

4. Реализуйте программы, в которых выполняются алгоритм Дейкстры и алгоритм Флойда.

5. Реализуйте программу, в которой определяется минимальное остовное дерево графа.