最小生成树的实现算法之克鲁斯卡尔算法（Kruskal）

实现原理

与普里姆算法不同，克鲁斯卡尔算法主要以边为维度，每次从剩下的边中找权重值最小的边来构建最小生成树，具体实现思路如下：

• 将无向图的边按权重大小递增式排序，放到集合中
• 遍历该集合，找出权重最小的边，加入到结果生成树的集合中
• 如果结果生成树出现回路，则放弃这条边
• 重新执行步骤2，直至所有顶点被遍历，最终生成最小生成树

该实现原理图示如下：

复杂度分析

克鲁斯卡尔算法时间复杂度主要消耗在对边的遍历和回路校验上，假设图的边数是 e，则对应的时间复杂度是 O(eloge)，e 是指边的循环遍历次数，loge 指的是 isLoop 函数，尤其是 find 函数的时间复杂度，关于这种形式的 while 循环其实是个递归，所以对应时间复杂度是 loge。单从数量级上看克鲁斯卡尔算法要优于普里姆算法。