Алгоритми та структури даних · Senior · Запитання 46 з 75
Який алгоритм використати для пошуку циклу в імпортах модулів під час збірки?
- 1Union-find по всіх ребрах імпортів
- ✓Правильна відповідь: DFS із трьома станами або алгоритм Кана
- 3Алгоритм Дейкстри з кожного модуля
Пояснення
Імпорти утворюють орієнтований граф; цикл - це зворотне ребро в DFS або вершини, що лишилися після топологічного сортування Кана. Union-find знаходить цикли лише в неорієнтованих графах, тож повідомив би про хибні цикли для «ромбів».