图--最小生成树（Prim和Kruskal算法）_prim算法权值相同的边得到的最小生成树的总权值

加权图，每条边关联一个权值的图。

图的生成树是包含其所有顶点的无环连通子图。最小生成树是在加权无向图中权值最小（生成树的所有边的权重加起来最小的）的生成树。

​

一、加权边和加权图

1、加权边        

对于非加权图的实现，并没有创造特定的类作为边，非加权的无向图和有向图对于边的处理都是围绕顶点展开的。但是加权边稍微复杂一点，很难单纯的仅用顶点表示边的权重。因此要用一个Edge类来表示边。Edge类API如下

public class Edge implements Comparable<Edge> {
	private final int either;
	private final int other;
	private final double weight;
	public Edge(int v,int w,double weight)
	{
		this.either = v;
		this.other = w;
		this.weight = weight;
	}
	public int either()
	{
		return either;
	}
	public int other(int v)
	{
		if(either == v) return other;
		else if(other == v) return either;
		else throw new RuntimeException("该条边不包含这个顶点");
	}
	public double weight()
	{return weight;}
	@Override
	public int compareTo(Edge that) {
		// TODO Auto-generated method stub
		if(this.weight == that.weight) return 0;
		else if(this.weight < that.weight) return -1;
		else return 1;
	}
	public String toString()
	{
		return either+" "+other+" "+weight;
	}
	
}

     2、加权图的表示

         图的表示方式有三种：邻接矩阵、边的数组、邻接表数组

        邻接矩阵：使用一个V*V的数组矩阵，如果是布尔矩阵可以用来表示普通无向图，顶点v和顶点w之间有连接则boolean[v][w]为true否则为false。double数组矩阵可以用来表示加权图，首先都初始化为负无穷，而后可以用边的权重作为矩阵元素。

        边的数组：用Edge类的数组来表示图，但是对于实现图的adj(int v)方法(返回所有其中一个顶点是v的边)过于复杂，需要遍历全部边。

        邻接表数组：使用一个以顶点为索引的列表数组（如下图所示），Bag<Item>数组，Bag<Integer>数组表示非加权无向图（图a），Bag<Edge>数组可以用来表示加权数组（图b）。

​

​

    加权图的API和代码实现都是与非加权无向图非常类似的，加权图的API如下：

        下方是加权图的代码实现 

public class EdgeWeightedGraph {
	private int V;
	private int E;
	private Bag<Edge>[] adj;
 
    public EdgeWeightedGraph(int V)    //具体实现见下方
	{...}
    
    public int V()
	{return V;}
	public int E()
	{return E;}
 
    public void addEdge(Edge e)
	{...}
 
    public Iterable<Edge> adj(int v)
	{return adj[v];}
    
    public Iterable<Edge> edges()
	{...}
 
    public String toString()
	{
		String s = "";
		for(int v=0;v<V;v++)
		{
			s+=v+":"+"\n";
			for(Edge e:adj[v])
				s+="  "+e+"\n";
		}
		return s;
	}
}

加权图的构造函数EdgeWeightedGraph(int V)

public EdgeWeightedGraph(int V)
{
    this.V = V;
    this.E = 0;
    adj = (Bag<Edge>[])new Bag[V];
    for(int i=0;i<V;i++)
        adj[i] = new Bag<Edge>();
}

 加权图的addEdge()方法

public void addEdge(Edge e)
	{
		int v = e.either();
		int w = e.other(v);
		adj[v].add(e);
		adj[w].add(e);
		E++;
	}

加权图的edges()方法，该方法在Kruskal算法计算加权图的最小生成树时用得到

public Iterable<Edge> edges()
	{
		Bag<Edge> edges = new Bag<Edge>();
		for(int i=0;i<V;i++)
		{
			for(Edge e:adj[i])
			{
				if(e.other(i)>i)
					edges.add(e);
			}
		}
		return edges;
	}

最小生成树(MST)的API如下 

