普里姆算法介绍

普里姆算法主要是求最小生成树

最小生成树

最小生成树(Minimum Cost Spanning Tree)，简称MST

• 给定一个带权的无向连通图如何选取一棵生成树，使树上所有边上权的总和为最小，这叫最小生成树
• N个顶点，一定有N-1条边
• 包含全部顶点
• N-1条边都在图中
• 求最小生成树的算法主要是普里姆算法和克鲁斯卡尔算法