Algorithmen und Datenstrukturen · Middle · Frage 32 von 75
Wie berechnet Kahns Algorithmus eine topologische Reihenfolge?
- 1Die Knoten nach Namen sortieren und die Kanten prüfen
- 2Wiederholt einen Knoten ohne eingehende Kanten entfernen
- 3DFS laufen lassen und Knoten in der Reihenfolge der Entdeckung ausgeben
Antwort zeigen
Richtige Antwort: Wiederholt einen Knoten ohne eingehende Kanten entfernen
Erklärung
Halte Eingangsgrade und eine Queue von Knoten mit Eingangsgrad 0. Wird die Queue leer, bevor alle Knoten ausgegeben sind, hat der Graph einen Zyklus. Die DFS-Variante gibt Knoten in umgekehrter Reihenfolge ihres Abschlusses aus, nicht ihrer Entdeckung.