数据结构和算法 - 生成树

生成树是图G的子集,其中所有顶点都覆盖有尽可能少的边.因此,生成树没有循环,也无法断开连接.

通过这个定义,我们可以得出结论,每个连通和无向图G都至少有一个生成树.断开连接的图形没有任何生成树,因为它不能跨越所有顶点.

Spanning Trees

我们从一个完整的图表中找到了三棵生成树.完整的无向图可以具有最大 n n-2 数量的生成树,其中 n 是节点的数量.在上面提到的例子中, n是3,因此 3 3 :  2 = 3 生成树是可能的.

生成树的常规属性

我们现在知道一个图可以有多个生成树.以下是生成树的一些属性,连接到图G :

  • 连接图G可以有多个生成树.

  • 图G的所有可能的生成树,具有相同数量的边和顶点.

  • 生成树没有任何循环(循环).

  • 从生成树中删除一条边会使图形断开连接,即生成树最小连接.

  • 向生成树添加一条边将创建一个电路或循环,即生成树是最大非循环.

生成树的数学属性

  • 生成树有 n-1 个边,其中 n 是节点数(顶点).

  • 从完整图表中删除最大值 e  -  n +  1 边缘,我们可以构建生成树.

  • 完整的图可以有最大 n n-2 生成树的数量.

因此,我们可以得出结论,生成树是连接的图G的子集,断开连接的图形没有生成树.

生成树的应用

生成树主要用于查找连接所有节点的最小路径图形.生成树的常见应用是 :

  • 民用网络规划

  • 计算机网络路由协议

  • 群集分析

让我们通过一个小例子来理解这一点.考虑一下,城市网络是一个巨大的图形,现在计划以这样的方式部署电话线,即在最小线路中我们可以连接到所有城市节点.这是生成树进入图片的地方.

最小生成树(MST)

在加权图中,最小生成树是跨越树的权重最小,而不是同一图的所有其他生成树.在实际情况中,此权重可以测量为距离,拥塞,流量负载或任何表示边缘的任意值.

最小生成树算法

我们将在这里学习两个最重要的生成树算法 :

  • Kruskal的算法

  • Prim算法

两者都是贪心算法.