克鲁斯卡尔与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算法也可以对不连通图起作用。