二、Prim算法计算最小生成树

        在理解Prim算法之前先了解几个概念。切分、横切边、切分定理。

        切分：图的一种切分是将所有顶点分为两个非空并且不重复的两个集合。

        横切边：是一条连接两个属于不同集合的顶点的边。

        切分定理：在一种切分方式中，所有横切边中权重最小的边属于图的最小生成树

         上图就是图的一种切分方式，灰点和白点分别属于两个不同的集合，红色的边就是连接两个集合的横切边。在6条横切边中边e的权重最小，那么该边就一定是最小生成树的一条边。

        也就是说，我们可以不断地变换切分方式，找到横切边中权重最小的边（将其变为黑色），直到找到V-1条黑色边。这V-1条边就可以组成最小生成树。

​

         问题来了，怎么适当的变换切分方式去找到所有V-1条权重最小的横切边呢？                                 这里选择的是一颗“生长”的树作为一个集合，其余的顶点作为一个集合，以此作为切分方式。                                                                                                                                                         如下图所示，先将顶点0加入到树(目前树只有一个顶点)，此时横切边有0-7、0-2、0-4、0-6。权重最小的是边0-7，将此边加入树，同时将顶点7也加入树中。                                                         此时树拥有两个顶点0、7和一条边0-7，然后就以0、7作为一个集合(白色)，其余的顶点为一个集合(黑色)进行切分，这时横切边就有7-1、7-5、7-4、7-2、0-4、0-2、0-6。权重最小的边是7-1，将此边和顶点1加入树中。以此类推，直到所有的顶点都被加入到树中(或者树中的边有7条)。

​

        Prim算法地原理就是这样，它的每一步都会为这颗生长中的最小生成树添加一边。一开始这棵树只有一个顶点，然后会向它添加V-1条边，每次总是将下一条连接树中的顶点与不在树中的顶点且权重最小的边加入树中。

        问题又来了，我们用什么样的数据结构来保存树的顶点、边呢，又用什么样的数据结构保存横切边？

        用布尔数组marked[ ]表示顶点是否在树中，在树中为true，不在树中为false；用一个队列Queue<Edge>来保存树中的边(mst)；用优先队列MinPQ<Edge>来保存横切边(pq)，优先队列不管输入顺序如何总是优先输出最大(MaxPQ)或最小的边(MinPQ)。优先队列与索引优先队列。

​

          再把上面的图拿来用一次，当我们把顶点0加入到树中时，令marked[0] == true,  要得到横切边只需要用加权无向图的adj(0)方法即可返回0-7、0-2、0-4、0-6这四条横切边，将这四条边加入到优先队列(pq)中。pq.delMin()返回权重最小的边0-7，将这条边加入队列(mst)中。

           然后将7加入到树中，令marked[7] == true, 然后用adj(7)方法返回几条边7-1、7-5、7-4、7-2、0-7。我们可以看到边0-7不属于横切边，但是它也被返回了，因此我们需要加一个判断条件（返回的边的另一个顶点是否在树中），忽略掉已经在树中的边。我们可以根据此编写添加一个顶点进入树后的方法visit(int v)。

private void visit(int v,EdgeWeightedGraph G)
{
    marked[v] = true; //顶点入树，标记为true
    for(Edge e:G.adj(v))
    {
        int w = e.other(v);    
        if(!marked[w])        //如果该边的另一个顶点也在树中，跳过该边，否则将该边为横切边，并将其加入优先队列pq中
            pq.insert(e);
    }
}

        事情看起来发展得很好，首先将一个点加入到树中，然后将横切边加入到优先队列pq中，找到权重最小的横切边加入到队列mst中。

• marked[v] = true;
• adj(v)，将符合条件的边pq.insert(e)
• Edge e = pq.delMin()----删除并得到优先队列中的边加入到树中mst.enqueue(e)
• 将刚刚加入到树中的边对应的顶点加入树

所以真的如此吗？我们还拿上面的图举例子

        ​

         如上图所示，当我们将顶点2加入到树中时，使用图的adj(2)方法返回1-2、7-2、0-2、2-6、2-3几条边，只有边2-3、2-6是有效的横切边可以添加到优先队列pq中去，也就是说边1-2、7-2是失效的横切边。但是当顶点1加入到树中时，这两条边已经被加入到优先队列pq中了，而且并没有被及时的删除。

        所以当我们用pq.delMin()得到权重最小的边时，先判断这个边是不是失效的边，然后再决定是否加入到树中。判断的方法很简单，只需要判断这条边的另一个顶点是不是也在树中即可。所以正确的流程应该是如下

