75

Лабораторная работа №5. Структуры и алгоритмы обработки данных. Нахождение эйлерова цикла в графе.

ID: 227094
Дата закачки: 30 Июня 2022
Продавец: DiKey (Напишите, если есть вопросы)
    Посмотреть другие работы этого продавца

Тип работы: Работа Лабораторная
Форматы файлов: Microsoft Office
Сдано в учебном заведении: УГАТУ

Описание:
Лабораторная работа №5. Структуры и алгоритмы обработки данных. Нахождение эйлерова цикла в графе.

Постановка задачи:
Найти эйлеров цикл в заданном графе.

Теория
Эйлеров путь (эйлерова цепь) в графе — это путь, проходящий по всем рёбрам графа и притом только по одному разу.
Эйлеров путь в графе существует тогда и только тогда, когда граф связный и содержит не более чем 2 вершины нечетной степени.
Если в связном графе нет вершин нечетной степени, то каждый эйлеров путь называется циклом.

Алгоритм нахождения эйлерова цикла графа
1. Если алгоритм обхода в глубину не посетил все вершины, то
1.1.  Выводим сообщение «Граф не содержит эйлерова цикла, так как граф несвязный».
2. Иначе
2.1.  Если количество ребер каждой какой-либо вершины нечетное, то
2.1.1. Выводим сообщение «Граф не содержит эйлерова цикла, так как не все вершины имеют четную степень».
2.2.  Иначе
2.2.1. Заносим первую вершину во временный стек.
2.2.2. Пока временный стек не пустой:
2.2.2.1. Присваиваем временной вершине значение вершины стека.
2.2.2.2. Если количество ребер временной вершины больше нуля, то
2.2.2.2.1. Заносим во временный стек первую смежную вершину.
2.2.2.2.2. Удаляем ребро, соединяющую временную вершину и ее первую смежную вершину.
2.2.2.3. Иначе
2.2.2.3.1. Вынимаем из временного стека и заносим в стек эйлерова цикла.
2.2.2.4. Выводим эйлеров цикл на экран

Входные данные:
• vertices[] – массив вершин графа.
• edges[] – массив ребер графа.

Промежуточные данные:
• stack – стек для промежуточного хранения вершин.
• cycl – стек для хранения вершин эйлерова пути.
• node – переменная для временного хранения вершины.
• adjacent – переменная для временного хранения первой смежной вершины.

Выходные данные:
• statusCycl– текстовое поле для вывода последовательности вершин эйлерова цикла.
• cycl – стек для хранения вершин эйлерова пути графа.


Комментарии: 2020

Размер файла: 118,5 Кбайт
Фаил: (.docx)

Скачать

Добавить в корзину

Занесено в корзину

        Коментариев: 0

Есть вопросы? Посмотри часто задаваемые вопросы и ответы на них.
Опять не то? Мы можем помочь сделать!

Некоторые похожие работы:

К сожалению, точных предложений нет. Рекомендуем воспользоваться поиском по базе.