最小生成树
加权无向图的最小生成树
1.加权边API
//加权边API
public class Edge implements Comparable<Edge>{
private final int v; //边的一个顶点
private final int w; //边的另一个顶点
private final double weight; //边的权重
public Edge(int v,int w,double weight) {
this.v = v;
this.w = w;
this.weight = weight;
}
public double weight(){ return weight; }
public int either(){ return v; } //获取其中一个顶点
public int other(int vertex){ //获取另一个顶点
if(vertex == v) return w;
else if(vertex == w) return v;
else throw new RuntimeException("不包含顶点"+v);
} //方便遍历所有边
public int compareTo(Edge that) { //可比较
if(weight-that.weight < 0) return -1;
else if(weight-that.weight > 0) return 1;
else return 0;
}
public String toString() { //字符串表示
return v + "-" + w +" " + weight;
}
}2.加权无向图API
//加权无向图API
public class EdgeWeightedGraph {
private int v; //顶点数
private int e; //边数
private LinkedList<Edge>[] adj; //邻接表
public EdgeWeightedGraph(int v) { //创建一副含有v个顶点的空图
this.v = v;
e = 0;
adj = new LinkedList[v];
for(int i=0;i<v;++i)
adj[i] = new LinkedList<>();
}
public EdgeWeightedGraph(InputStream input) { //从输入流中读取一幅图
BufferedReader reader = new BufferedReader(new InputStreamReader(input));
String value = null;
try {
int v = Integer.parseInt(reader.readLine());
this.v = v;
adj = (LinkedList<Edge>[]) new LinkedList[v];
for(int i = 0 ; i < v;i++)
adj[i] = new LinkedList<>();
int e = Integer.parseInt(reader.readLine());
for(int i=0; i<e; i++){
String[] str = reader.readLine().split(" +");
addEdge(new Edge(Integer.parseInt(str[0]),Integer.parseInt(str[1]),Double.parseDouble(str[2])));
}
} catch (IOException e1) {
e1.printStackTrace();
} finally {
try {
reader.close();
} catch (IOException e1) {
e1.printStackTrace();
}
}
}
//顶点数
public int V(){ return v; }
//边数
public int E(){ return e; }
//向图中添加一条边e
public void addEdge(Edge e){
adj[e.either()].add(e);
adj[e.other(e.either())].add(e);
this.e++;
}
//和v相连的所有边
public Iterable<Edge> adj(int v){ return adj[v]; }
//图的所有边
public Iterable<Edge> edges(){
ArrayDeque<Edge> queue = new ArrayDeque<>();
for(int i=0;i<v;++i) //按照顶点从小到大顺序遍历
for(Edge e : adj[i])
if(e.other(i) > i) queue.offer(e); //大顶点-小顶点的边肯定在之前被遍历过
return queue;
}
//图的字符串表示
public String toString() {
String s = V() + "vertices, " + E() + " edges\n";
for(int v = 0;v < V();v++){
s += v + ": ";
for(Edge e : adj(v))
s += e.toString() + " ";
s += "\n";
}
return s;
}
}3.Prim算法延时版本(最小生成树)
/**
* 最小生成树的Prim延时算法
* (假设为连通图,非连通时取每个连通分量的最小生成树合并为森林即可)
* 概述: 将图所有顶点分为两个非空且不重复的两个集合,横切边是连接两个属于不同集合的边,
* 而连接这两个集合的所有横切边中最小边必然属于最小生成树
* 实现: 以任意一个顶点开始,作为最小生成树的初始阶段,将图分为2部分(一个顶点为一部分(最小生成树起始阶段),剩余顶点为一部分)
* 获取连接这两个集合的所有横切边的最小者,加入最小生成树中,此时最小生成树的2个顶点和其余顶点作为图的两部分,
* 重复上面的步骤继续取横切边中最小的边加入最小生成树,直到得到v-1条边为止
*/
public class LazyPrimMST {
private boolean[] marked; //标记是否已加入到最小生成树中
private Queue<Edge> mst; //维护最小生成树的边
private PriorityQueue<Edge> pq; //使用优先队列保存横切边(包含失效的),每次可取出最小的横切边
private double weight;
public LazyPrimMST(EdgeWeightedGraph g) {
marked = new boolean[g.V()];
mst = new ArrayDeque<>();
pq = new PriorityQueue<>();
visit(g,0); //假设g连通
while(!pq.isEmpty()){
Edge e = pq.poll(); //取出最小的横切边
int v = e.either(), w = e.other(v); //横切边的两个顶点v-w
if(marked[v] && marked[w]) continue; //顶点都在树中,失效的横切边跳过
mst.offer(e); //有效的最小横切边加入最小生成树中
weight += e.weight(); //更新总权重
if(marked[v]) visit(g,w); //将刚加入的顶点加入树中,并遍历相连的边
if(marked[w]) visit(g,v);
}
}
private void visit(EdgeWeightedGraph g,int v){
marked[v] = true; //标记顶点V已经加入树中
for(Edge e : g.adj(v)) //遍历新加入顶点相连的所有边
if(!marked[e.other(v)]) pq.offer(e); //将加入顶点后新增加的横切边加入优先队列
/**
* 可在此进行优化,只加入有效的横切边,变成及时Prim算法
*/
}
//最小生成树所有边
public Iterable<Edge> edges(){ return mst; }
//最小生成树的权重
public double weight(){ return weight; }
}4.Prim算法及时版本(最小生成树)
/**
* Prim算法及时版本(最小生成树)
* 概述: 只需对延时版本的Prim算法稍作更改即可,只将有效的横切边加入优先队列
* 此处使用索引优先队列,索引为顶点,按权重(到达顶点的边的权重)构造优先队列
* 生成的索引优先队列可获取最小权重的顶点,还可以取出指定顶点的权重
* 索引优先队列api在以前博客记录
*/
public class PrimMST {
private boolean[] marked; //标记是否已加入最小生成树
private Edge[] edgeTo; //索引为顶点,值为到达该顶点的边,最后保存了最小生成树的边
private IndexMaxPQ<Double> pq; //索引优先队列(见堆排序)维护有效的横切边
public PrimMST(EdgeWeightedGraph g) {
marked = new boolean[g.V()];
edgeTo = new Edge[g.V()];
pq = new IndexMaxPQ<>(g.V(),(x,y) -> -x.compareTo(y));
pq.insert(0,0.0); //起始顶点
while(!pq.isEmpty())
visit(g,pq.delMax());
}
private void visit(EdgeWeightedGraph g,int v){
marked[v] = true;
for(Edge e : g.adj(v)){
int w = e.other(v);
if(marked[w]) continue; //如果另一个顶点已经加入最小生成树,则跳过
if(!pq.contains(w)) pq.insert(w,e.weight()); //与新顶点构成的横切边,直接加入
else if(pq.peek(w) < e.weight()) continue; //无效横切边跳过:以前记录的到达w顶点的横切边权重更小
else pq.change(w,e.weight()); //新的横切边权重更小,更新权重
edgeTo[w] = e; //执行到此为有效横切边,加入或者替换
}
}
//最小生成树的边
public Iterable<Edge> edges(){ return Arrays.stream(edgeTo).skip(1).collect(Collectors.toList()); }
//最小生成树的权重
public double weight(){ return Arrays.stream(edgeTo).skip(1).mapToDouble(x -> x.weight()).sum(); }
}5.Kruskal算法(最小生成树)
/**
* Kruskal算法
* 概述: 将所有边按照边的权重加入优先队列,每次取出一个最小的边,该边不会与已经加入的边构成环,
* 则加入最小生成树,直到含有v-1条边为止
* 实现: 使用union-find数据结构维护顶点的连通性,可以判断两个顶点是否连通,
* 如果在加入一条边时,此边的两个顶点已经连通, 则会构成环,此时为无效边
*/
public class KruskalMST {
private Queue<Edge> mst; //维护最小生成树的边
private double weight; //维护权重
public KruskalMST(EdgeWeightedGraph g) {
mst = new ArrayDeque<>();
PriorityQueue<Edge> minPQ = new PriorityQueue<>();
g.edges().forEach(minPQ::offer); //将所有边按照边的权重加入优先队列
WeightedQuickUnion un = new WeightedQuickUnion(g.V());//union-find(见union-find算法)
while(!minPQ.isEmpty() && mst.size() < g.V()-1){ //v-1条边为止
Edge e = minPQ.poll(); //取出最小边
int v = e.either(),w = e.other(v);
if(un.connected(v,w)) continue; //跳过无效边: v与w已经连通,此时再加入该边会构成环
un.union(v,w); //加入新的边,更新连通性
mst.offer(e); //加入新边
weight += e.weight(); //更新总权重
}
}
//最小生成树的所有边
public Iterable<Edge> edges(){ return mst; }
//最小生成树的权重
public double weight(){ return weight; }
}