prim

Prim是一个简单而优雅的算法，用于在图中找到最小生成树。它从一个顶点开始，逐步扩展已选择的顶点集，直到所有顶点都被包含进来。Prim算法的核心思想是每次选择距离当前已选择顶点集最近的一个顶点，并将其加入已选择的顶点集中。在选择过程中，使用一个优先队列来存储未被选择的顶点以及它们与已选择顶点之间的距离，以便快速找到下一个要加入的顶点。Prim算法保证了生成的最小生成树具有最短的总边长，因此在实践中得到了广泛应用。