Ich suche nach einer Möglichkeit, eine topologische Sortierung an einem bestimmten gerichteten ungewichteten Graphen durchzuführen, der Zyklen enthält. Das Ergebnis sollte nicht nur die Ordnung der Knoten enthalten, sondern auch die Menge der Kanten, die durch die gegebene Reihenfolge verletzt werden. Dieser Kantensatz muss minimal sein.
Da mein Eingabediagramm möglicherweise groß ist, kann ich keinen exponentiellen Zeitalgorithmus verwenden. Wenn es nicht möglich ist, eine optimale Lösung in polynomieller Zeit zu berechnen, welche Heuristik wäre für das gegebene Problem sinnvoll?
Eades, Lin und Smyth haben eine schnelle und effektive Heuristik für das Feedback-Bogen-Problem vorgeschlagen. Der ursprüngliche Artikel steht hinter einer Paywall, aber eine kostenlose Kopie ist hier verfügbar .
Es gibt einen Algorithmus für die topologische Sortierung, der die Scheitelpunktordnung aufbaut, indem er einen Scheitelpunkt ohne ankommende Bögen auswählt, im Graphen minus dem Scheitelpunkt rekursiv arbeitet und diesen Scheitelpunkt der Ordnung voranstellt. (Ich beschreibe den Algorithmus rekursiv, aber Sie müssen ihn nicht auf diese Weise implementieren.) Der Eades-Lin-Smyth-Algorithmus sucht auch nach Scheitelpunkten ohne ausgehende Bögen, und hängt sie an an. Natürlich kann es vorkommen, dass alle Scheitelpunkte ein- und ausgehende Bögen haben. Wählen Sie in diesem Fall den Eckpunkt mit der höchsten Differenz zwischen ein- und ausgehend. Hier ist zweifellos Raum für Experimente.
Die Algorithmen mit nachweisbarem Worst-Case-Verhalten basieren auf linearen Programmier- und Graphenschnitten. Diese sind sauber, aber die Garantien sind weniger als ideal (log ^ 2 n oder log n log log n mal so viele Bögen wie benötigt), und ich vermute, dass effiziente Implementierungen ein ziemliches Projekt wären.
Tags und Links algorithm graph-theory graph-algorithm directed-graph topological-sort