反向删除算法：从包含所有边的图形开始。然后按重量递减的顺序反复穿过边缘。对于每个边，检查删除该边是否会断开图形的连接；如果没有，请删除它。
如何证明该算法可以计算出MST？
jyc2410 回答：MST：反向删除算法
证明：首先，我们证明该算法产生了一个生成树。这是因为在开始时给定图是连接的，并且以不递增的顺序删除边时，仅删除任何循环中最昂贵的边，这确实消除了循环，但没有断开图的连接，导致连接的图不包含任何图。循环结束。为了表明所获得的生成树是MST，请考虑该算法去除的任何边缘。可以看出，它必须位于某个循环上（否则将其删除会断开图形连接），并且它必须是最昂贵的一个（否则保留它会违反循环属性）。因此，“反向删除”算法会产生MST。
王小春王夏利威尔克斯，D。米切尔。一种分治法，用于最小的基于生成树的聚类。 IEEE知识和数据工程学报，2009，21.7：945-958。