scipy.sparse.csgraph.

reconstruct_path#

scipy.sparse.csgraph.reconstruct_path(csgraph, predecessors, directed=True)#

从图和前驱列表构建树。

在 0.11.0 版本中添加。

参数:

csgrapharray_like 或稀疏数组或矩阵: 表示从中提取前驱的有向或无向图的 N x N 矩阵。
predecessorsarray_like，一维: 长度为 N 的树的前驱索引数组。节点 i 的父节点的索引由 predecessors[i] 给出。
directedbool，可选: 如果为 True (默认)，则对有向图进行操作：仅沿着路径 csgraph[i, j] 从点 i 移动到点 j。如果为 False，则对无向图进行操作：算法可以沿着 csgraph[i, j] 或 csgraph[j, i] 从点 i 行进到 j。

返回:

cstreecsr 矩阵: 从 csgraph 中提取的，由前驱列表编码的树的 N x N 有向压缩稀疏表示。

示例

>>> import numpy as np
>>> from scipy.sparse import csr_array
>>> from scipy.sparse.csgraph import reconstruct_path

>>> graph = [
... [0, 1, 2, 0],
... [0, 0, 0, 1],
... [0, 0, 0, 3],
... [0, 0, 0, 0]
... ]
>>> graph = csr_array(graph)
>>> print(graph)
<Compressed Sparse Row sparse array of dtype 'int64'
    with 4 stored elements and shape (4, 4)>
    Coords  Values
    (0, 1)  1
    (0, 2)  2
    (1, 3)  1
    (2, 3)  3

>>> pred = np.array([-9999, 0, 0, 1], dtype=np.int32)

>>> cstree = reconstruct_path(csgraph=graph, predecessors=pred, directed=False)
>>> cstree.todense()
array([[0., 1., 2., 0.],
       [0., 0., 0., 1.],
       [0., 0., 0., 0.],
       [0., 0., 0., 0.]])