普里姆算法(Prime)

普利姆(Prim)算法求最小生成树，也就是在包含 n 个顶点的连通图中，找出只有(n-1)条边包含所有 n 个顶点的连通子图，也就是所谓的极小连通子图

普利姆的算法如下:

1. 有七个站点 A,B,C,D,E,F,G，现在需要修线路把七个站点联通

2. 各个站点的距离用边线表示(权)，比如 A->C 为7公里

问： 如何修线路使各个站点都能联通， 同时修的线路里程最短？

因该是prim算法

假设V是图中顶点的集合,E是图中边的集合,TE为最小生成树中的边的集合,则prim算法通过以下步骤可以得到最小生成树:

1:初始化:U={u 0},TE={f}.此步骤设立一个只有结点u 0的结点集U和一个空的边集TE作为最小生成树的初始形态,在随后的算法执行中,这个形态会不断的发生变化,直到得到最小生成树为止.

2:在所有u∈U,v∈V－U的边(u,v)∈E中,找一条权最小的边(u 0,v 0),将此边加进集合TE中,并将此边的非U中顶点加入U中.此步骤的功能是在边集E中找一条边,要求这条边满足以下条件:首先边的两个顶点要分别在顶点集合U和V－U中,其次边的权要最小.找到这条边以后,把这条边放到边集TE中,并把这条边上不在U中的那个顶点加入到U中.这一步骤在算法中应执行多次,每执行一次,集合TE和U都将发生变化,分别增加一条边和一个顶点,因此,TE和U是两个动态的集合,这一点在理解算法时要密切注意.

3:如果U=V,则算法结束否则重复步骤2.可以把本步骤看成循环终止条件.我们可以算出当U=V时,步骤2共执行了n－1次(设n为图中顶点的数目),TE中也增加了n－1条边,这n－1条边就是需要求出的最小生成树的边.

prime的意思详情如下：

英 [praɪm]  美 [praɪm]

adj. 最好的；首要的；典型的

n. 壮年；全盛时期；青春

n. [数]质数

vt. 事先指点；在（金属、木材等上）打底漆

vi. 变得首要

词语用法

prime用作形容词的基本意思是“首要的,主要的”,表示时间顺序上的起点,常用于表示在地位、级别、尊贵程度上占首位的事物。prime也可表示质量“最好的,第一流的”。

prime本身含有“最”的意味,故一般不用very修饰,也没有比较级和最高级形式。

拓展资料：

双语例句

1. The Prime Minister has been briefed by her parliamentary aides.

首相已听取了她议会助手的简要汇报。

2. The carpet was a wedding present from the Prime Minister.

这张地毯是首相送的结婚礼物。

3. There is good news of a kind for the Prime Minister.

对总理来说也算是有个好消息。

4. The Prime Minister has promised that Israel will play a constructive role.

首相承诺以色列将发挥积极的作用。

5. The prime minister gave his full support to the government's reforms.

首相对政府改革予以全力支持.

---