使用贪婪算法理解Prim算法

"Prim算法普里姆-贪婪算法设计" Prim算法是一种用于寻找加权无向图中最小生成树的著名算法，由捷克数学家Vojtěch Jarník于1930年提出，后由美国计算机科学家Robert C. Prim在1957年独立发现并推广。它采用的是贪婪算法的思想，即在每一步中选择当前最优的决策，以期望最终达到全局最优。 贪婪算法的核心是每一步都采取局部最优解，希望这些局部最优解组合起来能得出全局最优解。在Prim算法中，这个局部最优解是指每次添加一条连接已选顶点集合和未选顶点集合的边，这条边的权重最小。算法开始时，已选顶点集合只有一个（通常是任意选择的一个顶点），然后逐步增加顶点，直到集合包含所有顶点，形成一棵最小生成树。 具体步骤如下： 1. 初始化：选择一个起始顶点，将其加入最小生成树S，其余顶点置于未选集合V-S。 2. 迭代过程：对于当前的V-S集合中的所有顶点，找到与S集合中的顶点相连且权值最小的边(u, v)。 3. 将找到的最小边的另一端顶点v加入S集合，移除V-S集合。 4. 重复步骤2和3，直到S集合包含了所有的顶点V。 5. 最终，S集合中的边构成的就是原始图G的最小生成树。 在实际应用中，Prim算法可以使用优先队列（如二叉堆）来高效地找到每一步的最小边，降低时间复杂度。对于n个顶点的图，Prim算法的时间复杂度通常为O(n^2)或O(m log n)，其中m是边的数量。 贪婪算法并不总是能确保得到全局最优解，但Prim算法在加权无向图中寻找最小生成树的情况下是正确的。这是因为Prim算法始终选择当前能够连接到已选集合且权重最小的边，这保证了最后得到的树的总权重不会超过任何其他可能的最小生成树。 在贪婪算法实例中，例如币值统计问题，我们通过贪婪策略（先取大面额的币种）来减少找零的张数，但这并不保证是最优解，因为有些情况下，先取小面额的币种可能会得到更少的张数。然而，Prim算法在寻找最小生成树的问题中是保证能得到最优解的贪婪算法之一。