В чем заключается алгоритм построения замкнутых маршрутов на графе?

Возможно, имелся в виду алгоритм построения эйлерова цикла — замкнутого маршрута, в котором каждое ребро графа встречается точно один раз. new2.intuit.ru

Алгоритм похож на поиск в глубину. new2.intuit.ru Начинают с произвольно выбранной стартовой вершины и строят путь, выбирая каждый раз для дальнейшего продвижения ещё не пройденное ребро. new2.intuit.ru При этом как пройденные помечают именно рёбра, а не вершины. new2.intuit.ru

Вершины пути накапливаются в стеке. new2.intuit.ru Через некоторое количество шагов наступает тупик: все рёбра, инцидентные активной (последней посещённой) вершине, уже пройдены. new2.intuit.ru Так как степени всех вершин графа чётны, в этот момент пройденные рёбра образуют цикл, но он может включать не все рёбра графа. new2.intuit.ru

Чтобы обнаружить ещё не пройденные рёбра, возвращаются по пройденному пути, перекладывая вершины из стека в другой стек, пока не встретят вершину, которой инцидентно непройденное ребро. new2.intuit.ru

Также существует метод ветвей и границ («поиск с возвратом», «backtracking») для поиска замкнутого маршрута в большом графе. habr.com Он основан на разбиении множества на два непересекающихся подмножества и на вычислении оценок каждого из них. habr.com