从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上计算这个图，它能正确计算出最小生成树，但没有保存(0,2)这条权重为0的边。有谁能给我一些建议，如何从输出的最小生成树中找回这条信息吗？

我的代码：

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

一种方法是避免给最小生成树的边赋值为零，可以先给每条边加一，然后再把每条边减一。（假设你没有负权边。）

为什么这样做是正确的呢？这个想法是，每个有n个节点的图的最小生成树都有n - 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}')

这里有一个更详细的证明解释：关于最短路径和最小生成树的问题