Большая сложность нахождения циклов в неориентированном графе

Question

Мне нужно найти сложность нахождения всех циклов в неориентированном графе, состоящем из 50 узлов. Более того, если график станет большим, изменится ли сложность и что будет, если сеть станет значительно больше. Кроме того, если я нахожу только несколько циклов, то как мне найти сложность нахождения нескольких циклов в графе.

Благодарю вас в ожидании!

Answer 1

У данного графа может быть экспоненциальное количество циклов (в размере графа).Рассмотрим двудольный граф, где v _i подключен к w _{i + 1% n} , а w _i подключен к v _{i + 1% n} .

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

Конечно, на практике вы можете найти решения, которые намного быстрее, чем это.

Answer 2

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

Я полагаю, что это O(V+E) подход, где V - это число вершин или узлов, а E - это число ребер или соединений.

Если вы поместите узлы в определенную ветвь в стек, вы также можете легко определить путь цикла. Просто убедитесь, что каждый раз, когда вы возвращаетесь назад, выскакиваете узел.