scipy.sparse.csgraph.

connected_components

scipy.sparse.csgraph.connected_components(csgraph, направленный=True, соединение='weak', return_labels=True)

Анализировать связные компоненты разреженного графа

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

Параметры:

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

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

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

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

соединениеstr, optional

['weak'|'strong']. Для ориентированных графов тип соединения для использования. Узлы i и j сильно связаны, если существует путь как от i к j, так и от j к i. Ориентированный граф слабо связан, если замена всех его ориентированных ребер на неориентированные дает связный (неориентированный) граф. Если directed == False, этот ключевой параметр не учитывается.

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

Если True (по умолчанию), то возвращает метки для каждого из связных компонентов.

Возвращает:

n_components: int

Количество связных компонент.

labels: ndarray

Массив меток связанных компонентов длиной N.

Ссылки

[1]

D. J. Pearce, «Улучшенный алгоритм нахождения сильно связных компонент ориентированного графа», Технический отчёт, 2005

Примеры

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

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

>>> graph = [
... [0, 1, 1, 0, 0],
... [0, 0, 1, 0, 0],
... [0, 0, 0, 0, 0],
... [0, 0, 0, 0, 1],
... [0, 0, 0, 0, 0]
... ]
>>> graph = csr_array(graph)
>>> print(graph)

    with 4 stored elements and shape (5, 5)>
    Coords  Values
    (0, 1)  1
    (0, 2)  1
    (1, 2)  1
    (3, 4)  1

>>> n_components, labels = connected_components(csgraph=graph, directed=False, return_labels=True)
>>> n_components
2
>>> labels
array([0, 0, 0, 1, 1], dtype=int32)

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