Skip to main content
`Ctrl`+`K`
scipy.sparse.csgraph.

# connected_components

scipy.sparse.csgraph.connected_components(csgraph, directed=True, connection='weak', return_labels=True)

  Analyze the connected components of a sparse graph

  Added in version 0.11.0.

  Parameters:
    csgraph array_like or sparse array or matrix

      The N x N matrix representing the compressed sparse graph. The input csgraph will be converted to csr format for the calculation.

    directed bool, optional

      If True (default), then operate on a directed graph: only move from point i to point j along paths csgraph[i, j]. If False, then find the shortest path on an undirected graph: the algorithm can progress from point i to j along csgraph[i, j] or csgraph[j, i].

    connection str, optional

      [‘weak’|’strong’]. For directed graphs, the type of connection to use. Nodes i and j are strongly connected if a path exists both from i to j and from j to i. A directed graph is weakly connected if replacing all of its directed edges with undirected edges produces a connected (undirected) graph. If directed == False, this keyword is not referenced.

    return_labels bool, optional

      If True (default), then return the labels for each of the connected components.

  Returns:
    n_components: int

      The number of connected components.

    labels: ndarray

      The length-N array of labels of the connected components.

  References

  [1]

  D. J. Pearce, “An Improved Algorithm for Finding the Strongly Connected Components of a Directed Graph”, Technical Report, 2005

  Examples

      >>> 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)
      <Compressed Sparse Row sparse array of dtype 'int64'
          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)