算法描述
lazy普利姆算法的步骤：
1.从源点s出发，遍历它的邻接表s.Adj，将所有邻接的边（crossing edges）加入优先队列Q；
2.从Q出队最轻边，将此边加入MST.
3.考察此边的两个端点，对两个端点重复第1步.
示例
从顶点0开始，遍历它的邻接表：边0-7、0-2、0-4、0-6会被加入优先队列Q.
顶点0的邻接表搜索完毕后，边0-7是最轻边，所以它会出队，并加入MST.
如下图：
边0-7出队后，开始考察边的两个端点：
顶点0已经访问过了，跳过；
顶点7还未探索，开始探索顶点7.对7的邻接表进行访问和第一步类似.
我们找到最轻边7-1并加入MST
如下图：
对每条边重复，当所有边都考察完毕，我们就得到了最小生成树,如下图：
时间复杂度
扫描所有边会耗时O(E ).
由于所有的边都会入队,优先队列调整的操作耗时O(logE ).
那lazy方式最差就是O(ElogE ).
其中E 是图的边数.
算法实现
算法的第一步，将源点s所有的邻接的边加入Q，如下：
/**
* 找出从源点出发的所有的crossing edges，并用一个优先队列维护他们
*
* 原理：
* 将对未访问的邻接点进行遍历当作一次切断（graph-cut），则源点和邻接点间的边就是crossing edge
* 根据贪心策略求MST的要求，要加入的边必须是最轻边（权重最小的边），
* 故而将crossing edges加入优先队列，这样便可用O(logN)的时间找出最小权重边
*
* @param src 源点
*/
private void search(int src) {
visited[src] = true;
for(Edge e : g.vertices()[src].Adj) {
WeightedEdge we = (WeightedEdge)e;
if(!visited[we.to])
crossingEdges.offer(we);
}
}算法的第二步和第三步如下：
/**
* lazy普利姆算法中，从一个源点出发
* 1：通过对源点的所有邻接点进行遍历的方式找出所有crossing edges
* 2：将crossing edges中最轻的（拥有最小的权重）边加入MST
* 3：将最轻边的另一个顶点作为源点，重复1-2步.
*
*
* @param src 源点
*/
private void mst(int src) {
search(src);
while (!crossingEdges.isEmpty()) {
WeightedEdge we = crossingEdges.poll();
//懒惰方式处理不再候选的边
if(visited[we.src] && visited[we.to])
continue;
//加入最小生成树
mst.offer(we);
//累积mst的权重
mstWeight += we.weight;
//向src的邻接点方向搜索
if(!visited[we.src])
search(we.src);
//向to的邻接点方向搜索
if(!visited[we.to])
search(we.to);
}
}其中，维护所有crossing edge的，是一个优先队列：
/**
* 优先队列，用于维护crossing edges
* 高效返回最轻边
*/
protected PriorityQueue<WeightedEdge> crossingEdges;带权边的定义很简单，像下面这样：
import java.util.Comparator;
/**
* Created by 浩然 on 4/19/15.
* 带权边
*/
public class WeightedEdge extends Edge implements Comparable<WeightedEdge> {
/**
* 边的权重
*/
public Double weight;
/**
* 边的源点
*/
public int src;
/**
* 构造一条带权边
*@param src 源点
* @param other 目标点
* @param weight 权重
*/
public WeightedEdge(int src,int other, Double weight) {
super(other);
this.src = src;
this.weight = weight;
}
/**
* 比较两条边的大小,这里作升序
* @param to 被比较边
* @return 如果权重比被比较的边小则返回-1，如果大于则返回1，相等则返回0
*/
@Override
public int compareTo(WeightedEdge to) {
if(this.weight < to.weight)
return -1;
else if(this.weight > to.weight)
return 1;
return 0;
}
}
public class Edge {
public int to;
public Edge(int key) {
this.to = key;
}
}而顶点的定义更简单，如下：
public class Vertex {
/**
* 邻接表
*/
public LinkedList<Edge> Adj;
}完整代码
public class LazyPrim extends Algorithm {
/**
* 优先队列，用于维护crossing edges
* 高效返回最轻边
*/
protected PriorityQueue<WeightedEdge> crossingEdges;
public LazyPrim(WeightedUndirectedGraph g) {
super(g);
}
/**
* lazy普利姆算法求MST或MSF（Minimum Spanning Forest最小生成森林）
*
* 算法复杂度：最差O(ElogE)
*/
public void performMST() {
resetMemo();
//对图中的所有顶点进行遍历，找出MST或MSF
for(int i = 0; i < g.vertexCount();i++){
if(!visited[i]) {
mst(i);
}
}
}
/**
* lazy普利姆算法中，从一个源点出发
* 1：通过对源点的所有邻接点进行遍历的方式找出所有crossing edges
* 2：将crossing edges中最轻的（拥有最小的权重）边加入MST
* 3：将最轻边的另一个顶点作为源点，重复1-2步.
*
*
* @param src 源点
*/
private void mst(int src) {
search(src);
while (!crossingEdges.isEmpty()) {
WeightedEdge we = crossingEdges.poll();
//懒惰方式处理不再候选的边
if(visited[we.src] && visited[we.to])
continue;
//加入最小生成树
mst.offer(we);
//累积mst的权重
mstWeight += we.weight;
//向src的邻接点方向搜索
if(!visited[we.src])
search(we.src);
//向to的邻接点方向搜索
if(!visited[we.to])
search(we.to);
}
}
/**
* 找出从源点出发的所有的crossing edges，并用一个优先队列维护他们
*
* 原理：
* 将对未访问的邻接点进行遍历当作一次切断（graph-cut），则源点和邻接点间的边就是crossing edge
* 根据贪心策略求MST的要求，要加入的边必须是最轻边（权重最小的边），
* 故而将crossing edges加入优先队列，这样便可用O(logN)的时间找出最小权重边
*
* @param src 源点
*/
private void search(int src) {
visited[src] = true;
for(Edge e : g.vertices()[src].Adj) {
WeightedEdge we = (WeightedEdge)e;
if(!visited[we.to])
crossingEdges.offer(we);
}
}
@Override
protected void resetMemo() {
super.resetMemo();
//重置优先队列
crossingEdges = new PriorityQueue<>();
}
}