【图论笔记】克鲁斯卡尔算法(Kruskal)求最小生成树

【图论笔记】克鲁斯卡尔算法(Kruskal)求最小生成树

适用于

克鲁斯卡尔适合用来求边比较稀疏的图的最小生成树

简记:

将边按照升序排序,选取n-1条边,连通n个顶点。
添加一条边的时候,如何判断能不能添加这条边?(添加进来之后,会不会构成回路)
看标记,
和原来的标记不一样,就可以加入,
加入之后将他们的标记修改为一样的。

图解

请添加图片描述
第一步:创建一个连通图,并且给每个顶点都标记上不同的颜色

第二步:选取边<A,C>,选完之后C的颜色要和A相同
请添加图片描述
第三步:加入边<D,F>,将F的颜色改为D的蓝色
请添加图片描述
第四步:加入边<B,E>,将E改为紫色
请添加图片描述
第五步:添加边<C,F>,将F相连的节点改为绿色(包括它自己)
请添加图片描述
第六步:<A,D>不能加入,因为A和D的颜色一样。加入边<B,C>,将原来和B相连的节点的颜色都改为绿色。完
请添加图片描述

代码正在研究

相关推荐

  1. 算法基础之Kruskal算法生成

    2023-12-10 09:18:04       37 阅读

最近更新

  1. TCP协议是安全的吗?

    2023-12-10 09:18:04       18 阅读
  2. 阿里云服务器执行yum,一直下载docker-ce-stable失败

    2023-12-10 09:18:04       19 阅读
  3. 【Python教程】压缩PDF文件大小

    2023-12-10 09:18:04       18 阅读
  4. 通过文章id递归查询所有评论(xml)

    2023-12-10 09:18:04       20 阅读

热门阅读

  1. 图论与网络优化3

    2023-12-10 09:18:04       30 阅读
  2. gin自定义日志

    2023-12-10 09:18:04       46 阅读
  3. AlexNet

    AlexNet

    2023-12-10 09:18:04      40 阅读
  4. GitHub为Rust语言添加了供应链安全工具

    2023-12-10 09:18:04       44 阅读
  5. 用Go写一个缓存工具

    2023-12-10 09:18:04       45 阅读
  6. 本地部署 Qwen-Audio-Chat

    2023-12-10 09:18:04       40 阅读
  7. YOLOX 学习笔记

    2023-12-10 09:18:04       30 阅读
  8. Django模板

    2023-12-10 09:18:04       33 阅读
  9. Django模型

    2023-12-10 09:18:04       33 阅读
  10. properties配置和读取

    2023-12-10 09:18:04       28 阅读
  11. React和Preact 这样处理className更优雅

    2023-12-10 09:18:04       43 阅读
  12. wordpress小记

    2023-12-10 09:18:04       35 阅读
  13. spring 单元测试 Junit

    2023-12-10 09:18:04       38 阅读