普里姆算法和克鲁斯卡尔算法区别

普里姆算法和克鲁斯卡尔算法是两种用于求解最小生成树问题的算法。它们的主要区别在于算法的思想、适用范围和实现方式。

普里姆算法是一种贪心算法，从一个顶点开始，逐步选择与当前子图相连的权值最小的边，直至生成树包含图中所有顶点。它适用于稠密图，即节点较多、边数较多的情况。普里姆算法的时间复杂度为O（N^2），其中N为节点数。

克鲁斯卡尔算法也是一种基于贪心策略的算法，用于求解带权无向连通图的最小生成树问题。该算法的目标是在保证图连通的前提下，选择边的权值之和最小的子图作为最小生成树。克鲁斯卡尔算法通常适用于稀疏图，即节点较多、边数相对较少的情况。它的时间复杂度为O（ElogE），其中E为边数。

总的来说，普里姆算法和克鲁斯卡尔算法都是有效的求解最小生成树问题的算法，根据具体情况选择不同的算法可以提高计算效率。

普里姆算法的发展

普里姆算法（Prim算法），图论中的一种算法，可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点（英语是Vertex graph theory），且其所有边的权值之和亦为最小。

该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克（英语是Vojtěch Jarník）发现；并在1957年由美国计算机科学家罗伯特·普里姆（英语是Robert C Prim）独立发现；1959年，艾兹格·迪科斯彻再次发现了该算法。因此，在某些场合，普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆－亚尔尼克算法。

以上内容参考百度百科-Prim