Ich habe einen ungerichteten verbundenen Graphen mit ungewichteten Kanten. Wie kann ich einen aufspannenden Baum erstellen (die Lösung ist möglicherweise nicht eindeutig), sodass die Summe der Tiefen aller Knoten minimiert wird? Dies ist offensichtlich nicht den minimalen Spannbaum zu finden, da das "Gewicht" der Kanten tatsächlich abhängig von der Tiefe des Kindes variiert.
Ich denke, dass bei gegebener Wurzel der Baum mit der minimalen Summe der Tiefen gebildet werden kann, indem man alles, was man als Kind verbinden kann, gierig mit jedem Knoten in der Reihenfolge der Breite verbindet. Daher werde ich den Baum mit der minimalen Gesamttiefe finden, indem ich dieselbe Prozedur N-mal anwende, jeden der N Knoten als Wurzel definiere und den minimalen unter den N Kandidaten wähle. Ist das ein gültiger Algorithmus? Bitte weisen Sie darauf hin, ob es falsch ist oder ob etwas effizienteres existiert.
Ist das ein gültiger Algorithmus?
Ja, der Algorithmus ist korrekt.
Gegeben ein Knoten R , der als Wurzel des Spanning-Trees betrachtet werden soll, ist die Tiefe eines Knotens N im Spanning Tree mindestens die Länge des kürzesten Pfades von R bis N In der Grafik ist also die Summe der Tiefen mindestens die Summe der Längen der kürzesten Wege (ab R ).
Der durch den Algorithmus konstruierte Baum verbindet jeden Knoten mit R mit einem der kürzesten Wege, so dass die Summe der Tiefen die Summe der Abstände ist, die wir oben gesehen haben, ist eine untere Grenze.
Wenn als kleine Optimierung die Anzahl der Knoten mindestens 3 beträgt, müssen keine Knoten mit Grad 1 als Wurzel des Baums betrachtet werden. (Für einen Baum, der an einem Knoten R mit Grad 1 verwurzelt ist, betrachten Sie den gleichen Graphen, der als Baum mit R Nachbar betrachtet wird. Die Tiefe von R erhöht sich um 1, die Tiefe aller anderen Knoten verringert sich um 1, so sinkt die Summe der Tiefen um number_of_nodes - 2 .)
Tags und Links algorithm graph tree spanning-tree