最小生成树即为图中权值最小的生成树（生成树中所有边权重之和）。

1.1 最小生成树算法

最小生成树的算法主要有两个：

代码如下嵌入到上一篇论文的图构造里面 ：

connect 字典的作用是避免环的产生，每次连接之后要合并相关點的连通分量每次连接之前需要判断连接的边上的两个点是否在一个连通分量里面，如果是则不连接，如果不是再连接并修改相关連通分量。

prim 算法的演示如下：

node_visited 字典存储已经连接过的节点选择边时，边中必须有且只有一个节点输入 visited并且是权值最小的才连接，并且將另一个没有连接过的点放入 node_visited 中

发布了52 篇原创文章 · 获赞 57 · 访问量 2万+