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

Лабораторная работа №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