最小生成树(MST)作为图论中最经典算法之一,引发了人们经久不衰的关注。由于MST的性质,在规划、网络和医学等各个领域得到了广泛的应用。同时,基于MST结构的聚类、分类和最短路径查询等复杂图算法,在效率和结果质量方面均有显著提高。然而,随着互联网的迅猛发展,图规模也变得越来越大,包含千万甚至上亿个顶点的大规模图越发常见。因此,如何在大规模图上实现查询处理和数据挖掘算法已成为了亟待解决的问题之一。除此之外,由于大规模图的动态性特征,即图的拓扑结构可能会发生改变,如何动态地维护算法结果也势必成为最受关注的问题之一。本文提出并行MST算法和MST动态维护算法,为上述问题提供了坚实的基础。首先,本文利用以边为中心的设计思想,提出了边驱动的并行MST算法。同时,本文设计了分布式索引、分区加速和基于直方图排序等优化技术,提高了算法的执行效率。随后,基于不同的通信模型实现了并行MST算法并分析了算法的时间复杂度。实验验证了算法的有效性,以及分布式索引和基于直方图排序技术的高效性。其次,本文从顶点为中心的角度出发,提出了顶点驱动的并行MST算法PB,并论证了PB算法的正确性。另外,本文给出了PB算法的终止条件和索引维护策略。随后,分别列出了基于MapReduce和BSP框架的PB算法的整体执行过程,其中包括启动作业和循环作业的详细处理流程。同时,本文分别针对上述框架剖析了PB算法的时间复杂度。实验证明了PB算法的有效性、高效性和可扩展性。最后,针对图的动态性特征,本文定义了动态图的五种操作并提出了MST结果的分布式动态维护算法MTBM。同时,本文给出了二次划分和分布式MST构建等预处理算法。在预处理之后,分别针对插入、删除和修改等操作,设计了相应的维护策略,并分析了MTBM算法执行代价。实验证明了MTBM算法的可靠性和高效性。总之,本文从大规模图角度出发,针对MST问题展开一系列研究,分别提出了边驱动和顶点驱动的并行MST算法以及MST结果的分布式动态维护算法。本文的研究工作,即大规模图的MST结构,为其他复杂的查询处理和数据挖掘算法提供了应用基础。