普利姆算法与克鲁斯卡尔算法

普利姆算法和克鲁斯卡尔算法都是用于解决最小生成树问题的经典算法。普利姆算法以一个初始顶点开始，以贪心的方式逐步选择与当前树连通的最小权值边，直到所有顶点都被包括进来。

克鲁斯卡尔算法通过对边集合按权值排序，并逐步选择权值最小的边，但保证不形成回路，直到生成树涵盖所有顶点。

两者的不同在于，普利姆算法是以顶点为驱动，而克鲁斯卡尔算法是以边为驱动。

1，普利姆算法是顶点优先，克鲁斯卡尔是边优先。二者应对不同情况效率不同。

2， 普利姆算法平均时间复杂度为O(n^2)，是顶点数的平方。

3，克鲁斯卡尔算法平均时间复杂度取决于选用的排序算法，是和边数相关的。

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

边数较少可以用Kruskal克鲁斯卡尔算法，因为克鲁斯卡尔算法算法每次查找最短的边。边数较多可以用普里姆算法，因为它是每次加一个顶点，对边数多的适用。

克鲁斯卡尔算法

假设WN=(V{E})是一个含有n个顶点的连通网，则按照克鲁斯卡尔算法构造最小生成树的过程为:先构造一个只含n个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有n棵树的一个森林。之后，从网的边集 E中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树;反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至森林中只有一棵树，也即子图中含有n-1条边为止。

普里姆算法

假设WN=(V{E})是一个含有n个顶点的连通网，

TV是WN上最小生成树中顶点的集合，TE是最小生成树中边的集合。显然，在算法执行结束时， TV=V，而TE是E的一个子集。在算法开始执行时，TE为空集，TV中只有一个顶点，因此，按普里姆算法构造最小生成树的过程为:在所有“其一个顶点已经落在生成树上，而另一个顶点尚未落在生成树上”的边中取一条权值为最小的边，逐条加在生成树上，直至生成树中含有n-1条边为止。