算法：生成树的数据结构和算法

生成树是图G的子集，其具有覆盖有最小可能边数的所有顶点。因此，生成树没有循环，也无法断开连接。

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

生成树木

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

生成树的一般属性

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

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

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

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

在加权图中，最小生成树是生成树，其权重最小于同一图的所有其他生成树。在实际情况中，该权重可以被测量为距离，拥塞，交通负载或任何表示边缘的任意值。

堆是平衡二叉树数据结构的特例，其中根节点密钥与其子节点进行比较并相应地进行排列。如果 α 有子节点 β 那么 -键(α)≥键(β)由于parent的值大于child的值，因此该属性会生成 Max Heap 。基于此标准，堆 ...

下一章：算法：堆数据结构