侧边栏壁纸
  • 累计撰写 247 篇文章
  • 累计创建 16 个标签
  • 累计收到 0 条评论

目 录CONTENT

文章目录

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

kaixindeken
2021-04-23 / 0 评论 / 0 点赞 / 104 阅读 / 463 字

实现原理

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

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

该实现原理图示如下:

1.png

复杂度分析

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

0

评论区