Abstract: This paper uses PAR method to derivate the readable and efficient recursive minimum spanning tree algorithm formally by transforming function specification. This method simplifies the process of algorithmic program’s design and correctness testifying, and effectively improves the automatization, standardization and correctness of algorithmic program’s design. It gives the implementation of the algorithm in automatic program transformation system of PAR platform.

Key words: PAR method, Formal derivation, Specifications transform, Algorithmic programs

摘要： 采用PAR方法通过功能归约变换，形式化推导出可读性好、效率高的递推的最小生成树算法，简化了算法程序设计和正确性证明的过程，有效提高了算法程序设计自动化、规范化的程度及其正确性。该文给出的相关算法在PAR平台通过自动转换系统转换成可执行语言程序并运行通过。

关键词: PAR方法, 形式化推导, 归约变换, 算法程序

CLC Number: 

• TP311