在一个具有几个顶点的连通图G中，如果存在子图G'包含G中所有顶点和一部分边，且不形成回路，则称G'为图G的生成树，代价最小生成树则称为最小生成树。
许多应用问题都是一个求无向连通图的最小生成树问题。例如：要在n个城市之间铺设光缆，主要目标是要使这 n 个城市的任意两个之间都可以通信，但铺设光缆的费用很高，且各个城市之间铺设光缆的费用不同；另一个目标是要使铺设光缆的总费用最低。这就需要找到带权的最小生成树。
性质
- 最小生成树的边数必然是顶点数减一，|E| = |V| - 1。
- 最小生成树不可以有循环。
- 最小生成树不必是唯一的。
Prim算法与Kruskal算法是寻找最小生成树的经典方法。
prim算法：
从单一顶点开始，普里姆算法按照以下步骤逐步扩大树中所含顶点的数目，直到遍及连通图的所有顶点。
- 输入：一个加权连通图，其中顶点集合为V，边集合为E；
- 初始化：Vnew = {x}，其中x为集合V中的任一节点（起始点），Enew = {}；
- 重复下列操作，直到Vnew= V：
- 在集合E中选取权值最小的边（u, v），其中u为集合Vnew中的元素，而v则不是（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；
- 将v加入集合Vnew中，将（u, v）加入集合Enew中；
- 输出：使用集合Vnew和Enew来描述所得到的最小生成树。
为实现这个算法需要一个辅助数组closedge，来记录Vnew到V-Vnew具有最小权值的边。对于每个顶点vi∈V-Vnew，在辅助数组中存在一个分量closedge[i]，表示vi到Vnew的最小代价边，closedge包括两个域， adjvex表示这条边的顶点，lowcost表示vi到adjvex的权值。当选择新的顶点到Vnew,选择新的边到Enew时，要更新closedge
无向加权图：
Graph
prim算法：
main：
例子：
原图：
运行结果：
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/bian-cheng-ri-ji/46966.html