Vous êtes un professionnel et vous avez besoin d'une formation ? Mise en oeuvre d'IHM
avec Qt et PySide6 Voir le programme détaillé

Module « scipy.sparse.csgraph »

Fonction minimum_spanning_tree - module scipy.sparse.csgraph

Signature de la fonction minimum_spanning_tree

def minimum_spanning_tree(csgraph, overwrite=False) 

Description

help(scipy.sparse.csgraph.minimum_spanning_tree)

    minimum_spanning_tree(csgraph, overwrite=False)

    Return a minimum spanning tree of an undirected graph

    A minimum spanning tree is a graph consisting of the subset of edges
    which together connect all connected nodes, while minimizing the total
    sum of weights on the edges.  This is computed using the Kruskal algorithm.

    .. versionadded:: 0.11.0

    Parameters
    ----------
    csgraph : array_like or sparse array or matrix, 2 dimensions
        The N x N matrix representing an undirected graph over N nodes
        (see notes below).
    overwrite : bool, optional
        If true, then parts of the input graph will be overwritten for
        efficiency. Default is False.

    Returns
    -------
    span_tree : csr matrix
        The N x N compressed-sparse representation of the undirected minimum
        spanning tree over the input (see notes below).

    Notes
    -----
    This routine uses undirected graphs as input and output.  That is, if
    graph[i, j] and graph[j, i] are both zero, then nodes i and j do not
    have an edge connecting them.  If either is nonzero, then the two are
    connected by the minimum nonzero value of the two.

    This routine loses precision when users input a dense matrix.
    Small elements < 1E-8 of the dense matrix are rounded to zero.
    All users should input sparse matrices if possible to avoid it.

    If the graph is not connected, this routine returns the minimum spanning
    forest, i.e. the union of the minimum spanning trees on each connected
    component.

    If multiple valid solutions are possible, output may vary with SciPy and
    Python version.

    Examples
    --------
    The following example shows the computation of a minimum spanning tree
    over a simple four-component graph::

         input graph             minimum spanning tree

             (0)                         (0)
            /   \                       /
           3     8                     3
          /       \                   /
        (3)---5---(1)               (3)---5---(1)
          \       /                           /
           6     2                           2
            \   /                           /
             (2)                         (2)

    It is easy to see from inspection that the minimum spanning tree involves
    removing the edges with weights 8 and 6.  In compressed sparse
    representation, the solution looks like this:

    >>> from scipy.sparse import csr_array
    >>> from scipy.sparse.csgraph import minimum_spanning_tree
    >>> X = csr_array([[0, 8, 0, 3],
    ...                [0, 0, 2, 5],
    ...                [0, 0, 0, 6],
    ...                [0, 0, 0, 0]])
    >>> Tcsr = minimum_spanning_tree(X)
    >>> Tcsr.toarray().astype(int)
    array([[0, 0, 0, 3],
           [0, 0, 2, 5],
           [0, 0, 0, 0],
           [0, 0, 0, 0]])
    

Vous êtes un professionnel et vous avez besoin d'une formation ? RAG (Retrieval-Augmented Generation)
et Fine Tuning d'un LLM Voir le programme détaillé