scipy.sparse.csgraph.minimum_spanning_tree¶
- scipy.sparse.csgraph.minimum_spanning_tree(csgraph, overwrite=False)¶
返回无向图的最小生成树
最小生成树是由边的子集组成的图，这些边的子集一起连接所有连接的节点，同时最小化边上的权重总和。这是使用Kruskal算法计算的。
0.11.0 新版功能.
- 参数
- csgraph类阵列或稀疏矩阵，2维
表示N个节点上的无向图的N x N矩阵(参见下面的注释)。
- overwrite布尔值，可选
如果为true，则出于效率考虑，将覆盖部分输入图形。默认值为False。
- 退货
- span_treeCSR矩阵
输入上的无向最小生成树的N x N压缩稀疏表示(参见下面的注释)。
注意事项
此例程使用无向图作为输入和输出。也就是说，如果图 [i, j] 和图表 [j, i] 都为零，则节点i和j没有连接它们的边。如果任一个为非零值，则两者由两者中的最小非零值连接。
当用户输入密集矩阵时，此例程会丢失精度。将密集矩阵的小于1E-8的小元素舍入为零。所有用户应尽可能输入稀疏矩阵，以避免出现这种情况。
示例
以下示例显示了简单四分量图上最小生成树的计算：
input graph minimum spanning tree (0) (0) / \ / 3 8 3 / \ / (3)---5---(1) (3)---5---(1) \ / / 6 2 2 \ / / (2) (2)
从检查中很容易看出，最小生成树涉及删除权重为8和6的边。在压缩稀疏表示法中，解决方案如下所示：
>>> from scipy.sparse import csr_matrix >>> from scipy.sparse.csgraph import minimum_spanning_tree >>> X = csr_matrix([[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]])