Для определения наличия цикла в неориентированном графе можно использовать обход в глубину. 13

Алгоритм: 3

1. Создать стек вершин — маршрут от начальной вершины до текущей, по которому до неё добрались. 3
2. Завести множество вершин V, которые уже посетили. 3
3. Для каждой вершины помнить, из какой вершины в неё пришли (словарь P) при обходе. 3
4. Если при обходе увидеть в числе соседей вершины уже посещённую вершину K, которая не входит в текущий стек вершин, то «разматывать» путь от K до изначальной вершины, используя информацию из словаря P. 3 Это в совокупности со стеком вершин даст цикл. 3
5. Если K входит в стек вершин, то циклом будет часть стека от K до вершины стека. 3

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