克鲁斯卡尔与PRM
在计算机科学中，Prim和Kruskal的算法是一种贪婪的算法，它为连通加权无向图寻找最小生成树。生成树是图的子图，使得图的每个节点都由一条路径连接起来，这条路径就是树。每棵生成树都有一个权重，所有生成树的最小可能权重/代价就是最小生成树（MST）。
关于Prim算法的更多信息
该算法由捷克数学家Vojtěch Jarník于1930年开发，随后由计算机科学家robertc.Prim于1957年独立开发。1959年，埃德斯格尔·迪克斯特拉重新发现了它。该算法可分为三个关键步骤；
给定有n个结点的连通图和每条边各自的权重，
1从图中选择任意节点并将其添加到树T（将是第一个节点）
2考虑连接到树中节点的每条边的权重并选择最小值。在树T的另一端添加边和节点，并从图中移除边。（如果存在两个或多个最小值，请选择任意一个）
三。重复步骤2，直到n-1条边添加到树中。
在这种方法中，树从一个任意节点开始，并在每个循环中从该节点开始扩展。因此，要使算**常工作，图必须是连通图。Prim算法的基本形式具有O（V2）的时间复杂度。
关于克鲁斯卡尔算法的更多信息
约瑟夫·克鲁斯卡尔（Joseph Kruskal）开发的算法出现在1956年的《美国数学学会会刊》上。克鲁斯卡尔的算法也可以用三个简单的步骤来表达。
给定有n个节点的图和每条边各自的权重，
1选择整个图中权重最小的弧，添加到树中并从图中删除。
2对于其余的边，选择权重最小的边，以不形成循环的方式。将边添加到树并从图形中删除。（如果存在两个或多个最小值，请选择任意一个）
三。重复步骤2中的过程。
在该方法中，算法从最小加权边开始，在每个周期继续选择每个边。因此，在算法中，图不需要连通。Kruskal算法的时间复杂度为O（logV）
克鲁斯卡尔算法和普里姆算法有什么区别？
•Prim的算法用一个节点初始化，而Kruskal的算法用一个边初始化。
•Prim的算法从一个节点延伸到另一个节点，而Kruskal算法选择边的方式不是基于最后一步。
•在prim算法中，图必须是连通图，而Kruskal算法也可以对不连通图起作用。
