普里姆算法 (最小生成树)

在本文中，我们将讨论普里姆算法。除了算法，我们还将了解普里姆算法的复杂性、工作原理、示例和实现。

在开始主要主题之前，我们应该讨论一些基本和重要的术语，例如生成树和最小生成树。

生成树 - 生成树是无向连通图的子图。

最小生成树 - 最小生成树可以定义为边的权重之和最小的生成树。生成树的权重是赋予生成树边的权重之和。

现在，让我们开始主要主题。

普里姆算法是一种贪婪算法，用于从图中找到最小生成树。普里姆算法找到边的子集，该子集包含图中的每个顶点，以便边的权重之和最小化。

普里姆算法从一个节点开始，并在每一步探索所有相邻节点和所有连接边。选择权重最小且不会在图中产生循环的边。

普里姆算法如何工作？

普里姆算法是一种贪婪算法，它从一个顶点开始，并不断添加权重最小的边，直到达到目标。实现普里姆算法的步骤如下：

• 首先，我们必须用随机选择的顶点初始化一个 MST。
• 现在，我们必须找到所有将上述步骤中的树与新顶点连接起来的边。从找到的边中，选择最小的边并将其添加到树中。
• 重复步骤 2，直到形成最小生成树。

普里姆算法的应用包括：

• 普里姆算法可用于网络设计。
• 它可用于创建网络循环。
• 它还可用于铺设电线电缆。

普里姆算法示例

现在，让我们通过一个例子来看看普里姆算法的工作原理。通过例子理解普里姆算法会更容易。

假设，一个加权图是 -

步骤 1 - 首先，我们必须从上图中选择一个顶点。让我们选择 B。

步骤 2 - 现在，我们必须选择并添加从顶点 B 出发的最短边。从顶点 B 出发有两条边，即 B 到 C，权重为 10；B 到 D，权重为 4。在这些边中，边 BD 具有最小权重。因此，将其添加到 MST 中。

步骤 3 - 现在，再次选择所有其他边中权重最小的边。在这种情况下，边 DE 和 CD 就是这样的边。将它们添加到 MST 中并探索 C 的相邻顶点，即 E 和 A。因此，选择边 DE 并将其添加到 MST 中。

步骤 4 - 现在，选择边 CD，并将其添加到 MST 中。

步骤 5 - 现在，选择边 CA。在这里，我们不能选择边 CE，因为它会在图中创建一个循环。因此，选择边 CA 并将其添加到 MST 中。

因此，步骤 5 中生成的图是给定图的最小生成树。MST 的成本如下 -

MST 的成本 = 4 + 2 + 1 + 3 = 10 单位。

算法

普里姆算法的复杂性

现在，让我们看看普里姆算法的时间复杂性。普里姆算法的运行时间取决于用于图的数据结构和边的排序。下表显示了一些选择 -

• 时间复杂度

普里姆算法可以通过使用邻接矩阵或邻接表图表示来简单实现，并且要添加权重最小的边需要线性搜索权重数组。它需要 O(|V|²) 的运行时间。通过使用堆实现来在算法的内循环中查找最小权重边，可以进一步改进。

普里姆算法的时间复杂性为 O(E logV) 或 O(V logV)，其中 E 是边的数量，V 是顶点的数量。

普里姆算法的实现

现在，让我们看看普里姆算法的实现。

程序： 编写一个程序以 C 语言实现普里姆算法。

输出

这就是本文的全部内容。希望本文能为您提供帮助和信息。

普里姆算法的多项选择题

问题 1 设 C1 是由普里姆算法计算的无向图 G 的最小生成树的成本。设 C2 是由 Kruskal 算法计算的同一图的最小生成树的成本。那么下列哪个语句总是正确的？

1. C1 > C2
2. C1 < C2
3. C1 = C2
4. C1 不等于 C2

问题 2 对于给定图，当使用邻接矩阵和最小堆实现普里姆算法时，该算法的时间复杂性是多少，该图有 V 个顶点和 E 条边？

1. O(V + E)
2. O(E logV0
3. O(V2)
4. O(V logV + E logV)

问题 3 哪种数据结构用于高效实现普里姆算法？

1. Stack
2. Queue
3. 优先队列（最小堆）
4. 哈希表

问题 4 关于普里姆算法，以下哪个语句是/是正确的？

1. 它是一种最短路径算法
2. 它是一种最小生成树算法
3. 该算法仅适用于有向图
4. 它不处理加权图

问题 5： 以下哪项在普里姆算法的上下文中是/是正确的？

1. 普里姆算法可以使用斐波那契堆实现，以提高效率。
2. 对于任何给定图，总是会生成唯一的最小生成树。
3. 它适用于带权重的连通无向图。
4. 普里姆算法可以处理图中负的边权重。