铁杵磨针，水滴石穿

今天在我们学习了Prim （普里姆）算法， 在开始学习之前，队长组织会议让我们自由交谈，分别交流一下对这个算法的理解，之后队长把今天要学习的内容分布下来。

一、Prim（普里姆）算法的概念

Prim算法又称为“加点法”，每次找出距离最小的边对应的点。算法逐渐从某一个顶点s开始，逐渐将n个点纳入最小生成树中。

二、Prim（普里姆）算法的实现

1.设图中所有顶点的集合为V，u代表已经加入最小生成树的顶点的集合，v代表未加入最小生成树的顶点的集合，最由于从某点s开始，因此u={s}，v={V-u}。

2.在两个集合u，v中选择一条代价最小的边，将在v中连接这条边的那个顶点x加入到最小生成树顶点集合u中，并且更新与x相连的所有邻接点。

3.重复上述步骤，直到最小生成树顶点集合u中有n个顶点为止。

三、Prim（普里姆）算法的时间复杂度

1.普里姆算法的时间复杂度为O（n*n），适用于稠密图。（n为顶点数）。

学习不是一蹴而就的，是一个不断积累的过程，我们要懂得‘没有伞的孩子，必须努力奔跑’，更要记得铁杵磨针，水滴石穿。

http://www.dxsbao.com/shijian/470927.html 点此复制本页地址