首页 > 代码库 > 算法8-1:最小生成树简介

算法8-1:最小生成树简介

最小生成树是图论中的一个概念。首先介绍一下什么是生成树。生成树就是将一个图中所有的顶点全部连接在一起,并且保证图中没有出现回路。


下图不是生成树,因为没有连接所有的顶点。



下图不是生成树,因为图中有回路。



像下图这样的才是生成树。



生成树的概念介绍完了。那么最小生成树的概念就比较明确了,这里的最小指的是所有的边权重之和最小。


应用


下图是美国西雅图的自行车路线图,用的是最小生成树。



下图是随机生成的最小生成树,看起来非常像大自然的产物。最小生成树在自然界中比较常见。