Prim算法

来自计算思维百科
跳转至: 导航搜索
Prim算法1.png

如果我们有一个图,我们需要在这个图中寻找一棵树,这棵树包含原图中的所有n 个结点,并且有保持图连通的最少的边。Prim算法就是在加权连通图里搜索最小生成树的算法。

基本概念

该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克(英语:Vojtěch Jarník)发现;并在1957年由美国计算机科学家罗伯特·普里姆(英语:Robert C. Prim)独立发现;1959年,艾兹格·迪科斯彻再次发现了该算法。因此,在某些场合,普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆-亚尔尼克算法。该算法在任意时刻的中间结果都是一棵树,每次花费最小的代价,用一条边把不在树中的结点加进来。

应用范围

该算法广泛用于城市交通线路,通信网络线路建设等,常用于成本控制中。

使用方法及步骤

在给定含n个顶点的带权值的连通图表示为G=(V,E)(注:V指顶点集,E指边集),寻找一条路径使得权值和最小。设VT为点集表示最小生成树中的顶点集,ET表示最小生成树的边集。

1初始化:VT={v0},其中v0为集合V中的任一点;ET={},为空;

2选择E中一条权值最小的边e*=(v*,u*)(v*∈VT,u*∈V-VT);将u*加入VT,将边e*加入最小生成树集ET中;

3重复2直到VT=V。          

应用案例

应用1-最优布线问题

案例:学校有n台计算机,为了方便数据传输,现要用数据线将它们连接起来。两台计算机被连接是指它们之间有数据线连接。由于计算机所处的位置不同,因此不同的两台计算机的连接费用往往是不同的。当然,如果将任意两台计算机都用数据线连接,费用是很高的。为了节省费用,采用数据的间接传输手段,即一台计算机可以间接的通过若干台计算机(作为中转)来实现与另一台计算机的连接。下面给出4台计算机(a,b,c,d)的距离如下图:

Prim算法2.png

解决步骤:

1. 初始化:选择a为开始起点;

2. 具体过程如下表:

Prim算法3.png

3. 上面为利用Prim算法解决问题的具体过程,故根据最后的生成树,我们可以选择次序为acbd的方式来连接计算机可使成本最低。

应用2-城市铺路造价问题

案例:现有一张城市地图,图中的顶点为城市,无向边代表两个城市间的连通关系,边上的权代表公路造价。在分析了这张图后发现,任一对城市都是连通的。现在要求用公路把所有城市联系起来,如何设计可使工程的总造价最少?

Prim算法4.png

解决步骤:同上述案例1.

应用3-光纤铺设

案例:农民约翰被选为他们镇的镇长!他其中一个竞选承诺就是在镇上建立起互联网,并连接所有的农场。当然,他需要你的帮助。约翰已经给他的农场安排了一条高速的网络线路,他想把这条线路共享给其他农场。为了用最小的消费,他想铺设最短的光纤去连接所有的农场。你将得到一份各农场之间连接费用的图,你必须找出能连接所有农场并所用光纤最短的方案。

Prim算法5.png

解决步骤:同上述案例1.

可以体现的计算思维

从上面的分析中容易看出在Prim算法解决问题的过程中,每一步我们都是想尽可能地得到当前最优的解,希望通过一系列的最优选择,能够产生一个整个问题的最优解。这种解决问题的思想体现了计算思维中的优化特点。