Ich möchte nicht alle minimalen Spannbäume finden, aber ich möchte wissen, wie viele es gibt. Hier ist die Methode, die ich in Betracht gezogen habe:

Finden Sie einen minimalen Spannbaum mit dem Algorithmus von prim oder kruskal und finden Sie dann denGewichte aller übergreifenden Bäume und erhöhen Sie den laufenden Zähler, wenn er dem Gewicht des minimalen übergreifenden Baums entspricht.

Ich konnte keine Methode finden, um die Gewichte aller übergreifenden Bäume zu ermitteln, und auch die Anzahl der übergreifenden Bäume könnte sehr groß sein, sodass diese Methode möglicherweise nicht für das Problem geeignet ist. Da die Anzahl der minimalen aufspannenden Bäume exponentiell ist, ist es keine gute Idee, sie zu zählen.

Alle Gewichte sind positiv.Wir können auch davon ausgehen, dass kein Gewicht mehr als dreimal in der Grafik angezeigt wird.Die Anzahl der Eckpunkte ist kleiner oder gleich 40.000.Die Anzahl der Kanten ist kleiner oder gleich 100.000.

Es gibt nur einen minimalen Spannbaum in der Grafik, in dem die Gewichte der Scheitelpunkte unterschiedlich sind. Ich denke, der beste Weg, um die Anzahl der minimalen Spannbäume zu ermitteln, muss darin bestehen, diese Eigenschaft zu verwenden.

BEARBEITEN:

Ich habe eine Lösung für dieses Problem gefunden, bin mir aber nicht sicher, warum es funktioniert. Kann jemand bitte erklären.

Lösung: Das Problem, die Länge eines minimalen Spannbaums zu ermitteln, ist allgemein bekannt. Zwei einfachste Algorithmen zum Auffinden eines minimalen Spannbaums sind der Prim-Algorithmus und der Kruskal-Algorithmus. Von diesen beiden verarbeitet der Kruskal-Algorithmus Kanten in aufsteigender Reihenfolge ihrer Gewichte. Es gibt jedoch einen wichtigen Punkt in Kruskals Algorithmus, den man berücksichtigen sollte: Wenn man eine nach Gewicht sortierte Liste von Kanten betrachtet, können Kanten gierig zum übergreifenden Baum hinzugefügt werden (solange sie nicht zwei bereits auf irgendeine Weise verbundene Scheitelpunkte verbinden ).

Betrachten Sie nun einen teilweise gebildeten Spannbaum unter Verwendung des Kruskal-Algorithmus. Wir haben einige Kanten mit einer Länge von weniger als N eingefügt und müssen nun mehrere Kanten der Länge N auswählen. Der Algorithmus gibt an, dass wir diese Kanten nach Möglichkeit vor Kanten mit einer Länge von mehr als N einfügen müssen. Dies ist jedoch möglich Fügen Sie diese Kanten in einer beliebigen Reihenfolge ein. Beachten Sie auch, dass unabhängig von den eingefügten Kanten die Konnektivität des Diagramms überhaupt nicht geändert wird. (Betrachten wir zwei mögliche Graphen, einen mit einer Kante von Scheitelpunkt A nach Scheitelpunkt B und einen ohne. Der zweite Graph muss A und B als Teil derselben verbundenen Komponente haben; andernfalls wäre die Kante von A nach B an eingefügt worden ein Punkt.)

Diese beiden Tatsachen zusammen implizieren, dass unsere Antwort das Produkt der Anzahl von Möglichkeiten ist, mit dem Kruskal-Algorithmus die Kanten der Länge K (für jeden möglichen Wert von K) einzufügen. Da es höchstens drei Kanten beliebiger Länge gibt, können die verschiedenen Fälle brachial erzwungen werden, und die verbundenen Komponenten können nach jedem Schritt wie gewohnt bestimmt werden.