最小生成树（minimum spanning tree，MST）是图论中最经典的算法之一。基于MST结构的聚类，分类和最短路径查询等复杂图算法，在效率和结果质量方面需要显着提高。随着互联网的迅猛发展，图数据规模也越来越大，包含数百万甚至上亿个指针的大图数据越发常见。因此，如何在大图数据上实现查询处理和数据挖掘算法已成为亟待解决的问题之一。此外，由于大图数据的动态性特征，如何动态地维护算法结果也势必成为最受关注的问题之一。针对目前集中式的最小生成树算法无法解决海量和动态图数据的问题，首先提出了分区Prim（partition Prim，PP）算法，基于此提出了前端驱动的并行MST算法——PB（PP Bor（u）vka）算法，并论证了PB算法的正确性。另外，基于MapReduce和BSP框架实现了PB算法。针对只删除动态图特征，提出了MST维护算法，以实现高效的增量计算。对提出的计算和维护算法进行了代价分析和比较。最后，使用真实和模拟数据集，验证了PB算法和维护算法的有效性，高效性和可扩展性。
