Prim's - HolmesJJ/Data-Structures-and-Algorithms GitHub Wiki

核心思想

• 贪婪算法
• 从顶点出发，优先选择与顶点相连边权最小的边
• 具有相同权值的边，则可任意选取其中之一

算法步骤（最小生成树组件Partition属性）

1. 选定一个结点作为一个已选集合a，剩下的结点为另一个未选集合b
2. 将横跨两个分区Partition且边权最小的边加入最小生成树
3. 将刚刚加入最小生成树的边所相连的不在集合a中的结点加入已选集合a，并从未选集合b中移除，直到所有的点加入已选集合a

标准写法

要点

• 维护一个表储存边权，每次需要找到边权最小的边，优先队列或AVL树搜索的时间复杂度是O(logn)