Задание 4. Тема Основные алгоритмы на графах выделение компонент сильной связности в ориентированном графе кратчайшие пути, остовные деревья
 Скачать 15.22 Kb.
|
Практическое задание 4Тема 6.2. Основные алгоритмы на графах: выделение компонент сильной связности в ориентированном графе; кратчайшие пути, остовные деревья Формулировка задания 4 1. Реализуйте программу, в которой выполняется алгоритм обхода графа на основе поиска в глубину. 2. Реализуйте программу, в которой выполняется алгоритм обхода графа на основе поиска в ширину. 3. Используйте обход графа в ширину для определения всех вершин графа, находящихся на фиксированном расстоянии d от данной вершины. 4. Реализуйте программы, в которых выполняются алгоритм Дейкстры и алгоритм Флойда. 5. Реализуйте программу, в которой определяется минимальное остовное дерево графа. Указания к выполнению работы При выполнении лабораторной работы для каждого задания требуется написать программу на языке C++, которая получает на входе числовые данные, выполняет их обработку в соответствии с требованиями задания и выводит результат на экран. Для обработки данных необходимо реализовать алгоритмы обхода графа в соответствии с постановкой задачи. Ввод данных осуществляется из файла с учетом требований к входным данным, содержащихся в постановке задачи. Ограничениями на входные данные является допустимый диапазон значений используемых числовых типов в языке C++. Выполнять задание необходимо в соответствии с приведенными ниже этапами: • разработать графическую схему алгоритмов; • записать алгоритмы на языке C++; • разработать контрольный тест к программе; • отладить программу; • представить отчет по работе. Требования к отчету Структура отчета должна соответствовать приведенным выше этапам: • титульный лист; • алгоритм решения задачи. Схема алгоритма выполняется по ЕСПД (ГОСТ 19.003-80 и ГОСТ 19.002-80); • листинг программы; • контрольный тест; • выводы. |