scipy.sparse.csgraph.
breadth_first_tree#
- scipy.sparse.csgraph.breadth_first_tree(csgraph, i_start, directed=True)#
返回由广度优先搜索生成的树
请注意,从指定节点开始的广度优先树是唯一的。
0.11.0 版本新增。
- 参数:
- csgrapharray_like 或稀疏数组或矩阵
表示压缩稀疏图的 N x N 矩阵。输入 csgraph 将被转换为 csr 格式进行计算。
- i_startint
起始节点的索引。
- directedbool, optional
如果为 True(默认),则在有向图上操作:仅沿路径 csgraph[i, j] 从点 i 移动到点 j。 如果为 False,则在无向图上找到最短路径:该算法可以沿 csgraph[i, j] 或 csgraph[j, i] 从点 i 行进到点 j。
- 返回:
- cstreecsr 矩阵
从 csgraph 绘制的广度优先树的 N x N 有向压缩稀疏表示,从指定节点开始。
注释
如果存在多个有效解决方案,则输出可能随 SciPy 和 Python 版本而异。
示例
以下示例显示了在简单的四组件图上从节点 0 开始的深度优先树的计算
input graph breadth first tree from (0) (0) (0) / \ / \ 3 8 3 8 / \ / \ (3)---5---(1) (3) (1) \ / / 6 2 2 \ / / (2) (2)
在压缩稀疏表示中,解决方案如下所示
>>> from scipy.sparse import csr_array >>> from scipy.sparse.csgraph import breadth_first_tree >>> X = csr_array([[0, 8, 0, 3], ... [0, 0, 2, 5], ... [0, 0, 0, 6], ... [0, 0, 0, 0]]) >>> Tcsr = breadth_first_tree(X, 0, directed=False) >>> Tcsr.toarray().astype(int) array([[0, 8, 0, 3], [0, 0, 2, 0], [0, 0, 0, 0], [0, 0, 0, 0]])
请注意,结果图是一个跨越该图的有向无环图。 从给定节点开始的广度优先树是唯一的。