算法 - 图（Graph）- 生成树（Spanning Tree） - Go语言中文社区

算法 - 图（Graph）- 生成树（Spanning Tree）

  • 生成树（Spanning Tree），也称为支撑树
  • 连通图的极小连通子图，它含有图中全部的n个顶点，恰好只有n-1条边
    在这里插入图片描述

最小生成树（Minimum Spanning Tree）

  • 最小生成树（Minimum Spanning Tree，简称MST）
    也称为最小权重生成树（Minimum Weigth Spanning Tree）、最小支撑树
    是所有生成树中，总权值最小的那棵
    适用于有权的连通图
    在这里插入图片描述
  • 最小生成树在许多领域都有重要的作用，例如：
    要在n个城市之间铺设光缆，使它们都可以通信
    铺设光缆的费用很高，且各个城市之间因为距离不同等因素，铺设光缆的费用也不同
    如何铺设光缆的总费用最低？
  • 如果图的每一条边的权值都互不相同，那么最小生成树将只有一个，否则可能会有多个最小
    生成树
  • 求最小生成树的2个经典算法
  1. Prim（普里姆算法）
  2. Kruskal（克鲁斯科尔算法）
版权声明：本文来源CSDN，感谢博主原创文章，遵循 CC 4.0 by-sa 版权协议，转载请附上原文出处链接和本声明。
原文链接：https://blog.csdn.net/songzhuo1991/article/details/103071532
站方申明：本站部分内容来自社区用户分享，若涉及侵权，请联系站方删除。
  • 发表于 2023-01-02 08:34:15
  • 阅读 ( 333 )
  • 分类：算法

你可能感兴趣的文章

精选的优质文章

0 条评论

请先 登录 后评论

官方社群

GO教程

推荐文章

猜你喜欢

随便看看

来源51CTO

如果觉得我的文章对您有用，请随意打赏。你的支持将鼓励我继续创作！