Algorytmy i struktury danych · Senior · Pytanie 46 z 75
Którego algorytmu użyć do wykrycia cyklu w importach modułów podczas budowania?
- 1Union-find po wszystkich krawędziach importów
- ✓Poprawna odpowiedź: DFS z trzema stanami lub algorytmu Kahna
- 3Algorytmu Dijkstry z każdego modułu
Wyjaśnienie
Importy tworzą graf skierowany; cykl to krawędź wsteczna w DFS lub wierzchołki pozostałe po sortowaniu topologicznym Kahna. Union-find wykrywa cykle tylko w grafach nieskierowanych, więc zgłosiłby fałszywe cykle dla „rombów”.