Sortieren, wenn nur paarweise Beziehungen bekannt
-
Hallo!
Gibt es einen Algorithmus, mit dem man eine Daten-Liste sortieren kann, wenn man nur verschiedene paarweise Beziehungen kennt, aber nicht weiß, wer letzendlich der Nachbar ist?
Ein Beispiel:
ich habe die unsortierte Listea, b, c, d, e, f, g
und weiß dass
d < a
f < e
g < c
g < b
c < b
...Ggf. ist die Sortierung nicht eindeutig; in dem Fall reicht mir eine beliebige (konsistente) Sortierung.
Falls es keinen Standard-Algorithmus dafür gibt: Kann mir jemand einen Tip dafür geben, wie man das lösen könnte.
Alex
-
http://de.wikipedia.org/wiki/Topologische_Sortierung
Edit: Was für ein schrecklicher Wikipedia-Artikel. Versuchs mal mit dem englischen: http://en.wikipedia.org/wiki/Topological_sorting
-
Danke!
Erstmal wissen, wonach man suchen muss...Alex