离散数学 - 生成树

---

无向连通图 $G$ 的生成树是至少包含 $G$ 所有顶点的树。一个图可能有许多生成树。

例子

最小生成树

指定权值小于或等于带权连通无向图 $G$ 的每个可能生成树权值的生成树，称为最小生成树 (MST)。生成树的权重是分配给生成树每条边的所有权重的总和。

例子

克鲁斯卡尔算法

克鲁斯卡尔算法是一种贪心算法，它为连通的加权图找到最小生成树。它找到该图的一棵树，其中包括每个顶点，并且树中所有边的总权重小于或等于每个可能的生成树。

算法

步骤 1 - 根据边权重按升序排列给定图 $G (V,E)$ 的所有边。

步骤 2 - 从图中选择最小的加权边，并检查它是否与迄今为止形成的生成树形成一个循环。

步骤 3 - 如果没有循环，则将此边包含到生成树中，否则丢弃它。

步骤 4 - 重复步骤 2 和步骤 3，直到生成树中剩余 $(V-1)$ 条边。

问题

假设我们想要使用 Kruskal 算法找到以下图 G 的最小生成树。

解决方案

根据上图，我们构建了下表 -

现在我们将根据边权重按升序重新排列表格 -

由于我们在上图中获得了所有 5 条边，因此我们停止算法，这就是最小生成树，其总权重为 $(1 + 2 + 3 + 5 + 9) = 20$。

普里姆算法

Prim 算法由数学家 Vojtech Jarnik 和 Robert C. Prim 于 1930 年发现，是一种贪婪算法，可为连通加权图找到最小生成树。它找到该图的一棵树，其中包括每个顶点，并且树中所有边的总权重小于或等于每个可能的生成树。Prim 的算法在密集图上速度更快。

算法

• 使用从图中随机选择的单个顶点初始化最小生成树。

• 重复步骤 3 和 4，直到所有顶点都包含在树中。

• 选择一条将树与树中尚未存在的顶点连接起来的边，使得该边的权重最小并且包含该边不会形成环。

• 添加选定的边及其连接到树的顶点。

问题

假设我们想要使用 Prim 算法找到以下图 G 的最小生成树。

解决方案

这里我们从顶点“a”开始并继续。

这是最小生成树，其总权重为 $(1 + 2 + 3 + 5 + 9) = 20$。