实现原理
与普里姆算法不同,克鲁斯卡尔算法主要以边为维度,每次从剩下的边中找权重值最小的边来构建最小生成树,具体实现思路如下:
- 将无向图的边按权重大小递增式排序,放到集合中
- 遍历该集合,找出权重最小的边,加入到结果生成树的集合中
- 如果结果生成树出现回路,则放弃这条边
- 重新执行步骤2,直至所有顶点被遍历,最终生成最小生成树
该实现原理图示如下:
复杂度分析
克鲁斯卡尔算法时间复杂度主要消耗在对边的遍历和回路校验上,假设图的边数是 e,则对应的时间复杂度是 O(eloge),e 是指边的循环遍历次数,loge 指的是 isLoop 函数,尤其是 find 函数的时间复杂度,关于这种形式的 while 循环其实是个递归,所以对应时间复杂度是 loge。单从数量级上看克鲁斯卡尔算法要优于普里姆算法。
评论区