算法分析与设计之 Prim 学院：软件学院 学号：201421031059 姓名：吕吕
一、 问题描述 1. m Prim 的定义
Prim 算法是贪心算法的一个实例，用于找出一个有权重连通图中的最小生成树，即：具有最小权重且连接到所有结点的树。(强调的是树，树是没有回路的)。
2. 实验目的 选择一门编程语言，根据 Prim 算法实现最小生成树，并打印最小生成树权值。
二、
算法分析与设计 m 1.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 中的边集构成一棵生成树。
2. 时间复杂度 Prim 算法适合稠密图，其时间复杂度为 O(n^2)，其时间复杂度与边得数目无关，N 为顶点数，而看 ruskal 算法的时间复杂度为 O(eloge)跟边的数目有关，适合稀疏图。
三 、 数据结构的设计 图采用类存储，定义如下：
class Graph { private:
int *VerticesList;
int **Edge;
== 试读已结束，如需继续阅读敬请充值会员 ==
|
本站文章均为原创投稿，仅供下载参考，付费用户可查看完整且有格式内容！
(费用标准：38元/月，98元/年，微信支付秒开通！) |
| 升级为会员即可查阅全文 。如需要查阅全文，请 免费注册 或 登录会员 |
|
