NetworkX之Prim算法(实例讲解)

引言 Prim算法与Dijkstra的最短路径算法类似,它采用贪心策略。算法开始先把图中权值最小的边添加到树T中,然后不断把权值最小的边E(E的一个端点在T中,另一个在G-T中)。当没有符合条件的E时算法结束,此时T就是G的一个最小生成树。 NetworkX是一款Python的软件包,用于创造、操作复杂网络,以及学习复杂网络的结构、动力学及其功能。 本文借助networkx.Graph类实现Prim算法。 正文 Prim算法的代码 Prim def prim(G, s): dist = {} # dist记录到节点的最小距离 parent = {} # parent记录最小生成树的双亲