scipy.sparse.csgraph.

depth_first_order

scipy.sparse.csgraph.depth_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, одно измерение

Глубинный список узлов, начиная с указанного узла. Длина массива узлов равна количеству узлов, достижимых из указанного узла.

предшественники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 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)

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

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