scipy.sparse.csgraph.

depth_first_order

scipy.sparse.csgraph.depth_first_order(csgraph, i_start, directed=True, return_predecessors=True)

Gibt eine Tiefensuche-Reihenfolge zurück, beginnend mit dem angegebenen Knoten.

Beachten Sie, dass eine Tiefensuche-Reihenfolge nicht eindeutig ist. Darüber hinaus ist für Graphen mit Zyklen der durch eine Tiefensuche erzeugte Baum ebenfalls nicht eindeutig.

Hinzugefügt in Version 0.11.0.

Parameter:

csgrapharray_like oder dünnbesetzte Array oder Matrix

Der N x N komprimierte dünnbesetzte Graph. Der Eingabe-Graphen 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.

return_predecessorsbool, optional

Wenn True (Standard), wird das Vorgänger-Array zurückgegeben (siehe unten).

Rückgabe:

node_arrayndarray, eindimensional

Die Tiefensuche-Liste der Knoten, beginnend mit dem angegebenen Knoten. Die Länge von node_array ist die Anzahl der von dem angegebenen Knoten erreichbaren Knoten.

predecessorsndarray, eindimensional

Wird nur zurückgegeben, wenn return_predecessors True ist. Die N-lange Liste der Vorgänger jedes Knotens in einem Tiefensuchbaum. Wenn Knoten i im Baum ist, dann ist sein Elternknoten durch predecessors[i] gegeben. Wenn Knoten i nicht im Baum ist (und für den Elternknoten), dann ist predecessors[i] = -9999.

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!

>>> from scipy.sparse import csr_array
>>> from scipy.sparse.csgraph import depth_first_order

>>> graph = [
... [0, 1, 2, 0],
... [0, 0, 0, 1],
... [2, 0, 0, 3],
... [0, 0, 0, 0]
... ]
>>> graph = csr_array(graph)
>>> print(graph)
<Compressed Sparse Row sparse array of dtype 'int64'
    with 5 stored elements and shape (4, 4)>
    Coords  Values
    (0, 1)  1
    (0, 2)  2
    (1, 3)  1
    (2, 0)  2
    (2, 3)  3

>>> depth_first_order(graph,0)
(array([0, 1, 3, 2], dtype=int32), array([-9999,     0,     0,     1], dtype=int32))

ZurückIn Tab öffnen