K12教育赛事综合服务平台
聚乐之家官方网站
下载聚乐之家官方App
专注青少年竞赛题库网站
以下讨论的对象均为存在最小生成树的带权无向连通图。
Prim算法的核心逻辑是每次从全局所有未加入生成树的边中选择权值最小的边，加入最小生成树
当使用邻接矩阵存储图时，Prim算法的时间复杂度为O(n²)（n为顶点数量），更适合处理稠密图场景
若图中存在权值为负数的边，Prim算法将无法计算出正确的最小生成树
Prim算法执行过程中，不需要维护已加入生成树的顶点集合，只需要对所有边按权值排序即可