Prim算法求解最小生成树

Prim算法是一种贪心算法，用于求解最小生成树。它从一个顶点开始，每次选择距离当前顶点最近的一个未访问过的顶点，并将其加入最小生成树中。重复这个过程，直到所有的顶点都被加入到最小生成树中。 Prim算法的基本思想是：在每一步中，总是选择使得总权值最小的边来连接两个子集。具体来说，它维护了一个集合U和一个集合V，其中U表示已经加入最小生成树的顶点集合，V表示尚未加入最小生成树的顶点集合。在每一步中，它从V中选择一个距离当前顶点最近的顶点u，并将其加入U中。然后，它更新所有与u相连的边的权值，并将这些边的另一端点加入到候选集中。最后，它从候选集中选择距离当前顶点最近的顶点v，并将其加入U中。