自己就是没有耐心看.....
说说浅显的理解,MST-REDUCE的预处理,对每一个节点u,如果u没有在任何集合中,就找到边E(u,v),其中w(u,v)是最小的,也就是找到与u连接的最短的一条边,把u和v加入到一个集合中,也就是收缩了边u-v,把两个点合并成一个点,这样处理每一个点,最终就形成了新的点集,当然,前面收缩掉的边肯定是在最小生成树中的边,这和kruskal算法是一个思想,只不过MST-REDUCE是得到了新的图,这个图的节点数V' . V'<V/2 .
然后再枚举每一条边,如果这条边是连接两个不同的点的集合的,那么就选择最短的那条边,作为连接这两个点集的边,也就是新的图中,连接收缩成一个点的点集之间的边...废话多了..也就是新的图的边...
说了这么半天,貌似说的是kruskal算法,,,不过有一点区别,就是以上的处理 得到的是新的图.......