克鲁斯卡尔算法描述
什么是布鲁斯卡尔算法？
什么是布鲁斯卡尔算法？
布鲁斯卡尔算法是一种用来寻找最小生成树最常用的算法，在剩下的所有未选取的边中，找到最小边，如果和已选取的边构成回路，则放弃，选取次小边。克鲁斯卡尔算法的时间复杂度为O（eloge），因此它相对于普里姆算法而言，适合于求边稀疏的网的最小生成树。
求最小生成树问题常用的方法？
主要有两个： 1.普里姆（Prim)算法 特点：时间复杂度为O(n2).适合于求边稠密的最小生成树。
2.克鲁斯卡尔（Kruskal)算法 特点：时间复杂度为O(eloge)(e为网中边数），适合于求稀疏的网的最小生成树。 Prim算法 和 Kruskal算法 Prim算法逐次将最小权的边和相应顶点加到集合中，适合于求边稠密的最小生成树；Kruskal算法先将所有边都放入集合，然后再逐个选择最小权的边，适合于求稀疏的网的最小生成树。 详细过程请参考相关资料 Prim算法 Kruskal算法
克鲁斯卡尔算法的时间复杂度？
克鲁斯卡尔算法是在剩下的所有未选取的边中，找最小边，如果和已选取的边构成回路，则放弃，选取次小边。
克鲁斯卡其尔算法的时间复杂度为O（eloge）(e为网中边的数目)，因此它相对于普里姆算法而言，适合于求边稀疏的网的最小生成树。
无向图的最小生成树？
无向图的最小生成树？
最小生成树（MST）：权值最小的生成树。
构造网的最小生成树必须解决下面两个问题：
1、尽可能选取权值小的边，但不能构成回路；
2、选取n－1条恰当的边以连通n个顶点；
MST性质：假设G＝(V,E)是一个连通网，U是顶点V的一个非空子集。若(u,v)是一条具有最小权值的边，其中u∈U，v∈V－U，则必存在一棵包含边(u,v)的最小生成树。
1.prim算法
基本思想：假设G＝(V，E)是连通的，TE是G上最小生成树中边的集合。算法从U＝{u0}（u0∈V）、TE＝{}开始。重复执行下列操作：
在所有u∈U，v∈V－U的边(u，v)∈E中找一条权值最小的边(u0,v0)并入集合TE中，同时v0并入U，直到V＝U为止。
此时，TE中必有n-1条边，T=(V，TE)为G的最小生成树。
Prim算法的核心:始终保持TE中的边集构成一棵生成树。
注意：prim算法适合稠密图，其时间复杂度为O(n^2)，其时间复杂度与边得数目无关。