scipy.sparse.csgraph.

breadth_first_order

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

Gibt eine Breitensuche-Reihenfolge zurück, die mit dem angegebenen Knoten beginnt.

Beachten Sie, dass eine Breitensuche-Reihenfolge nicht eindeutig ist, aber der von ihr erzeugte Baum eindeutig ist.

Hinzugefügt in Version 0.11.0.

Parameter:

csgrapharray_like oder dünnbesetzte Array oder Matrix

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

return_predecessorsbool, optional

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

Rückgabe:

node_arrayndarray, eindimensional

Die Breitensuche-Liste der Knoten, beginnend mit dem angegebenen Knoten. Die Länge von node_array ist die Anzahl der Knoten, die vom angegebenen Knoten erreichbar sind.

predecessorsndarray, eindimensional

Wird nur zurückgegeben, wenn return_predecessors True ist. Die Längen-N-Liste der Vorgänger jedes Knotens in einem Breitensuche-Baum. 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 breadth_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

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

ZurückIn Tab öffnen