• marked[v] = true;
• adj(v)，将符合条件的边pq.insert(e)          前两个步骤被包装到visit()方法里
• Edge e = pq.delMin()----删除并得到优先队列中的边
• 判断得到的权重最小的边是不是失效的边，如果不是则加入到树中mst.enqueue(e)
• 将刚刚加入到树中的边对应的顶点加入树

visit(0,G);        //先将顶点0以及对应的横切边加入到树中
while(!pq.isEmpty())
{
	Edge e = pq.delMin();    //得到权重最小的边
	int v = e.either(),w = e.other(v);
	if(marked[v]&&marked[w]) continue;		//跳过失效的边
	mst.enqueue(e);					//将边添加到树中
	if(marked[v]) visit(w,G);		//将顶点v或w添加到树中
	if(marked[w]) visit(v,G);
}

 Prim算法的完整代码如下

public class LazyPrimMST {
	private boolean[] marked;
	private MinPQ<Edge> pq;
	private Queue<Edge> mst;
	public LazyPrimMST(EdgeWeightedGraph G)
	{
		int V = G.V();
		marked = new boolean[V];
		pq = new MinPQ<Edge>();
		mst = new Queue<Edge>();
		
		visit(0,G);
		while(!pq.isEmpty())
		{
			Edge e = pq.delMin();
			int v = e.either(),w = e.other(v);
			if(marked[v]&&marked[w]) continue;		//跳过失效的边
			mst.enqueue(e);					//将边添加到树中
			if(marked[v]) visit(w,G);		//将顶点v或w添加到树中
			if(marked[w]) visit(v,G);
		}
	}
	private void visit(int v,EdgeWeightedGraph G)
	{
		marked[v] = true;
		for(Edge e:G.adj(v))
			if(!marked[e.other(v)])
				pq.insert(e);
			
	}
	public Iterable<Edge> edges()
	{return mst;}
	public double weight()
	{
		double weight = 0;
		for(Edge e: mst)
			weight+=e.weight();
		return weight;
	}
}

Prim算法的改进

        上述算法命名为LazyPrimMST，因为该算法有可改进的空间。改进方法就是怎样及时删除失效的边，或者选择一个合适的数据结构，只保留有效的横切边。当删除失效边之后，就只剩树顶点和非树顶点之间连接的横切边。

        但其实还可以删除更多，一个非树顶点可能与多个树顶点有横切边，对于这些顶点，我们只需要保留权重最小的那个横切边。比如下图左边那张图，非树顶点4与树连接两条横切边0-4、7-4，我们只需要保留权重最小的边0-4即可，非树顶点2与树连接的横切边也只需保留边0-2即可（下图右图）。

同样用布尔数组marked[ ]表示顶点是否在树中，用大小为V(顶点数)的边的数组edgeTo[ ]保存横切边，同样大小为V的double类型的数组distTo[ ]保存对应边的权重。

edgeTo[ ]数组代表什么，如果是非树顶点代表的是该顶点距离树权重最小的边，如果是树顶点，代表的是一条最小生成树的边。如下图所示，当树只有一个顶点0时，edgeTo[2]的边代表的就是非树顶点2到树顶点0的最小权重边，distTo[2]则代表该边的权重。之后再将有效横切边中权重最小的边加入树，循环往复，直到所有的顶点都加入树就行了。

 我们再来看一幅图

 上图介绍的是树生长的一个大致流程。问题的关键在于，我们怎样在有效横切边里，也就是数组edgeTo[ ]中，怎样快速找到权重最小的横切边。遍历整个数组是最简单的方法，但是每次添加一条边到树中都要遍历整个数组，这样的话所需时间就是平方级别的，所以遍历数组不是可取的方法。

这里使用索引优先队列(IndexMinPQ<Double>)pq（优先队列与索引优先队列），在将有效横切边及其权值放入数组edgeTo[ ]和distTo[ ]的同时，把对应的索引及其权值插入索引优先队列pq。

然后使用pq.delMin()就可得到权重最小横切边的索引，该索引就是下一个要加入树的顶点。

        现在总结一下，需要的数据结构有布尔数组marked[ ]，有效横切边数组edgeTo[ ]，权重double数组distTo[ ]，索引优先队列pq;

