Какой лучший (по временной сложности) алгоритм для нахождения цикла в ориентированном графе?

Question

Также есть какие-то рандомизированные алгоритмы для этого.Мне нужно найти один цикл как можно быстрее, а не все циклы.

Answer 1

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

Answer 2

Я не знаю, что это возможно сделать в общем случае, но если вы знаете определенные свойства графика (такие как «расстояние от цикла-свободности», как описано в статье ниже), существуют рандомизированныеалгоритмы, которые с высокой вероятностью быстро найдут цикл.В частности, см. Первый алгоритм в разделе 3 связанной статьи с соответствующим анализом, объясняющим, как извлечь цикл.

Что касается детерминированных алгоритмов, ответ г-на Саурава является правильным.В худшем случае вам, по крайней мере, придется сканировать весь ввод, чтобы правильно определить, существует ли цикл, для которого уже требуется время O (| V | + | E |).

[1] http://arxiv.org/abs/1007.4230

Answer 3

Какой лучший (по временной сложности) алгоритм поиска цикла в ориентированном графе?

Алгоритм сильносвязанных компонент Тарьяна . Временная сложность, если O (| V | + | E |).