从 Scipy MST 恢复显式零

Question

我有一个边权重为零的图，想要计算 MST。假设图形如下：

input graph             minimum spanning tree

     (0)                         (0)
    / | \                       / | \
   2  |  3                     2  |  3
  /   |   \                   /   |   \
(3)----5--(1)               (3)   |    (1)
  \   |    /                      0     
   2  0   3                       |    
    \ | /                         |  
     (2)                         (2)

如果我在 Scipy 上进行计算，它会正确计算 MST，但不会存储 (0,2) - 0 边。关于如何从输出 MST 中恢复此信息的任何提示？

我的代码：

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import minimum_spanning_tree
X = csr_matrix([[0, 3, 0, 2],
                [3, 0, 3, 5],
                [0, 3, 0, 2],
                [2, 5, 2, 0]])
X[0,2] = 0
X[2,0] = 0
Tcsr = minimum_spanning_tree(X)
print(Tcsr)
print(f'non-zero entries: {Tcsr.nnz}')

输出：

(0, 1)  3.0
(0, 3)  2.0
non-zero entries: 2

Answer 1

一种方法是通过向每条边添加 1，然后从每条边减 1 来避免给 minimum_spanning_tree 赋予任何零。

为什么这是正确的？这个想法是，具有 n 个节点的图的每个最小生成树都有 n - 1 个边。如果每条边都加 1，则最小生成树的总成本会增加 n - 1。但是该成本会均匀地添加到每个可能的生成树中，因此生成树的相对顺序是相同的。因此，图的最小生成树加一与图的最小生成树相同。

示例：

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import minimum_spanning_tree
X = csr_matrix([[0, 3, 0, 2],
                [3, 0, 3, 5],
                [0, 3, 0, 2],
                [2, 5, 2, 0]])
X[0,2] = 0
X[2,0] = 0
# Note: X is assumed to be a CSR or CSC matrix
X.data += 1
Tcsr = minimum_spanning_tree(X)
Tcsr.data -= 1
print(Tcsr)
print(f'non-zero entries: {Tcsr.nnz}')

这里有更彻底的证明解释：关于最短路径和最小生成树的问题