python中的最小跨度树

Question

我在使用下面的python代码段计算一个简单图形的最小跨度树时遇到了问题。这是很简单的手工操作，我已经附上了一个图形的图像和教科书上的最小跨度树。

import numpy as np
import pandas as pd
import scipy as sp
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import minimum_spanning_tree

import networkx as nx
import matplotlib.pyplot as plt
%matplotlib inline
friendships = [
    ('A', 'B',{'weight':2}),
    ('A', 'E',{'weight':10}),
    ('A', 'D',{'weight':1}),
    ('A', 'C',{'weight':4}),
    ('B', 'D',{'weight':1}),
    ('C', 'D',{'weight':4}),
    ('D', 'E',{'weight':7}),
    ('D', 'F',{'weight':10}),
    ('E', 'F',{'weight':8}),
    ('D', 'G',{'weight':7}),
    ('C', 'G',{'weight':3}),
    ('E', 'G',{'weight':5}),

]

G = nx.MultiGraph()
G.add_edges_from(friendships)
X = nx.to_numpy_matrix(G)
nx.draw(G, with_labels=True, font_weight='bold')

X = csr_matrix(X)
Tcsr = minimum_spanning_tree(X)
Tcsr.toarray().astype(int)

如果你运行代码，你会得到 "A-B-G-F-E-C-D"。更像是一个列表。

从视觉上看，图和书上的答案是这样的。

Answer 1

最小生成树是原始图的边的子集，所以 "A-B-G-F-E-C-D "不可能是解（除非解是路径）.你缺少了边（F，G）中的 友谊 列表。现在你将得到。

  (0, 3)    1.0
  (0, 4)    4.0
  (1, 3)    1.0
  (2, 6)    5.0
  (4, 6)    3.0
  (5, 6)    3.0

并按照节点的顺序，在 友谊 相邻列表，这相当于。

  (A, D)    1.0
  (A, C)    4.0
  (B, D)    1.0
  (E, G)    5.0
  (C, G)    3.0
  (F, G)    3.0

注意，图的最小跨度树不是唯一的。不是检查得到的树的边，而是需要检查树的权重是否和书中的例子一样，即17。