[LintCode 629: Minimum Spanning Tree - Summary

https://shmilyaw-hotmail-com.iteye.com/blog/2010747

Prim算法

    Prim算法的基本思路如下，首先选择任意一个节点作为一个单节点的树。它就相当于是一棵树的根或者发起点。然后我们从这个节点开始，看它关联的所有边。每次我们选择一个边的时候，挑选一个权值最小的而且不在这个树的节点集合里的。因为如果我们增加一个边的时候，同时就把这个边所关联的另外一个节点加入到前面的树的节点集合里来了。

    我们以如下的图来说明Prim算法的过程，首先，我们在图里选择节点a：

    节点a是我们考虑的起始节点，按照算法的描述我们就要通过它来选择边，扩展整个树。a的边有两个分别关联到b和h，它们的权值分别为4和8。那么这时我们选择权值最小的边4, 这个边关联的节点b不在我们原来的树节点集合里。将这个边和关联的节点加入到树中间，这样我们树的集合里节点为{a, b}。如下图：

    这个时候，我们要考虑和扩展的边就不仅仅是原来节点a的边了，也要考虑节点b的。从图中可以看到权值最小的边为bc, ah，它们的值都为8。因为c和h都不在树的节点集合里，所以它们都可以选取。假定我们选取bc。那么节点集合为{a, b, c}，其结构如下图：

    总结起来，Prim算法无非就是首先找到一个节点，然后选择它关联的节点中权值最小的边，并将对应的节点也加入集合。然后将新加入的节点的边也加入到边选择考察的范围。这样重复前面的扩展过程，导致节点和边的队伍不断扩充壮大。

    现在，从实现的角度来考虑，我们需要注意几个细节。一个就是，我们要考察的边必须放在某个地方保存起来，它们必然是我们的树节点集合里关联的边。这样每次我们能很方便的去选取它们最小的那个。另外一个就是，我们每次选择到一个边的时候还是需要判断这个新加入的点是否已经在树节点的集合里了，如果已经在了就不能加这个边和节点。这两个问题，我们分别实现的思路如下。因为每次我们需要加入边，并且要选择最小的出来，我们不一定要对它们所有的进行排序，最有效的办法是采用一个最小堆。实际代码中可以使用PriorityQueue。而至于判断是否重复访问节点，我们可以定义一个和节点对应的boolean数组，每次访问到对应的节点时就将该数组里对应的元素值设置为true。

    这里稍微截取了一部分代码。最关键的代码在prim()方法和visit()方法里。我们定义了pq来每次visit一个节点的时候将关联的边加入到其中。在加入之前我们只需要判断一下这个要访问的节点是否已经访问过。而prim方法里每次通过pq.remove()方法取出权值最小的边。这些选取出来的边，至少有一个节点已经在树的节点集合里面了，所以我们之需要判断一下关联的节点里有一个不在，我们就可以去访问该节点。

1. public class LazyPrimMST {  
2.     private double weight;  
3.     private Queue<Edge> mst;  
4.     private boolean[] marked;  
5.     private Queue<Edge> pq;  
6.   
7.     public LazyPrimMST(EdgeWeightedGraph g) {  
8.         mst = new LinkedList<Edge>();  
9.         pq = new PriorityQueue<Edge>();  
10.         marked = new boolean[g.getVertices()];  
11.         prim(g, 0);  
12.     }  
13.   
14.     private void prim(EdgeWeightedGraph g, int s) {  
15.         visit(g, s);  
16.         while(pq.size() > 0) {  
17.             Edge e = pq.remove();  
18.             int v = e.either(), w = e.other(v);  
19.             if(marked[v] && marked[w]) continue;  
20.             mst.add(e);  
21.             weight += e.getWeight();  
22.             if(!marked[v]) visit(g, v);  
23.             if(!marked[w]) visit(g, w);  
24.         }  
25.     }  
26.   
27.     private void visit(EdgeWeightedGraph g, int v) {  
28.         marked[v] = true;  
29.         for(Edge e : g.adj(v))  
30.             if(!marked[e.other(v)])  
31.                 pq.add(e);  
32.     }  

Kruskal算法

    Kruskal算法考虑的思路和前面的不同。既然我们要找的Minimum Spanning Tree是要求涵盖所有节点并且权值最小。那么如果我们从权值最小的边这个角度入手呢？如果每次我们都选择权值最小的边，然后再考察它所关联的节点。假定我们图里的每个节点都是一个个独立的集合。它们每个集合就是包含它们本身。而一旦我们选择了一个边，相当于两个集合直接建立了一个关联，或者说将它们给合并了。比如最开始的时候，我们找到第一个边，那么它就将两个独立的节点合并成一个集合。然后我们再去找权值最小的边。当然，并不是每次我们找到的权值最小的边就合适。比如说我们原来已经有几个节点在一棵连通的树里了，我们找到的边如果它的节点都在数的节点集合里就不合适。

    我们结合下面的图来详细的走一下后面的步骤。首先我们从图中权值最小的边，在这里是选择了hg，它的权值为1。

    这里，我们选择的边将h, g关联起来，它们相当于形成了一棵树。然后，我们再选择下一个权值最小的边，这次我们找到了ci, gf，假定我们选择ci，则如下图：

    在这里我们会发现一个有意思的地方。在不断引入最小权值边的时候，我们会引入一组组独立的集合，它们是相互关联的，但是暂时它们和其他的集合又是相互独立的。这时，我们再按照前面的思路挑最小的边，这次选择了gf：

    在构造函数里，我们通过g.edges()将图里面所有的边取出来放到PriorityQueue里，然后不断的从里面取边。while循环的条件在于只要我们能够找到节点个数-1个边或者队列为空就可以了。所以循环里面的代码很简单，每次我们取出边，然后判断两边的节点是否属于同一个集合，是的话则忽略，不是的话则归并它们到同一个集合里。mst则用来保存所有选取出来的边。

1. public class KruskalMST {  
2.     private Queue<Edge> mst;  
3.     private double weight;  
4.   
5.     public KruskalMST(EdgeWeightedGraph g) {  
6.         mst = new LinkedList<Edge>();  
7.         Queue<Edge> pq = new PriorityQueue<Edge>(g.edges());  
8.         UF uf = new UF(g.getVertices());  
9.           
10.         while(pq.size() > 0 && mst.size() < g.getVertices() -1) {  
11.             Edge e = pq.remove();  
12.             int v = e.either(), w = e.other(v);  
13.             if(uf.connected(v, w)) continue;  
14.             uf.union(v, w);  
15.             mst.add(e);  
16.             weight += e.getWeight();  
17.         }  
18.     }  

https://www.hackerearth.com/practice/algorithms/graphs/minimum-spanning-tree/tutorial/