private boolean[] marked;
private Edge[] edgeTo;
private double[] distTo;
private IndexMinPQ<Edge> pq;

首先是往树中加入一个顶点0，即访问顶点0，visit(0)， visit方法详细代码如下。

vist(0,G);
pq.insert(0,0.0)
 
private void visit(int v,EdgeWeightedGraph G)
{
    marked[v] = 0;
    for(Edge e:G.adj(v))
    {
        int w = e.other(v);
        if(marked[w]) continue;        //先判断e是否为横切边
        if(e.weight<distTo[w])        //再判断e是否比原横切边的权重更小，也就是判断其是否为有效横切边
        {
            distTo[w] = e.weight;
            edgeTo[w] = e;
            if(pq.contains(w)) pq.change(w,distTo[w]);    //在更改数组edgeTo和distTo的同时，别忘记更改索引优先队列pq
            else pq.insert(w,distTo[w]);
        }
    }
}

在访问顶点0之后，pq中就有了四个索引及其对应的权值，数组edgeTo和distTo也有了四个有效值。然后就可以通过pq.delMin()得到索引7，7就是下一个要加入树的顶点。

vist(0,G);
pq.insert(0,0.0)
 
while(!pq.isEmpty)
{
    visit(pq.deMin(),G);
}

 Prim改进后算法完整代码如下

public class PrimMST {
	private Edge[] edgeTo;	//距离
	private double[] distTo;
	private boolean[] marked;
	private IndexMinPQ<Double> pq;
	public PrimMST(EdgeWeightedGraph G)
	{
		edgeTo = new Edge[G.V()];
		distTo = new double[G.V()];
		marked = new boolean[G.V()];
		pq = new IndexMinPQ<Double>(G.V());
		for(int v=0;v<G.V();v++)
			distTo[v] = Double.POSITIVE_INFINITY;	//初始化时无限大
		distTo[0] = 0;
		pq.insert(0, 0.0);
		while(!pq.isEmpty())
		{
			visit(pq.delMin(),G);
		}
	}
	@SuppressWarnings("deprecation")
	private void visit(int v,EdgeWeightedGraph G)
	{
		marked[v] = true;
		for(Edge e:G.adj(v))
		{
			int w = e.other(v);
			if(marked[w]) continue;
			if(e.weight() < distTo[w])
			{
				edgeTo[w] = e;
				distTo[w] = e.weight();
				if(pq.contains(w)) pq.change(w,distTo[w]);
				else pq.insert(w, distTo[w]);
			}
		}
	}
	public Iterable<Edge> edges()
	{
		Queue<Edge> mst = new Queue<Edge>();
		for(Edge e:edgeTo)
		{
			mst.enqueue(e);
		}
		return mst;	
	}
	public double weight()
	{
		double all = 0.0;
		for(double b:distTo)
		{
			all+=b;
		}
		return all;
	}
}

二、Kruskal算法

        该算法原理很简单，我们将图中所有的边按照权重从小到大排序，按照这个顺序，一条一条的将边加入到生成树中，如果加入某个边形成环了，则跳过该边添加下一条边，直到生成树中有V-1条边为止。

 这个问题的关键是怎样判断加入一条边之后，是否形成环。这里用到并查集-union-find算法和优先队列，理解该算法必须先了解union-find算法。

 最小生成树在“生长”过程中，每添加一条边就相当于连接两个分量，如果在添加这条边之前两个顶点已经在同一个分量中了，那么添加这条边一定会产生环。

public class KruskalMST {
	private Queue<Edge> mst;
	@SuppressWarnings("deprecation")
	public KruskalMST(EdgeWeightedGraph G)
	{
		UF uf = new UF(G.V());
		MinPQ<Edge> edges = new MinPQ<Edge>();
		mst = new Queue<Edge>();
		for(Edge e:G.edges())
			edges.insert(e);
		while(mst.size()<G.V()-1)
		{
			Edge e = edges.delMin();
			int v = e.either(),w = e.other(v);
			if(uf.connected(v, w)) continue;
			uf.union(v, w);
			mst.enqueue(e);
		}
		
	}
	public Iterable<Edge> mst()
	{ return mst;}
	public double weight()
	{ 
		double weight = 0;
		for(Edge e: mst)
		weight+=e.weight();
		return weight;
	}
}