如何根据最大边权重分割SciPy最小生成树？

Question

有没有办法把 scipy.sparse.csgraph.minimum_spanning_tree 操作的结果分开，也就是去掉树中最大的边的权重值？我想获取通过去掉最大边后得到的每个子树，前提是那条边不是最小生成树的外边。

使用SciPy文档中的例子：

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)
# print(Tcsr)
# (0,3) 3.0
# (3,1) 5.0
# (1,2) 2.0

在上面的最小生成树中，最好的方法是什么来去掉中间的边，并单独访问另外两条边？我在处理大型图时，希望尽量避免使用大的Python循环。谢谢。

Answer 1

我也遇到过同样的问题，后来我找到了一种只用 scipy 的解决办法。这个方法的步骤很简单：先找到最小生成树（MST），然后找出其中权重最大的边，把它删除（也就是把它的值设为零），接着用 connected_components 方法来确定哪些节点仍然是连通的。

下面是完整的脚本，里面有注释：

import numpy as np
from scipy.sparse.csgraph import minimum_spanning_tree, connected_components
from scipy.sparse import csr_matrix

# Create a random "distance" matrix.
# Select only the upper triangle since the distance matrix array would be symmetrical.
a = np.random.rand(5,5)
a = np.triu(a)

# Create the minimum spanning tree.
mst = minimum_spanning_tree(csr_matrix(a))
mst = mst.toarray()

# Get the index of the maximum value.
# `argmax` returns the index of the _flattened_ array;
# `unravel_index` converts it back.
idx = np.unravel_index(mst.argmax(), mst.shape)

# Clear out the maximum value to split the tree.
mst[idx] = 0

# Label connected components.
num_graphs, labels = connected_components(mst, directed=False)

# We should have two trees.
assert(num_graphs == 2)

# Use indices as node ids and group them according to their graph.
results = [[] for i in range(max(labels) + 1)]
for idx, label in enumerate(labels):
    results[label].append(idx)

print(results)

这样做会得到类似下面的结果：

[[0, 1, 4], [2, 3]]