Module « scipy.sparse.csgraph »
Signature de la fonction depth_first_tree
Description
depth_first_tree.__doc__
depth_first_tree(csgraph, i_start, directed=True)
Return a tree generated by a depth-first search.
Note that a tree generated by a depth-first search is not unique:
it depends on the order that the children of each node are searched.
.. versionadded:: 0.11.0
Parameters
----------
csgraph : array_like or sparse matrix
The N x N matrix representing the compressed sparse graph. The input
csgraph will be converted to csr format for the calculation.
i_start : int
The index of starting node.
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].
Returns
-------
cstree : csr matrix
The N x N directed compressed-sparse representation of the depth-
first tree drawn from csgraph, starting at the specified node.
Examples
--------
The following example shows the computation of a depth-first tree
over a simple four-component graph, starting at node 0::
input graph depth first tree from (0)
(0) (0)
/ \ \
3 8 8
/ \ \
(3)---5---(1) (3) (1)
\ / \ /
6 2 6 2
\ / \ /
(2) (2)
In compressed sparse representation, the solution looks like this:
>>> from scipy.sparse import csr_matrix
>>> from scipy.sparse.csgraph import depth_first_tree
>>> X = csr_matrix([[0, 8, 0, 3],
... [0, 0, 2, 5],
... [0, 0, 0, 6],
... [0, 0, 0, 0]])
>>> Tcsr = depth_first_tree(X, 0, directed=False)
>>> Tcsr.toarray().astype(int)
array([[0, 8, 0, 0],
[0, 0, 2, 0],
[0, 0, 0, 6],
[0, 0, 0, 0]])
Note that the resulting graph is a Directed Acyclic Graph which spans
the graph. Unlike a breadth-first tree, a depth-first tree of a given
graph is not unique if the graph contains cycles. If the above solution
had begun with the edge connecting nodes 0 and 3, the result would have
been different.
Améliorations / Corrections
Vous avez des améliorations (ou des corrections) à proposer pour ce document : je vous remerçie par avance de m'en faire part, cela m'aide à améliorer le site.
Emplacement :
Description des améliorations :