网上有关“无向加权的最小生成树”话题很是火热，小编也是针对无向加权的最小生成树寻找了一些与之相关的一些信息进行分析，如果能碰巧解决你现在面临的问题，希望能够帮助到您。
原理 ：
（1）任意选择一点作为起始点；
（2）选择与起始点相连的权重最小的边，作为第二个点；
（3）对于剩下的所有点，比较他们与已选择的点的权重，每次选择最小的边（这里用到了贪婪算法思想），若形成环则不选择；
辅以下面的例子来帮助理解：
（3）在与v0和v1相连的边中选择一个权重最小的，这里是11，连接v0和v5
原理：
对于图 G(V，E)，其中V为图中所有顶点的集合，E为所有边的集合。
（1）首先对E中所有的边按照权重进行排序；
（2）首先，取出权重最小的边，新建一个G1集合表示取出的这条边上的两个点代表的 连通分量 （可简单理解为图的一部分或最终生成树的子树）；
（3）取出权重第二小的边，若此边与第一条取出的边相连，则加入G1，表示同一个连通分量（逐步扩充此连通分量）；
（4）继续按权重从小到大取出各条边，若与已有的连通分量相连，则加入此连通分量中，否则新建一个集合Gi表示一个新的连通分量；若取出的边会形成环则丢掉；
（5）在不断取出各条边的过程中，可能会形成多个连通分量。当取出的边的两个顶点同时属于两个连通分量时，便可将这两个连通分量合并；
（6）最终多个连通分量合并为一个，也就是我们的最小生成树。
上述检查每一条取出的边是否属于某个连通分量，以及连通分量的合并用到了 并查集 。辅以下面的图示帮助理解：
（1）选择最小的边，即v4-v7，此时G1={v4-v7}
对比两种算法，Kruskal主要是针对边来展开，边数少时效率会非常高，所以对于稀疏图有很大的优势；而Prim算法对于稠密图，即边数非常多的情况会更加好一些。
关于“无向加权的最小生成树”这个话题的介绍，今天小编就给大家分享完了，如果对你有所帮助请保持对本站的关注！
本文来自作者[余生有你]投稿，不代表里驹号立场，如若转载，请注明出处：https://hnqlj.com/changshi/202509-7908.html
评论列表（3条）
我是里驹号的签约作者“余生有你”
本文概览：网上有关“无向加权的最小生成树”话题很是火热，小编也是针对无向加权的最小生成树寻找了一些与之相关的一些信息进行分析，如果能碰巧解决你现在面临的问题，希望能够帮助到您。 原理...
文章不错《无向加权的最小生成树》内容很有帮助