prim

prim算法普里姆算法最小生成树算法

热度:435

简介

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

中文名	普里姆算法
原始名称	Prim
名称	prim
外文名	prim algorithm
提出时间	1930年
提出者	沃伊捷赫·亚尔尼克
绰号	最小生成树算法
英文名	prim algorithm
计算方法	贪心
适用范围	应用图论知识的实际问题