ефективний алгоритм ідентифікації циклу у спрямованому графі? [дублікат] - алгоритм, граф, теорія складності, теорія графів, спрямований граф

Можливі дублікати:
Кращий алгоритм виявлення циклів у спрямованому графі

Я шукаю алгоритм, щоб знайти петлі у спрямованому графі.

Мій графік має мітки лише в вузлах, а не в краях, і це може стати досить великим.

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

Графіки, які я використовую, найімовірніше матимуть лише один зв'язаний компонент і не мають сильно з'єднаних компонентів. Очікується, що кількість циклів буде низькою (я все ще повинен це перевірити).

Будь-який хороший алгоритм для саме цього чи щось подібного вітається.

Велике спасибі.

PS: Якщо щось незрозуміло, не соромтеся попросити мене про деталі, наприклад, граф зберігається (поки що) як набір наборів країв, від одного вузла до декількох вузлів, як правило, до одного, це має бути недоречним, IMHO.

Відповіді:

Подібне питання було задано, і хтось надав дуже детальну відповідь, яка може вам допомогти - Пошук всіх циклів у спрямованому графіку