图论算法：最小生成树介绍

本文概述

• 树
• 生成树
• 生成树的属性
• 最小生成树

树

树是具有以下属性的图：

1. 图形已连接（可以从任何地方到任何地方）
2. 没有循环（Acyclic）

生成树

给定一个连接的无向图, 该图的生成树是一个子图, 该子图是一棵树, 并连接了所有顶点。单个图可以具有许多生成树。

例如：

对于上面连接的图。可能有多个生成树, 例如

生成树的属性

1. 可能有几个具有最小权重的相同权重的最小生成树。
2. 如果给定图的所有边缘权重都相同, 则该图的每个生成树都是最小的。
3. 如果每个边缘都有不同的权重, 那么将只有一个唯一的最小生成树。
4. 连通图G可以具有多个生成树。
5. 断开连接的图不必覆盖树, 也可以不覆盖所有顶点。
6. 生成树不包含循环。
7. 生成树具有（n-1）个边, 其中n是顶点数。

甚至增加一个单边都会导致生成树失去其非周期性特性, 而消除一个单边会导致生成树失去连通性。

最小生成树

最小生成树是具有最小总成本的生成树。如果我们有一个链接的无向图, 其权重（或成本）与每个边结合。那么生成树的成本将是其边缘成本的总和。