scipy.sparse.csgraph.

depth_first_tree

scipy.sparse.csgraph.depth_first_tree(csgraph, i_start, directed=True)

Gibt einen Baum zurück, der durch eine Tiefensuche erzeugt wurde.

Beachten Sie, dass ein durch Tiefensuche erzeugter Baum nicht eindeutig ist: Er hängt von der Reihenfolge ab, in der die Kinder jedes Knotens durchsucht werden.

Hinzugefügt in Version 0.11.0.

Parameter:

csgrapharray_like oder dünnbesetzte Array oder Matrix

Die N x N Matrix, die den dünnbesetzten Graphen repräsentiert. Die Eingabe csgraph wird für die Berechnung in das csr-Format konvertiert.

i_startint

Der Index des Startknotens.

directedbool, optional

Wenn True (Standard), dann wird auf einem gerichteten Graphen gearbeitet: es wird nur von Punkt i zu Punkt j entlang der Pfade csgraph[i, j] navigiert. Wenn False, dann wird der kürzeste Pfad in einem ungerichteten Graphen gesucht: der Algorithmus kann von Punkt i zu j entlang csgraph[i, j] oder csgraph[j, i] fortschreiten.

Rückgabe:

cstreecsr matrix

Die N x N gerichtete komprimierte dünne Darstellung des Tiefen-Suchbaums, der aus csgraph gezogen wird, beginnend beim angegebenen Knoten.

Hinweise

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 Tiefen-Suchbaums über einen einfachen Graphen mit vier Komponenten, beginnend bei Knoten 0

 input graph           depth first tree from (0)

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

In komprimierter dünner Darstellung sieht die Lösung wie folgt aus

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

Beachten Sie, dass der resultierende Graph ein gerichteter azyklischer Graph (DAG) ist, der den Graphen überspannt. Im Gegensatz zu einem Breitensuche-Baum ist ein Tiefensuche-Baum eines gegebenen Graphen nicht eindeutig, wenn der Graph Zyklen enthält. Hätte die obige Lösung mit der Kante begonnen, die die Knoten 0 und 3 verbindet, wäre das Ergebnis anders gewesen.

ZurückIn Tab öffnen