最小生成树问题
1、针对带权无向图
2、针对连通图
最小生成树问题就是找到V-1条边连接V个顶点且总权值最小
切分定理
算法需要用到切分定理，切分即把图中的顶点分成两部分。若一条边的两个端点分别属于切分后的不同的两部分，则称这条边为横切边。切分定理：给定任意切分，横切边中权值最小的边必定属于这个最小生成树。所以我们可以从一个点开始扩散慢慢求出最小生成树。看下图示例:
LazyPrim算法实现最小生成树(带权值)
这里我求的是稠密图的最小生成树
public class LazyPrimMST {
private DenseGraph dg;
private MinHeap mp;
private boolean[] marked; //节点是否被标记(被标记的即被切分到另一部分)
private ArrayList<Edge> mst=new ArrayList<Edge>(); //存储最小生成树
private int mstWeight; //最小的权值和
public LazyPrimMST(DenseGraph dg) {
this.dg = dg;
this.mp =new MinHeap(dg.E()); //以图的边数初始化
this.marked=new boolean[dg.V()];
for(int i=0;i<dg.V();i++)
marked[i]=false;
mst.clear();
visit(0);
while(!mp.isEmpty()){
Edge e=mp.extractMin();
if(marked[e.v()]==marked[e.w()]){ //若不是横切边，则跳过
continue;
}
mst.add(e);
if(!marked[e.v()]){
visit(e.v());
}else{
visit(e.w());
}
}
mstWeight=mst.get(0).wt();
for(int i=1;i<mst.size();i++){
mstWeight+=mst.get(i).wt();
}
}
private void visit(int v){
assert(!marked[v]);
marked[v]=true;
ArrayList<Edge> g=dg.getGraph(v);
Iterator<Edge> ite=g.iterator();
while(ite.hasNext()){
Edge ed=ite.next();
if(!marked[ed.other(v)]){
mp.insert(ed); //这条边成为横切边,将这条横切边插入最小堆
}
}
}
public ArrayList<Edge> mstEdges(){
return mst;
}
public int result(){
return mstWeight;
}
public static void main(String[] args) {
int N=20; //顶点
int M=200; //边
DenseGraph sg=new DenseGraph(N,false);
for(int i=0;i<M;i++){
sg.addEdge(new Random().nextInt(N), new Random().nextInt(N),new Random().nextInt(100)+1);//权值[1,101)
}
LazyPrimMST la=new LazyPrimMST(sg);
System.out.println("最小生成树为");
ArrayList<Edge> arr=la.mstEdges();
for(int i=0;i<arr.size();i++){
System.out.println("{"+arr.get(i).v()+"-"+arr.get(i).w()+",wt:"+arr.get(i).wt()+"}");
}
System.out.println();
System.out.println("最小权值和为"+la.result());
}
}
结果图:
