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