一、概念最小生成树(MinimumCostSpanningTree)，简称MST。1)给定一个带权的无向连通图,如何选取一棵生成树,使树上所有边上权的总和为最小,就叫最小生成树2)N个顶点，一定有N-1条边3)包含全部顶点4)N-1条边都在图中（好像不能形成闭合回路）求最小生成树的算法主要是普里姆算法和克鲁斯卡尔算法二、普里姆算法Prim1)普利姆(Prim)算法求最小生成树，也就是在包含n个顶点的连通图中，找出只有(n-1)条边包含所有n个顶点的连通子图，也就是所谓的极小连通子图2)普利姆的算法思路如下:        (1)设G=(V,E)是连通网，T=(U,D)是最小生成树，V,U是顶点

一、概念最小生成树(MinimumCostSpanningTree)，简称MST。1)给定一个带权的无向连通图,如何选取一棵生成树,使树上所有边上权的总和为最小,就叫最小生成树2)N个顶点，一定有N-1条边3)包含全部顶点4)N-1条边都在图中（好像不能形成闭合回路）求最小生成树的算法主要是普里姆算法和克鲁斯卡尔算法二、普里姆算法Prim1)普利姆(Prim)算法求最小生成树，也就是在包含n个顶点的连通图中，找出只有(n-1)条边包含所有n个顶点的连通子图，也就是所谓的极小连通子图2)普利姆的算法思路如下:        (1)设G=(V,E)是连通网，T=(U,D)是最小生成树，V,U是顶点