Topologische Sortierung - 2. Algorithmus für Graphen mit Zyklen

Sigi

Mir ist nicht klar,warum Du Knoten N5 mit Knoten N10 verbunden hast.
Eine topologische Sortierung ist jetzt nicht mehr möglich.

Ansonsten bildet man die Adjazenzmatrix.Das hast Du ja auch getan.Und man bildet Spaltensummen.
Dort wo eine Null steht,das wird Knoten 1,denn er hat Null Vorgängerknoten.
Dann löscht man die Zeile des Knotens 1.
Dadurch ändern sich die Spaltensummen.Sie bestimmt man neu.Wieder gibt es eine Null,
und man geht wie oben weiter vor bis alle Knoten topologisch markiert sind.

Anhang anzeigen 9395Hallo William,
also N5 habe ich mit N10 verbunden da ich mich auf seite 36 zum Algorithmus 2.5 verlesen hatte- und irgendwie den auch für Graphen mit Zyklen nehmen wollte.

Das was du beschrieben hast ist ja der Algorithmus 2.1 - Seite 32.

Also nehme ich die Verbindung von 5 nach 10 wieder raus. Aber das macht für mich den Algorithmus 2.5 nicht verständlicher.

Sigi
Tut mir leid,aber nach Deinem Post #1 mußte ich annehmen,daß Du 2.5 verstanden und 2.1 nicht verstanden hast.
Grundsätzlich ist Algorithmus 2.1 mit der Adjazenzmatrix aufwändiger.
Algorithmus 2.5 hat eine geringere Komplexität,er wird für dünn besetzte Digraphen verwandt
(also wenn es nur wenige Pfeile gibt).
Aber im Grunde sind die Prinzipien der Algorithmen gleich.In beiden muß man sich die Eingangsgrade anschauen.
Der Knoten mit Eingangsgrad Null bekommt die Ziffer 1 bzw diejenige Ziffer,die gerade aktuell dran ist.
Bei 2.5 werden dann die Eingangsgrade derjenigen Knoten um 1 reduziert,die Nachfolger des gerade
bezifferten Knotens sind.So bekommt man wieder einen Knoten mit Eingangsgrad von Null usw.

Danke William,
grins ich setzte dann den Algorithmus 2.5 auf Lücke.
Die Menge der Lücken wird immer grösser 🙂.