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

逃离我推掉我的手 2022-09-25 06:27 192阅读 0赞

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);
    	}
    
    }