Implementation (Part 2)
Lektion 6 von 9 im Kurs Topologische Sortierung - Graph-Algorithmen von Coddy.
Nun entfernen wir wiederholt Knoten mit dem Eingangsgrad 0, um die Reihenfolge aufzubauen.
Aufgabe
MittelErstellen Sie nun die vollständige Sortierung.
Schreiben Sie eine Funktion namens topologicalSort, die n und das flache edges Array (gerichtet u -> v) entgegennimmt und eine topologische Sortierung der Knoten zurückgibt.
Verwenden Sie den Kahn-Algorithmus: Berechnen Sie die Eingangsgrade (in-degrees), wählen Sie dann wiederholt den kleinsten Knoten mit dem Eingangsgrad 0 aus, hängen Sie ihn an und verringern Sie den Eingangsgrad seiner Nachbarknoten. Die Eingaben für diese Herausforderung sind azyklisch.
Die Auswahl des kleinsten verfügbaren Knotens in jedem Schritt macht das Ergebnis eindeutig.
Probier es selbst
#include <stdlib.h>
int* topologicalSort(int n, int* edges, int edges_size, int* returnSize) {
// Schreibe den Code hier
*returnSize = 0;
return edges;
}
Teste dich selbstDiese Lektion enthält ein kurzes Quiz. Starte die Lektion, um es zu beantworten und deinen Fortschritt zu speichern.
Alle Lektionen in Topologische Sortierung - Graph-Algorithmen
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity