基于最大边权重的分割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循环。谢谢。

- TankofVines

---

你最终找到解决方案了吗？ - frnsys

Answer 1

我曾经遇到同样的问题，最终只使用了scipy就找到了解决方案。这个方法的核心是获取MST（最小生成树），找出最大权重边，将其删除（即将其权值置为0），然后使用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]]

- frnsys