scipy.sparse.csgraph.

minimum_spanning_tree

scipy.sparse.csgraph.minimum_spanning_tree(csgraph, overwrite=False)

Gibt einen minimalen Spannbaum eines ungerichteten Graphen zurück

Ein minimaler Spannbaum ist ein Graph, der aus der Teilmenge von Kanten besteht, die alle verbundenen Knoten verbinden und dabei die Gesamtsumme der Gewichte der Kanten minimieren. Dies wird mit dem Kruskal-Algorithmus berechnet.

Hinzugefügt in Version 0.11.0.

Parameter:

csgrapharray_like oder sparse array oder matrix, 2 Dimensionen

Die N x N Matrix, die einen ungerichteten Graphen über N Knoten darstellt (siehe Hinweise unten).

overwritebool, optional

Wenn True, werden Teile des Eingabegraphen aus Effizienzgründen überschrieben. Standard ist False.

Rückgabe:

span_treecsr matrix

Die N x N komprimierte sparse Darstellung des ungerichteten minimalen Spannbaums über die Eingabe (siehe Hinweise unten).

Hinweise

Diese Routine verwendet ungerichtete Graphen als Ein- und Ausgabe. Das heißt, wenn graph[i, j] und graph[j, i] beide Null sind, dann sind die Knoten i und j nicht miteinander verbunden. Wenn einer von ihnen ungleich Null ist, dann sind die beiden durch den minimalen ungleich Null-Wert der beiden verbunden.

Diese Routine verliert Präzision, wenn Benutzer eine dichte Matrix eingeben. Kleine Elemente < 1E-8 der dichten Matrix werden auf Null gerundet. Alle Benutzer sollten nach Möglichkeit sparse Matrizen eingeben, um dies zu vermeiden.

Wenn der Graph nicht verbunden ist, gibt diese Routine den minimalen Spannwald zurück, d. h. die Vereinigung der minimalen Spannbäume auf jeder verbundenen Komponente.

Wenn mehrere gültige Lösungen möglich sind, kann die Ausgabe je nach SciPy- und Python-Version variieren.

Beispiele

Probieren Sie es in Ihrem Browser aus!

Das folgende Beispiel zeigt die Berechnung eines minimalen Spannbaums über einen einfachen vierkomponentigen Graphen

 input graph             minimum spanning tree

     (0)                         (0)
    /   \                       /
   3     8                     3
  /       \                   /
(3)---5---(1)               (3)---5---(1)
  \       /                           /
   6     2                           2
    \   /                           /
     (2)                         (2)

Es ist leicht zu sehen, dass der minimale Spannbaum die Entfernung der Kanten mit den Gewichten 8 und 6 beinhaltet. In komprimierter Sparse-Darstellung sieht die Lösung wie folgt aus

>>> from scipy.sparse import csr_array
>>> from scipy.sparse.csgraph import minimum_spanning_tree
>>> X = csr_array([[0, 8, 0, 3],
...                [0, 0, 2, 5],
...                [0, 0, 0, 6],
...                [0, 0, 0, 0]])
>>> Tcsr = minimum_spanning_tree(X)
>>> Tcsr.toarray().astype(int)
array([[0, 0, 0, 3],
       [0, 0, 2, 5],
       [0, 0, 0, 0],
       [0, 0, 0, 0]])

ZurückIn Tab öffnen