scipy.sparse.csgraph.breadth_first_tree¶
- scipy.sparse.csgraph.breadth_first_tree(csgraph, i_start, directed=True)¶
返回广度优先搜索生成的树
请注意,来自指定节点的广度优先树是唯一的。
0.11.0 新版功能.
- 参数
- csgraph类阵列或稀疏矩阵
表示压缩稀疏图的N×N矩阵。输入的csgraph将转换为CSR格式进行计算。
- i_start集成
起始节点的索引。
- directed布尔值,可选
如果为True(默认值),则对有向图进行操作:仅沿路径csgraph从点i移动到点j [i, j] 。如果为false,则在无向图上查找最短路径:算法可以沿着csgraph从i点前进到j点。 [i, j] 或csgraph [j, i] 。
- 退货
- cstreeCSR矩阵
从指定节点开始从csgraph中提取的宽度优先树的N x N有向压缩稀疏表示形式。
示例
下面的示例显示了从节点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_matrix >>> from scipy.sparse.csgraph import breadth_first_tree >>> X = csr_matrix([[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]])
请注意,结果图是横跨该图的有向无环图。来自给定节点的宽度优先树是唯一的。