«Структуры и алгоритмы компьютерной обработки данных: система двусторонних дорог»

Графы являются обобщенными иерархическими структурами. Граф со-стоит из множества элементов данных, называемых вершинами, и множества ребер, соединяющих эти вершины попарно. Граф мы будем обозначать G = , где V - множество вершин, Е - множество ребер.

Существует много алгоритмов на графах, в основе которых лежит систе-матический перебор вершин графа, при этом каждая вершина просматривается в точности один раз. Поэтому важной задачей является нахождение хороших методов поиска в графе. Поисковые методы для бинарных деревьев имеют свои аналоги для графов. В нисходящем обходе бинарного дерева применяется такая стратегия, при которой сначала выполняется обработка узла-, а затем уже про-движение вниз по поддереву. Обобщением прямого метода прохождения для графов является поиск "сначала в глубину" {depth - first). Начальная вершина передается в качестве параметра и становится первой обрабатываемой верши-ной. По мере продвижения вниз до тупика смежные вершины запоминаются в стеке с тем, чтобы можно было к ним вернуться и продолжить поиск по друго-му пути в случае, если еще остались необработанные вершины. Обработанные вершины образуют множество всех вершин, достижимых из начальной вершины.

Постановка задачи

Задана система двусторонних дорог. Найти два города и соединяющий их путь, который проходит через каждую из дорог ровно один раз.

Разработать алгоритм решения этой задачи и написать программу.

Решение задачи

Вся задача сводится к тому чтобы найти Эйлеровый путь для выполнение этой задачи напишем алгоритм нахождения Эйлерова цикла.

Основные теоретические положеня

Эйлеровым путем в графе называется произвольный путь, проходящий через каждое ребро графа в точности один раз, т.е. путь V1, V2, Vm+1, такой, что каждое ребро е е Е появляется в последовательности V1, V2, Vm+1 в точности один раз как е = {Vi, Vi+1} для некоторого i. Если V1 = Vm+i, то такой путь назы-вается эйлеровым циклом.