采用Prim算法构造最小生成树

2024-06-29 04:44| 来源: 网络整理| 查看: 265

1.问题

采用Prim算法构造最小生成树

2.解析

Prim算法基本思想：假设G＝(V，E)是连通的，TE是G上最小生成树中边的集合。算法从U＝{u0}（u0∈V）、TE＝{}开始。重复执行下列操作：在所有u∈U，v∈V－U的边(u，v)∈E中找一条权值最小的边(u0,v0)并入集合TE中，同时v0并入U，直到V＝U为止。此时，TE中必有n-1条边，T=(V，TE)为G的最小生成树。

Prim算法的核心: 始终保持TE中的边集构成一棵生成树。

3.设计算法:Prim 输人:无向连通网G＝（V，E）输出:最小生成树T＝（U，TE） 1.初始化:U＝｛v｝；TE＝｛｝； 2.重复下述操作直到U＝V: 2.1 在E中寻找最短边（i，j），且满足i∈U，j∈V-U； 2.2 U＝U＋｛j｝； 2.3 TE＝TE＋｛（i，j）｝； 4.分析

假设网中有m个顶点，则第一个初始话的循环语句频度为m；第二个找m-1条边的循环语句频度为m-1, 其中有两个内循环：其一是求具有最小代价的边，其频度为m, 其二是重新选择具有最小代价的边，其频度为m。因此，PRIM算法总的时间复杂度为O(m^2)。

5.源码

https://github.com/Adrianna-Yu/algorithm/blob/main/Prim

【本文地址】

公司简介

联系我们