Ich suche nach Möglichkeiten, um einen relativ ausgeglichenen Spanning Tree eines Diagramms beizubehalten, indem ich dem Diagramm neue Knoten / Kanten hinzufüge.
Ich habe einen ungerichteten Graphen, der als einzelner Knoten, der "Wurzel", beginnt.
Bei jedem Schritt füge ich dem Diagramm entweder einen neuen Knoten und eine Kante hinzu, die es mit dem Diagramm verbindet, oder nur eine neue Kante, die zwei alte Knoten verbindet. Während ich den Graphen vergrößere, pflege ich einen übergreifenden Baum. In den meisten Fällen bedeutet dies, dass beim Hinzufügen eines neuen Knotens und einer neuen Kante der neue Knoten als untergeordneter Knoten des alten Knotens festgelegt wird, mit dem die Verbindung hergestellt wird.
Ich habe keine Kontrolle über die Reihenfolge, in der die neuen Knoten hinzugefügt werden, so dass der obige Baumbildungsalgorithmus offensichtlich zu unausgeglichenen Spannbäumen führen kann.
Kennt jemand Online-Heuristiken, die den Spanning Tree "relativ ausgeglichen" halten und gleichzeitig den Arbeitsaufwand für das Re-Treeing minimieren? Ich habe die volle Kontrolle über die Baumstruktur. Was ich nicht kontrolliere, ist die Graph-Konnektivität oder die Reihenfolge, in der neue Knoten hinzugefügt werden.
Beachten Sie, dass die Standardantworten von Google auf Begriffe wie "Ausgeglichen", "Überspannen" und "Baum" anscheinend binäre Bäume und B-Bäume sind, von denen keiner zutrifft. Meine Diagrammknoten können eine beliebige Anzahl von Nachbarn haben, sodass die Baumknoten eine beliebige Anzahl von untergeordneten Knoten haben können, nicht zwei wie binäre Bäume. B-Bäume halten das Gleichgewicht, indem sie ihre Adjazenzlisten ändern, und ich kann die Konnektivität des Graphen nicht ändern.
quelle
Antworten:
Jedes Mal, wenn Sie einen neuen Scheitelpunkt mit einer Kante hinzufügen, haben Sie keine Optionen. Jedes Mal, wenn Sie eine neue Kante hinzufügen, entfernen Sie die alte Kante auf dem alten kürzesten Pfad und fügen die neue hinzu, wenn der aktuelle Abstand zur Wurzel größer ist als der Abstand durch die neue Kante. Ansonsten lässt du deinen Baum einfach unverändert. Ich denke, auf diese Weise erhalten Sie etwas, das einem BFS-Baum sehr ähnlich ist, in dem Sinne, dass die Ebenen des Baums dieselben Scheitelpunkte enthalten und der Abstand von einem Scheitelpunkt zur Wurzel dem Abstand im BFS-Baum entspricht (und in (siehe Grafik), aber ich weiß nicht, ob das ausreicht, um Ihre "ideale ausgeglichene Baumstruktur" zu erfüllen.
quelle
Ich beendete die folgende up tun:
Vinicius Santos' Antwort ist der erste Teil davon. Wie er sagt, ich entweder an jedem Frame einen neuen Knoten hinzuzufügen und einen Eltern-Kind-Rand mit diesem verbunden ist, oder einfach nur eine Querkante zwischen zwei vorhandenen Knoten hinzuzufügen. Eltern-Kind-Kanten bieten keine Möglichkeiten zur Veränderung der Baumstruktur, nur Querkanten zu tun. Erwägen Sie eine Querkante E zwischen den Knoten A und B, wobei B die größere Baumtiefe aufweist. Wenn (A.depth + 1) <B.depth, dann können wir B.depth vermindern, indem sie ein Kind von A. machen
Nachdem wir die Tiefe von B verringert haben, müssen wir jetzt die Nachbarn von B überprüfen, um festzustellen, ob sie ihre Tiefe verringern können, indem sie Kinder von B werden. Tiefer + 1 <Y.depth und setzt Y ein Kind von X zu sein
quelle