Алгоритм для минимального цикла, включая определенную вершину

Question

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

Другими словами, если вершина v1 участвует в двух циклах, скажем один с v1, v2, v3, а другой v1, v2, v4, v5, v6. Я хочу, чтобы алгоритм дал мне v1, v2, v3 цикл в качестве выхода.

Кто-нибудь знает, какой алгоритм это сделает?

Также может быть сложность этого алгоритма.

Заранее спасибо.

Answer 1

Запустите bfs из данной вершины v0. Остановитесь, как только bfs рассмотрит вершину v1, смежную с v0, а v0 не является родителем v1 в дереве bfs. Найденный путь от края v0 до v1 plus (v1, v0) - ваш самый короткий цикл. Сложность - O (n + m) из-за bfs.