首页 > 代码库 > 算法8-1:最小生成树简介
算法8-1:最小生成树简介
最小生成树是图论中的一个概念。首先介绍一下什么是生成树。生成树就是将一个图中所有的顶点全部连接在一起,并且保证图中没有出现回路。
下图不是生成树,因为没有连接所有的顶点。
下图不是生成树,因为图中有回路。
像下图这样的才是生成树。
生成树的概念介绍完了。那么最小生成树的概念就比较明确了,这里的最小指的是所有的边权重之和最小。
应用
下图是美国西雅图的自行车路线图,用的是最小生成树。
下图是随机生成的最小生成树,看起来非常像大自然的产物。最小生成树在自然界中比较常见。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。