K12教育赛事综合服务平台
聚乐之家官方网站
下载聚乐之家官方App
专注青少年竞赛题库网站
以下描述均针对带权无向连通图的最小生成树求解场景，默认讨论无特殊优化的基础实现。
Prim算法的核心思想是每次选择全局权值最小的边加入生成树集合，只要不产生环就保留
使用邻接矩阵存储图时，Prim算法的时间复杂度为O(n²)，其中n为图的顶点总数
Prim算法相较于Kruskal算法，更适合处理边数远小于顶点数的稀疏图场景
Prim算法执行过程中，已经加入最小生成树的顶点集合可以存在多个连通分量