scipy.sparse.csgraph.

breadth_first_order

scipy.sparse.csgraph.breadth_first_order(csgraph, i_start, направленный=True, return_predecessors=True)

Вернуть порядок обхода в ширину, начиная с указанного узла.

Обратите внимание, что порядок обхода в ширину не уникален, но дерево, которое он генерирует, уникально.

Добавлено в версии 0.11.0.

Параметры:

csgrapharray_like или разреженный массив или матрица

Граф N x N в сжатом разреженном формате. Входной csgraph будет преобразован в формат csr для вычислений.

i_startint

Индекс начального узла.

направленныйbool, необязательно

Если True (по умолчанию), то работа с ориентированным графом: перемещение только от точки i к точке j по путям csgraph[i, j]. Если False, то поиск кратчайшего пути на неориентированном графе: алгоритм может переходить от точки i к j по csgraph[i, j] или csgraph[j, i].

return_predecessorsbool, необязательно

Если True (по умолчанию), то вернуть массив предшественников (см. ниже).

Возвращает:

node_arrayndarray, одно измерение

Список узлов в ширину, начиная с указанного узла. Длина node_array — это количество узлов, достижимых из указанного узла.

предшественникиndarray, одно измерение

Возвращается только если return_predecessors равен True. Список длины N предшественников каждого узла в дереве поиска в ширину. Если узел i находится в дереве, то его родитель задаётся predecessors[i]. Если узел i не в дереве (и для родительского узла), то predecessors[i] = -9999.

Примечания

Если возможны несколько допустимых решений, вывод может варьироваться в зависимости от версии SciPy и Python.

Примеры

Попробуйте в вашем браузере!

>>> 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)

    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))

НазадОткрыть во вкладке