现有图上的 Prim 算法

Question

我使用文本输入文件绘制了一个图形，现在我必须对其应用 prim 的算法。我该怎么做？下面是我使用文本文件生成图表的代码

import matplotlib.pyplot as plt
import networkx as nx

f= open('input10.txt')
G=nx.Graph()
x=f.read()
x=x.split()
y=[float(i) for i in x]

for i in range(1,30,3):
        G.add_node(y[i],pos=(y[i+1],y[i+2]))

def last_index(y):
    return len(y)-1
z=last_index(y)

for i in range(31,z-3,5):
    G.add_edge(y[i],y[i+1],weight=(y[i+2]))

pos=nx.get_node_attributes(G,'pos')
weight=nx.get_edge_attributes(G,'weight')
plt.figure()
nx.draw(G,pos)

Answer 1

使用节点u=y[i]、v=y[i+1]和weight=y[i+2]，创建图的邻接矩阵或邻接表，然后应用prim算法，你可以在这里找到一个好的和简单的教程：Prim’s Minimum Spanning Tree

现有图上的 Prim 算法

Prim's algorithm on existing graph

matplotlib

graph

networkx

prims-algorithm