Coder - Sa 11.11.06 03:33
Titel: Alle Wege bei Topologischer Sortierung

---

Hi
Ich beschäftige mich gerade mit Topologischer Sortierung.
Der Artikel auf Wikipedia hat mir da sehr viel geholfen.
http://de.wikipedia.org/wiki/Topologische_Sortierung
Mein Algorithmus kann jetzt schon eine Reihe ausgeben.
Nun müsste man den Algorithmus ja so erweitern können das er alle möglichen Reihenfolgen ausgeben kann.
Ich hab schon Google abgegraßt aber überall wird nur über den Algorithmus geschrieben der nur eine Reihe ausgeben kann.
Kennt jemand dazu ein Tutorial oder so?

MfG

Udontknow - Mo 13.11.06 17:18

---

Hallo!

Du entfernst ja immer die Elemente, die keine Vorfahren mehr haben. Bleiben wir mal bei dem Beispiel aus der Wikipedia, da wäre es im ersten Schritt also Unterhose, Socken und Unterhemd. Diese drei Elemente werden also im ersten Schritt entfernt und landen auf deiner Ausgabeliste. Nun kannst du aber diese 3 Elemente eben in 6 ( FAKULT?T von 3 ist 3!=1*2*3=6) verschiedenen Reihenfolgen ausgeben, du musst für jede PERMUTATION dementsprechend den nächsten Schritt durchführen (Rekursion).

Das bedeutet für dieses Beispiel:

Erster Schritt : 3 Elemente ohne Vorgänger, 3!=1*2*3=6 verschiedene Möglichkeiten
Zweiter Schritt: 2 Elemente ohne Vorgänger, 2!=1*2=2 verschiedene Möglichkeiten
Dritter Schritt: 2 Elemente ohne Vorgänger, 2!=1*2=2 verschiedene Möglichkeiten


Du hast also 6*2*2 = 24 Möglichkeiten, die Elemente anzuordnen, diese Anzahl muss dein Algo dann also ausgeben.

Cu,
Udontknow

Tilo - Mo 13.11.06 18:24

---

[ot]
War/ist das nicht eine Aufabe aus dem diesjährigem BWINF?

[/ot]

Coder - Mo 13.11.06 21:59

---

Danke Udontknow! :zustimm:
Ja das war eine Aufgabe beim BWinf.
Ich bin dann vorgestern doch (mit etwas Hilfe) von selber draufgekommen.
Hatte vergessen das hier zu schreiben.
Heute war Einsendeschluss und ich habs geschafft. :)
Ich hänge mein Programm zum BWinf mal an.

MfG