最小生成树求解方法与分析 报告人： 小组成员： 求解最小生成树方法 Prim算法 Kruskal算法 破圈法 三种算法的比较Prim算法 基本思路：任选一个定点V 0 ，连接于V 0 最近 的顶点V 1 ，得到子树T 1 ，在连接与T 1 最近的 顶点V 2 ，得到子树T 2 ，如此继续下去，直到 所得子树包含所有顶点。 时间复杂度：O（n 2 ）, n为图的定点数。Prim算法构造最小生成树过程Prim算法的抽象描述 PrimMST(G，T，r) /求图G的以r为根的MST，结果放在T=(U，TE)中 InitCandidateSet()； /初始化：设置初始的最短边候选集，并置T=(r，) for(k=0；kn-1；k+) /求n-1条树边 (u，v)=SelectLiShtEdge()； /选取最短边(u，v)； TT (u，v)；/扩充T ModifyCandidateSet()； kruskal算法 基本思路：假设连通网N=(V,E)，则令最小 生成树的初始状态为只有n个顶点而无边的 非连通图T=(V,),图中每个顶点自成一个连 通分量。在E中选择一个代价最小的边，若 该边依
