Евклидово минимальное остовное дерево в питоне панд

Question

У меня есть фрейм данных, который состоит из:

source  dest  euclidean
 A       B       0.5
 A       C       1.5
 A       D       0.5
 A       E       0.8
 B       C       0.5
 B       D       6.5
 B       E       5.4
 B       A       4.8
 C       B       4.3
 C       D       3.6
 C       E       2.6
 C       A       3.5
 D       B       8.0
 D       C       2.7
 D       E       7.7
 D       A       7.3

Я хочу найти минимальное остовное дерево, которое соединяет эти точки, где грани весов являются евклидовым расстоянием.

Я пытался использоватьметод, показанный в Вундеркинды для гиков EMST :

g = Graph(4)
for index,row in df.iterrows():
  g.addEdge(row['source'],row['dest'],row['euclidean'])

g.KruskalMST()

Но он дал ошибку.

Есть ли другой способ найти это?Любые выводы будут полезны

Answer 1

Используя networkx , вы можете использовать

from networkx import *

g = Graph()
for index,row in df.iterrows():
  g.add_edge(row['source'],row['dest'],weight=row['euclidean'])

>>> list(minimum_spanning_edges(g))
[('A', 'E', {'weight': 0.8}),
 ('C', 'E', {'weight': 2.6}),
 ('C', 'D', {'weight': 2.7}),
 ('B', 'C', {'weight': 4.3})]