近年来随着聚类算法应用领域的扩大,可处理的数据类型日趋丰富,基于图论的聚类方法引起越来越多的关注,新的和改进的算法不断被提出。但是,新的应用需求层出不穷、不断变化,且现有的方法也存在不足,因此要对现有方法进行改进,提出新的理论和方法以满足新应用的需求。本文通过对基于最小生成树(Minimum Spanning Tree,MST)的聚类算法的研究分析,发现该算法在执行的过程中利用贪心算法生成MST,算法的判定过程较复杂,存在大量的冗余信息。当数据量较大时,算法运行所需时间较长,算法在时间性能上是低效的。此外,噪声数据对算法效果的影响较大。这些缺陷在一定程度上限制了算法的应用。针对上述问题,本研究结合网格技术和粗糙集理论提出了一种基于MST聚类的快速算法。该算法在基于MST的聚类中引入网格的概念,根据粗糙集理论给出网格的下确界和上确界,创建边界可扩展的粗糙网格。接着,将每个网格单元作为执行MST生成算法的独立单元,构造每个网格的MST。结合高斯分布特征规律,依据得到的MST边长分布特征删除噪声网格,根据本研究中给出的合并定理合并近邻网格进行聚类。本文提出的算法可以视为一个算法框架,各种生成MST的算法(如,最常用的Kruskal算法和Prim算法)都可以与其结合以减少运行时间。实验结果表明,本文提出的算法计算效率较高,且准确率接近传统的基于MST的聚类算法,算法在大规模数据集的应用中性能良好。