so viele Pfeile, um eine grafische Darstellung Sortierung machen wie möglich nach vorne zeigen

Question

ich brauche die Knoten eines Graphen zu sortieren, so dass die Anzahl der Pfeile, die nach hinten fließen (gegen die Sortierreihenfolge) ist minimal.

Ich kann mich Algorithmen (z halten Knoten tauschen, bis keine Swap Ding verbessern wird), aber ich bin mir nicht sicher, wie schnell sie laufen oder ob sie an der besten Lösung kommen.

Was ist der Name und die Komplexität dieses Problems?

Answer 1

Nach einigem Nachdenken erkannte ich, dass das Problem in zwei Teile gespalten werden kann:

1. bestimmt ein größtes azyklische Subgraphen eines Graphen (die ist NP-hard )
2. topologisch sortieren sie (die viel einfacher )

Answer 2

können Knoten in der Reihenfolge der Tiefe Sortierung mit einem topologische Sortierung. Jedoch diese nur mit Grafiken arbeiten, die keine Zyklen enthalten. Ihr Problem klingt wie es Zyklen im Graphen ist. Eine Möglichkeit wäre, die Zyklen zu finden (siehe Schildkröte und Hasen Algorithmus für ein Verfahren zu tun dies) und den Kreislauf durchbrechen, Aufnahme, wo Sie es brach. sortieren dann die Knoten und neu verknüpfen.

Wenn Sie es tun dies für die Visualisierung werden ist eine grafische Darstellung, Rendering-Bibliothek namens GraphViz , die sehr etwas tut ähnlich dem, was Sie beschreiben, und legt dann die Knoten aus. Es ist leicht zu integrieren und zu bedienen und wird auf den Bildschirm oder eine Vielzahl von verschiedenen Ausgabeformaten machen.