贪心算法详解：Prim最小生成树算法

"Prim算法-第4讲 贪心算法" 贪心算法是一种解决问题的策略，它通过在每一步选择当前看起来最优的解决方案，希望能够通过局部最优的选择一步步达到全局最优的结果。这种算法并不保证在所有情况下都能得到最优解，但它在某些特定问题上表现优秀，比如构建最小生成树和寻找单源最短路径。 Prim算法是贪心算法的一个经典应用，主要用于寻找加权无向图的最小生成树。最小生成树是图中连接所有顶点的树形结构，其边的权重之和最小。在给定的图G=(V,E)，V={1,2,…,n}，Prim算法按照以下步骤进行： 1. 初始化：选择一个起始顶点（例如1号顶点）作为已选集合S，其余顶点位于未选集合V-S中。 2. 贪心选择：在每次迭代中，从V-S中找出与S中顶点相连且权重最小的边(i, j)，并将j加入S中。这里，i属于S，j属于V-S，c[i][j]表示边(i, j)的权重。 3. 重复步骤2，直到S包含所有顶点，即S=V。 在这个过程中，Prim算法每次选取的边都是当前未选顶点中与已选顶点连接的权重最小的边，这样逐步将图的各个部分连接起来，最终形成一棵最小生成树。 然而，贪心算法并非总是能得出全局最优解。例如，在找硬币的例子中，如果硬币面值不同，贪心算法可能无法找到最少数量的硬币组合。对于找1角5分的问题，贪心算法可能会选择1个1角1分和4个1分，而实际上3个5分是更好的解决方案。 活动安排问题也是贪心算法可以解决的问题之一。在这个问题中，我们需要在一系列活动之间做出选择，使得尽可能多的活动能够共享同一资源，且活动之间不冲突。贪心算法在这里会选择结束时间最早的活动，这样可以确保尽可能多的活动在不相互干扰的情况下进行。 总结来说，Prim算法是贪心算法的一种具体实现，用于找到加权无向图的最小生成树。贪心算法的核心思想是在每一步选择当前最优，但并不保证总能得到全局最优解。它在特定场景下，如最小生成树问题和活动安排问题，表现出较高的效率和实用性。