原文: https://www.programiz.com/dsa/spanning-tree-and-minimum-spanning-tree

在本教程中,您将通过示例和图形学习有关生成树和最小生成树的信息。

在学习生成树之前,我们需要了解两个图:无向图和连接图。

无向图是其中边没有指向任何方向的图(即,边是双向的)。

生成树和最小生成树 - 图1

无向图

连通图是其中始终存在从顶点到任何其他顶点的路径的图。

生成树和最小生成树 - 图2

连通图


生成树

生成树是无向图和连通图的子图,其中包括图的所有顶点,这些顶点的边数最少。 如果缺少顶点,则它不是生成树。

边可以分配权重,也可以不分配权重。

可以从完整图形创建的具有n顶点的生成树总数等于n^(n-2)

如果我们有n = 4,则最大可能的生成树数等于4^(4-2) = 16。 因此,可以从具有 4 个顶点的完整图形中形成 16 个生成树。


生成树的示例

让我们通过以下示例了解生成树:

让原始图为:

生成树和最小生成树 - 图3

普通的图

可以从上图创建的一些可能的生成树是:

生成树和最小生成树 - 图4

一棵生成树

生成树和最小生成树 - 图5

一棵生成树

生成树和最小生成树 - 图6

一棵生成树

生成树和最小生成树 - 图7

一棵生成树

生成树和最小生成树 - 图8

一棵生成树

生成树和最小生成树 - 图9

一棵生成树


最小生成树

最小生成树是其中边的权重之和尽可能最小的生成树。


生成树的示例

让我们借助下面的示例了解上面的定义。

初始图形为:

生成树和最小生成树 - 图10

带权图

上图可能的生成树是:

生成树和最小生成树 - 图11

最小生成树 - 1

生成树和最小生成树 - 图12

最小生成树- 2

生成树和最小生成树 - 图13

最小生成树 - 3

生成树和最小生成树 - 图14

最小生成树 - 4

上述生成树中的最小生成树为:

生成树和最小生成树 - 图15

最小生成树

使用以下算法可找到图中的最小生成树:

  1. Prim 的算法
  2. Kruskal 算法

生成树应用

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

最小生成树应用

  • 在地图中查找路径
  • 设计诸如电信网络,供水网络和电网的网络。