Разработать алгоритм для обнаружения цикла в графе G

Question

Как будет выглядеть следующий алгоритм:

алгоритм с линейным временем, который, учитывая неориентированный граф G и конкретное ребро e в нем, определяет, имеет ли G цикл, содержащий e

У меня есть следующая идея:

для каждого v, которое принадлежит V, если v является потомком e и (e, v) не было пройдено, тогда проверьте следующее:

, если мыпосетили e до v и оставили v до того, как мы покинули e, тогда график содержит цикл

Answer 1

Согласно подсказке грядущей бури, ненаправленное ребро само по себе является циклом. A <-> B взад и вперед столько раз, сколько хотите.

Answer 2

Я не уверен, что это ваша домашняя работа, поэтому я просто дам небольшую подсказку - используйте свойства дерева поиска в ширину (с корнем в любой из двух вершин ребра e), его поддеревья, которые являютсяопределяется соседями корня и ребер между этими поддеревьями.