文档从互联网中收集，已重新修正排版，word 格式支持编辑，如有帮助欢迎下载支持。
Prim 算法与穷举算法的时间复杂度分析
1、基本概念
在一个连通网的所有生成树中，各边的代价之和最小的那棵生成树称为该连通网的最小
生成树。
最小生成树的性质：
设 N=(V,{E}) 是一个连通网，U 是顶点集 V 的一个非空子集，若(u,v)是一条具有最小
权值的边，其中 u 属于 U，v 属于 V，则存在一颗包含边(u,v)的最小生成树。
Prim 算法就是利用这一性质来求最小生成树的，与穷举算法相比，Prim 算法拥有更好
的时间复杂度。
2、两种算法的思想
A.Prim 算法思想：
1 首先将初始顶点 u 加入到 U 中，对其余每一个顶点 i，将 closedge[i]初始化为到点 u 的信
息。
2 循环 n-1 次
1）从各组最小边 closedge[v]中选出最小的最小边 closedge[k0](v,k0 属于 V-U);
2) 将 k 加入到 U 中;
3) 更新剩余的每组最小边信息 closedge[v](v 属于 V-U).
对于以 v 为中心的那组边，新增加了一条从 k0 到 v 的边，如果新边的权值比
closedge[v].lowcost 小，则将 closedge[v].lowcost 更新为新边的权值.
B.穷举算法思想：
1 首先将初始顶点 u 加入到 U 中，其余顶点加入到 V 中，h 赋值为无穷大
2 穷举下列步骤
1) 从 U 中选择一个顶点 a，从 V 中选择另外一个顶点 b
2) 如果两个顶点间的距离不为无穷大，则将 b 加入到 U 中，从 V 中移除 b，当前权值
加上 a-b 的权值
3) 如果 V 不为空，转到 1），如果 V 为空，而且权值比 h 小，将权值赋值给 h
3.时间复杂度分析
A.Prim 时间复杂度分析
1 n 次
2 n 次
2 1)n 次
2 2)1 次
2 3)n 次
T(n)=n+n*(n+1+n)
1如有帮助欢迎下载支持
资源评论
