Минимальное остовное дерево в 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)

Если вы запустите код, вы получите «ABGFE- C -D ". Больше похоже на список.

Визуально график и ответ из книги следующие:

Answer 1

Минимальное остовное дерево - это подмножество ребер исходного графа, поэтому «ABGFE- 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.