数据结构&算法 生成树

• 

  生成树

  生成树是图G的子集，图G的所有顶点都覆盖有尽可能少的边。因此，生成树没有周期，因此无法断开连接。通过这个定义，我们可以得出一个结论，即每个连通和无向的图G至少都有一个生成树。断开连接的图没有任何生成树，因为它无法跨越到其所有顶点。

  

  我们从一张完整的图上发现了三棵生成树。一个完整的无向图最多可以具有n^n-2个生成树，其中n是节点数。在上述示例中，n为3，因此3^3-2= 3棵生成树是可能的。
• 

  生成树的一般属性

  现在我们了解到，一张图可以有不止一棵生成树。以下是连接到图G的生成树的一些属性-

  • 连通图G可以具有一个以上的生成树。
  • 图G的所有可能的生成树具有相同数量的边和顶点。
  • 生成树没有任何循环（循环）。
  • 从生成树中删除一条边将使图断开连接，即，生成树已最小连接。
  • 在生成树上添加一条边会创建一个电路或回路，即生成树最大程度是非循环的。
• 

  生成树的数学性质

  • 生成树具有n-1个边，其中n是节点（顶点）的数量。
  • 从一个完整的图中，通过去除最大e-n + 1个边，我们可以构建生成树。
  • 一个完整的图最多可以包含n^n-2个生成树。

  因此，我们可以得出结论，生成树是连接图G的子集，而断开连接的图没有生成树。
• 

  生成树的应用

  生成树基本上用于查找连接图中所有节点的最小路径。生成树的常见应用是-

  • 民用网络规划
  • 计算机网络路由协议
  • 聚类分析

  让我们通过一个小例子来了解这一点。考虑到城市网络是一个巨大的图，并且现在计划以这样的方式部署电话线：我们可以在最少的线路上连接到所有城市节点。这是生成树出现应用的地方。
• 

  最小生成树（MST）

  在加权图中，最小生成树是比同一图的所有其他生成树具有最小权重的生成树。在现实世界中，可以将这种权重度量为距离，拥塞，交通负荷或任何表示边缘的任意值。
• 

  最小生成树算法

  我们将在这里了解两种最重要的生成树算法-

  • 克鲁斯卡尔算法
  • 普里姆算法

  两者都是贪婪算法。