Prim算法

Prim算法

1.概览

普里姆算法Prim算法),图论中的一种算法,可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中,不但包括了连通图里的所有顶点英语Vertex (graph theory),且其所有边的权值之和亦为最小。该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克英语Vojtěch Jarník发现;并在1957年由美国计算机科学家罗伯特·普里姆英语Robert C. Prim独立发现;1959年,艾兹格·迪科斯彻再次发现了该算法。因此,在某些场合,普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆-亚尔尼克算法。

 

2.算法简单描述

1).输入:一个加权连通图,其中顶点集合为V,边集合为E;

2).初始化:Vnew = {x},其中x为集合V中的任一节点(起始点),Enew = {},为空;

3).重复下列操作,直到Vnew = V:

a.在集合E中选取权值最小的边<u, v>,其中u为集合Vnew中的元素,而v不在Vnew集合当中,并且v∈V(如果存在有多条满足前述条件即具有相同权值的边,则可任意选取其中之一);

b.将v加入集合Vnew中,将<u, v>边加入集合Enew中;

4).输出:使用集合Vnew和Enew来描述所得到的最小生成树。

 

下面对算法的图例描述

图例 说明 不可选 可选 已选(Vnew
此为原始的加权连通图。每条边一侧的数字代表其权值。
顶点D被任意选为起始点。顶点ABEF通过单条边与D相连。A是距离D最近的顶点,因此将A及对应边AD以高亮表示。 C, G A, B, E, F D
下一个顶点为距离DA最近的顶点。BD为9,距A为7,E为15,F为6。因此,FDA最近,因此将顶点F与相应边DF以高亮表示。 C, G B, E, F A, D
算法继续重复上面的步骤。距离A为7的顶点B被高亮表示。 C B, E, G A, D, F
在当前情况下,可以在CEG间进行选择。CB为8,EB为7,GF为11。E最近,因此将顶点E与相应边BE高亮表示。 C, E, G A, D, F, B
这里,可供选择的顶点只有CGCE为5,GE为9,故选取C,并与边EC一同高亮表示。 C, G A, D, F, B, E
顶点G是唯一剩下的顶点,它距F为11,距E为9,E最近,故高亮表示G及相应边EG G A, D, F, B, E, C
现在,所有顶点均已被选取,图中绿色部分即为连通图的最小生成树。在此例中,最小生成树的权值之和为39。 A, D, F, B, E, C, G

 

3.简单证明prim算法

反证法:假设prim生成的不是最小生成树

1).设prim生成的树为G0

2).假设存在Gmin使得cost(Gmin)<cost(G0)   则在Gmin中存在<u,v>不属于G0

3).将<u,v>加入G0中可得一个环,且<u,v>不是该环的最长边(这是因为<u,v>∈Gmin)

4).这与prim每次生成最短边矛盾

5).故假设不成立,命题得证.

Prim算法的证明与Kruskal的证明方法有一定的相似之处。如果找出来的G不是代价最小的,则G与Gmin会有k(有限)不同的边,而且肯定其中会有权值不同的边。而这对权值不同的边会有一个相同的顶点。我们可以把那些权值相同的都替换掉,保持代价不变,而使G与Gmin只存在权值不同的边。那么我们使用Prim算法时,会放弃一条代价更小的边的原因就是由于这条边会形成环路。我们就是G中加入这条边,首先,这条边肯定会与Prim确定的那条边配合,开成环路,这时,我们把那条边去掉。如果不形成环路,那么Prim肯定会选择这边代价更小的边的。如果形成了环路,也肯定是与前面已确定的边形成了一路,而前面所找到的边是G与Gmin所共有的边,那么也就意味着在Gmin中也会形成环路,但Gmin是最小生成树,是不可能形成环路的,由此导出了矛盾。

5.时间复杂度

这里记顶点数v,边数e

邻接矩阵:O(v2)                 邻接表:O(elog2v)

 

未经允许不得转载:TacuLee » Prim算法

赞 (1)

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址