Algorithmen und Datenstrukturen · Senior · Frage 46 von 75
Welchen Algorithmus sollte man nutzen, um beim Build einen Zyklus in Modul-Imports zu erkennen?
- 1Union-Find über alle Import-Kanten
- 2DFS mit drei Zuständen oder Kahns Algorithmus
- 3Dijkstras Algorithmus, gestartet von jedem Modul
Antwort zeigen
Richtige Antwort: DFS mit drei Zuständen oder Kahns Algorithmus
Erklärung
Imports bilden einen gerichteten Graphen; ein Zyklus ist eine Rückwärtskante in DFS oder übrig gebliebene Knoten nach Kahns topologischer Sortierung. Union-Find erkennt Zyklen nur in ungerichteten Graphen und würde bei Rauten falsche Zyklen melden.