最小生成树 (MST)

在本文中，我们将讨论生成树和最小生成树。但在直接进入生成树之前，让我们先简要了解一下图及其类型。

Graph

图可以定义为一组顶点和连接这些顶点的边。图的类型如下：

• 无向图：无向图是指所有边都不指向任何特定方向的图，即它们不是单向的，而是双向的。它也可以定义为由一组 V 个顶点和一组 E 条边组成的图，每条边连接两个不同的顶点。
• 连通图：连通图是指从一个顶点到任何其他顶点总存在路径的图。如果我们可以通过沿任一方向的边从任何顶点到达任何其他顶点，则该图是连通的。
• 有向图：有向图也称为 digraphs。如果图中任意顶点或节点之间的所有边都是有向的或具有确定的方向，则该图是有向图（或 digraph）。

现在，让我们转向生成树这个主题。

什么是生成树？

生成树可以定义为无向连通图的子图。它包含所有顶点以及尽可能少的边。如果遗漏了任何一个顶点，它就不是生成树。生成树是图的一个子集，它没有环，也不能是不连通的。

一个生成树包含 (n-1) 条边，其中 'n' 是顶点（或节点）的数量。生成树的边可能有也可能没有分配权重。从给定的图 G 创建的所有可能的生成树将具有相同数量的顶点，但生成树中的边数将等于给定图中的顶点数减 1。

一个完整的无向图可以有 n^n-2 个生成树，其中 n 是图中的顶点数。假设，如果 n = 5，最大可能的生成树数量将是 5^5-2 = 125。

生成树的应用

基本上，生成树用于找到连接图中所有节点的最小路径。生成树的一些常见应用如下：

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

现在，让我们通过一个例子来理解生成树。

生成树的例子

假设图如下：

如上所述，生成树包含与图相同数量的顶点，上图中的顶点数为 5；因此，生成树将包含 5 个顶点。生成树中的边数将等于图中顶点数减 1。所以，生成树中将有 4 条边。

从上图创建的一些可能的生成树如下所示：

生成树的属性

生成树的一些属性如下：

• 一个连通图 G 可以有多个生成树。
• 生成树没有任何环或回路。
• 生成树是最小连通的，因此从树中删除一条边会使图变得不连通。
• 生成树是最大无环的，因此向树中添加一条边会产生一个环。
• 一个完全图最多可以创建 n^n-2 个生成树。
• 一个生成树有 n-1 条边，其中 'n' 是节点数。
• 如果图是一个完全图，那么可以通过移除最多 (e-n+1) 条边来构建生成树，其中 'e' 是边数，'n' 是顶点数。

因此，生成树是连通图 G 的一个子集，而不连通图没有生成树。

最小生成树

最小生成树可以定义为边的权重之和最小的生成树。生成树的权重是赋予生成树各边的权重之和。在现实世界中，这个权重可以被视为距离、交通负荷、拥堵或任何随机值。

最小生成树的例子

让我们通过一个例子来理解最小生成树。

上图的边权重之和为 16。现在，从上图创建的一些可能的生成树如下：

因此，从上述生成树中为给定加权图选择的最小生成树是：

最小生成树的应用

最小生成树的应用如下：

• 最小生成树可用于设计供水网络、电信网络和电网。
• 它可以用来在地图中寻找路径。

最小生成树的算法

可以使用以下算法从加权图中找到最小生成树：

• Prim 算法
• Kruskal 算法

让我们简要介绍一下上面列出的两种算法。

Prim 算法 - 它是一种贪心算法，从一个空的生成树开始。它用于从图中找到最小生成树。该算法找到边的子集，该子集包含图的每个顶点，使得边的权重之和可以最小化。

要了解更多关于 Prim 算法的信息，您可以点击：Prim 算法

Kruskal 算法 - 该算法也用于为连通加权图找到最小生成树。Kruskal 算法也遵循贪心方法，它在每个阶段找到一个最优解，而不是专注于全局最优解。

要了解更多关于 Prim 算法的信息，您可以点击：Kruskal 算法

好了，这就是本文的全部内容。希望这篇文章对您有帮助和启发。在这里，我们讨论了生成树和最小生成树以及它们的属性、例子和应用。