day57 | prim 和 kruskal算法

prim

  • 维护一个最小生成树的点集合
  • minWeight 数组表示点到这个集合的距离
  • 默认所有节点离这个数的距离是无穷大
  • 随机选取一个节点,然后更新相连节点的 minWeight 数组
  • 持续遍历所有不在树里面节点,
  • 找到离这个树最近的节点cur
  • 把 cur 加入到树里面,并且更新和 cur 关联节点的minWeight

Kruskal算法

  • 维护一个最小生成树的边集合
  • 遍历所有边,
  • 如果两个节点不在同一个集合里,则加入边,并且加到一个集合中
  • 不在一个集合则跳过
全部评论

相关推荐

10-26 13:03
已编辑
门头沟学院 物流经理
在okr拆解的小太阳...:实习待过,我待的部门氛围很好,基本不加班,双休有保证。
投递正浩创新EcoFlow等公司10个岗位
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务