Лабораторная работа №4. Структуры и алгоритмы обработки данных. Поиск в глубину в графе.

Лабораторная работа №4. Структуры и алгоритмы обработки данных. Поиск в глубину в графе.

Постановка задачи:
Задан граф. Осуществить прохождение вершин заданного графа в соответствии с обходом этого графа согласно алгоритму «Поиск в глубину» в порядке возрастания первоначальной нумерации вершин графа.

Алгоритм прохождения вершин графа
1. Заносим в стек первую вершину.
2. Заносим в список посещенных первую вершину.
3. Выделяем визуально первую вершину.
4. Пока количество элементов в стеке больше нуля:
4.1.  Текущей вершине приравниваем вершину стека.
4.2.  Перебираем все вершины графа:
4.2.1. Если эта вершина имеет общее ребро с текущей и эта вершина не содержится в списке посещенных, то
4.2.1.1. Заносим эту вершину в стек.
4.2.1.2. Заносим эту вершину в список посещенных.
4.2.1.3. Выделяем визуально ребро, соединяющее текущую и эту вершину.
4.2.1.4. Выделяем визуально эту вершину.
4.3.  Если у текущей вершины нет смежных вершин, то
4.3.1. Удаляем вершину стека.

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

Вспомогательные данные:
• vertices – список вершин графа.
• stack – стек для промежуточного хранения вершин графа.
• visited – список посещенных вершин графа.
• node – переменная для временного хранения вершины графа.

Выходные данные:
• statusObhod – текстовое поле для вывода последовательности прохождения графа.

2020