加权无向图的最小生成树的Vyssotsky算法

Vyssotsky算法的基本思想：每次将一条边添加到假设的最小生成树中，如果形成环则删除环中权重最大的边，与Prim算法和Kruskal算法比耗时，加入一条边时要判断是否

形成环，形成环了要做出相应的处理

下面的代码是我根据这个算法的基本思想自己写的，实现了要求，仅供参考

首先几个需要用到的类：

Edge：加权边的数据结构

https://github.com/xiaoyuzdy/Algorithms/blob/master/Algorithms/src/Number_4_02/Edge.java

EdgeWeightedGraph：加权无向图的数据结构，其中添加删除边的方法

https://github.com/xiaoyuzdy/Algorithms/blob/master/AlgorithmsTest2/src/Num2_4_03/EdgeWeightedGraph.java

Cycle：检测加权无向图是否含环，实现一个返回环的方法

https://github.com/xiaoyuzdy/Algorithms/blob/master/AlgorithmsTest2/src/Num2_4_03/Cycle.java

MaxPQ:最大优先队列，可用TreeSet代替，满足返回最大权重的边即可

下面是Vyssotsky算法的代码：

package Num2_4_03;

import java.util.HashSet;
import java.util.Set;
import edu.princeton.cs.algs4.Edge;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.MaxPQ;

/**
 * P410 T23 删除的是形成环中的权重最大的边 
 * 修改Cycle类，实现检测加权无向图的环检测，
 * 修改无向加权边的数据结构实现可以删除指定边
 * 
 * @author he
 * args[0]:tinyEWG.txt
 *   测试通过
 *
 */
class Vyssotsky {
 private MaxPQ<Edge> pq;
 private Cycle cycle;
 private Set<Edge> set;// 保存最小生成树
 private EdgeWeightedGraph G2;

 public Vyssotsky(EdgeWeightedGraph G) {
  pq = new MaxPQ<Edge>();
  G2 = new EdgeWeightedGraph(G.V());
  set = new HashSet<Edge>();
  for (Edge e : G.edges()) {
   G2.addEdge(e);
   cycle = new Cycle(G2);//每添加一条边就检测一次
   set.add(e);
   if (cycle.hasCycle()) {//如果形成环将环中最大的加权边删除
    pq = new MaxPQ<Edge>();
    for (Edge t : cycle.path()) {
     pq.insert(t);
    }
    set.remove(pq.max());// 将形成环的加权边从最小生成树中删除
    G2.delEdge(pq.max());// 无权有向图中移除要删除的边
   }
  }
 }

 public Iterable<Edge> edges() {
  return set;
 }

}

public class Num_4_03_23 {
 public static void main(String[] args) {
  EdgeWeightedGraph G = new EdgeWeightedGraph(new In(args[0]));
  Vyssotsky v = new Vyssotsky(G);
  for (Edge e : v.edges())
   System.out.println(e);
 }

}