Длина кратчайшего цикла в ненаправленном графике

Question

Мне дается алгоритм, который должен найти длину кратчайшего цикла в ненаправленном графе с длинами единичных краев. Я должен показать, что алгоритм не всегда работает, предоставляя контрпример. У меня возникают проблемы с примером, который может показать, что этот алгоритм не всегда работает.

---

Алгоритм:

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

---

Любые предложения/помощь будет оценена

Answer 1

Посмотрите на этот график с заданным обходе:

Когда вы сталкиваетесь backedge e->a вы отмечаете цикл с длиной 5 и для e->b - цикл с длиной 4. Однако ответ 3, полученный по циклу a-b-e.