Алгоритми та структури даних · Middle · Запитання 33 з 75
Як знайти цикл в орієнтованому графі за допомогою DFS?
- 1Будь-яке ребро до вже відвіданої вершини означає цикл
- 2Цикл є, якщо хоч одна вершина має понад одне вихідне ребро
- ✓Правильна відповідь: Відстежувати поточний шлях DFS: ребро назад у нього означає цикл
Пояснення
Використовуйте три стани: не відвідана, в обробці (на стеку) і завершена. Лише ребро до вершини «в обробці» є зворотним. Ребро до завершеної вершини нормальне: це просто ще один шлях до того самого місця.