克鲁斯卡尔算法步骤，克鲁斯卡尔算法适用于什么图

很多朋友对于克鲁斯卡尔算法步骤和克鲁斯卡尔算法适用于什么图不太懂，今天就由小编来为大家分享，希望可以帮助到大家，下面一起来看看吧！

什么是布鲁斯卡尔算法

布鲁斯卡尔算法是一种用来寻找最小生成树最常用的算法，在剩下的所有未选取的边中，找到最小边，如果和已选取的边构成回路，则放弃，选取次小边。克鲁斯卡尔算法的时间复杂度为O（eloge），因此它相对于普里姆算法而言，适合于求边稀疏的网的最小生成树。

已知一个无向图如下，分别用普里姆和克鲁斯卡尔算法生成最小生成树（假设以1为起点，试画出构造过程）

图看不清，p，树向外扩张，找最短外扩路径k，增加一条不会造成回路的边(现在选中的边可以暂不相连)

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

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

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

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

克鲁斯卡尔算法的时间复杂度

克鲁斯卡尔算法是在剩下的所有未选取的边中，找最小边，如果和已选取的边构成回路，则放弃，选取次小边。

克鲁斯卡其尔算法的时间复杂度为O（eloge）(e为网中边的数目)，因此它相对于普里姆算法而言，适合于求边稀疏的网的最小生成树。

END，本文到此结束，如果可以帮助到大家，还望关注本站哦！