提出了一种基于近邻传播的半监督聚类算法的并行算法PSAP，给出了约束的转换过程并结合实例进行说明。在UCI数据集上的实验表明：PSAP算法的运行时间约为SAP算法运行时间的1/8~1/4，聚类结果同时有提高。