[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/

建水井

狗家 建水井
https://www.1point3acres.com/bbs/thread-505957-1-1.html

第一轮建水井，一个村庄里有很多房子，有的房子旁边能建水井，有的房子只能通过与其他房子建立管道获得供水。给出了在不同房子旁边建水井的花费，已及两个房子间建管道的花费，要求结果给出一份竞价，使得总花费尽可能少 第一题就卡住了，给出了个不算特别好的算法，我又试了别的想法，但是没想出来，面试官问是要个提示还是就之前我给出的完整的算法写，我选择要了提示，面试官根据我第二个思路引导我构成联通图 最后怕时间不够写代码，提醒说用最小生成树-b

这题一周内已经看到两三次了。仔细想了一下，觉得比最小生成树更复杂，因为可以仅仅找多个联通分量，每个联通分量内只需要一个水井，最后代价最小就行，并不是一定要连通图。

感觉不要去考虑连通分量连通图之类的，直接用最小生成树的思路比较好。因为能建水井的房子，相当于有一条管道可以通往水源，管道长度就是建井费用，最后就是要用最小生成树把所有房子+水源都连接起来。

+1 所以事实上就是构建这样一个graph G=<V, E>, V包括了所有的房子+一个虚拟的水源节点，E包括了所有的管道和打井消耗，然后寻找G的MST即可

考虑到了呀。不要去想水井，就想整个村子只有一个水源，然后只有几个房子可以连到水源。最终要所有房子都有水。

你说的这个情况，那个最后的房子会直接连到水源。但无论如何，都是用一颗树把所有房子还有水源都连起来。

写了一个最小生成树的代码，核心思想就是维护一个PriorityQueue，每次poll出来[cost, v1, v2] 其中v1是已访问的节点，如果v2没有访问就加入到已访问节点中，然后把v2的相连的节点加到queue中。时间复杂度：用邻接表 O( VElogE)， 用邻接矩阵是O(VVlogE) 


这是Lazy implementation版的Prim's algorithm
所以是O(E log E)

先建一个dummy，自己家挖水井，当成是这个房子到dummy的一个边，cost就是这个房子自己挖水井的cost，这个时候整个就是一个全连接的图，每个点和其他点都有连接，都有cost，把所有的边加到minheap中，pop cost最小的边，用union find check当前的边可以保留吗？我们的目标是pop出的边能包括所有的房子和dummy，并且没有边（使得房子有重复，会增加cost不是我们想要的） ，每pop一个边，check是不是已经find了？是，不要，不是，留下，一直到这些边包括所有的房子和dummy

Agri-Net - USACO 3.1.1

agri-net - codetrick
Farmer John has been elected mayor of his town! One of his campaign promises was to bring internet connectivity to all farms in the area. He needs your help, of course.
Farmer John ordered a high speed connection for his farm and is going to share his connectivity with the other farmers. To minimize cost, he wants to lay the minimum amount of optical fiber to connect his farm to all the other farms.
Given a list of how much fiber it takes to connect each pair of farms, you must find the minimum amount of fiber needed to connect them all together. Each farm must connect to some other farm such that a packet can flow from any one farm to any other farm.
The distance between any two farms will not exceed 100,000.

PROGRAM NAME: agrinet

INPUT FORMAT

Line 1:	The number of farms, N (3 <= N <= 100).
Line 2..end:	The subsequent lines contain the N x N connectivity matrix, where each element shows the distance from on farm to another. Logically, they are N lines of N space-separated integers. Physically, they are limited in length to 80 characters, so some lines continue onto others. Of course, the diagonal will be 0, since the distance from farm i to itself is not interesting for this problem.

SAMPLE INPUT (file agrinet.in)

4  0 4 9 21  4 0 8 17  9 8 0 16  21 17 16 0  

OUTPUT FORMAT

The single output contains the integer length that is the sum of the minimum length of fiber required to connect the entire set of farms.

SAMPLE OUTPUT (file agrinet.out)

28

X. PriorityQueue Prime
https://github.com/scv119/USACO/blob/master/src/agrinet.java

	static class Node implements Comparable{ int id;
	int value;
	int visit;
	@Override
	public int compareTo(Object o) {
	return this.value - ((Node)o).value;
	}
	}
	static int prim(){
	Node list[] = new Node[N];
	for(int i = 0; i < N; i ++)
	{
	list[i] = new Node();
	list[i].id = i;
	list[i].value = INF;
	}
	list[0].value = 0;
	PriorityQueue<Node> q = new PriorityQueue<Node>();
	for(Node node:list)
	q.add(node);
	int ret = 0;
	while(q.size()>0){
	Node node = q.poll();
	if(node.value == INF)
	break;
	node.visit = 1;
	ret += node.value;
	for(int j = 0 ; j < N ; j ++){
	if(g[node.id][j]<list[j].value && list[j].visit == 0)
	{
	list[j].value = g[node.id][j];
	q.remove(list[j]);
	q.offer(list[j]);
	}
	}
	}
	return ret;
	}

http://qingtangpaomian.iteye.com/blog/1635938
          基本的Prim算法，按照算法实现的步骤来做就可以了。首先将起始点加入最小生成树中，然后遍历每次取最小的边加入，重复n-1次，就可以得到一颗完整的最小生成树。

1.         ArrayList<Integer> now = new ArrayList<Integer>();//在最小生成树当中的节点  
2.         ArrayList<Integer> next = new ArrayList<Integer>();//不在最小生成树中的节点  
3.           
4.         int num = in.nextInt();  
5.         int[][] dist = new int[num][num];  
6.   
7.         for (int i=0;i<num;i++){  
8.             next.add(i);  
9.             for (int j=0;j<num;j++){  
10.                 dist[i][j] = in.nextInt();  
11.                 dist[j][i] = dist[i][j];  
12.             }  
13.         }  
14.           
15.         now.add(0);  
16.         next.remove(new Integer(0));  
17.           
18.         int cnt = 0;  
19.         for(int i=1;i<num;i++){  
20.             int min = Integer.MAX_VALUE;  
21.             int nextNode = -1;  
22.             for (int j=0;j<now.size();j++){  
23.                 for (int k=0;k<next.size();k++){  
24.                     if (dist[now.get(j)][next.get(k)]!=0){   
25.                         if(dist[now.get(j)][next.get(k)]<min){  
26.                             min = dist[now.get(j)][next.get(k)];  
27.                             nextNode = next.get(k);  
28.                         }  
29.                     }  
30.                 }  
31.             }  
32.             cnt = cnt + min;  
33.             now.add(nextNode);  
34.             next.remove(new Integer(nextNode));  
35.         }  

X. Kruskal  http://sdjl.me/index.php/archives/113

    private static void run()
    {
        //根据边的距离排序
        Collections.sort(edges);
        //依次考虑每条边
        Iterator it = edges.iterator();
        while (it.hasNext())
        {
            edge e = (edge)it.next();
            //如果边的两个顶点属于不同的集合
            if (e.u.set != e.v.set)
            {
                //把此边加入最小生成树
                cost += e.w;
                //合并两个集合
                union(e.u.set, e.v.set);
            }
        }
    }

    private static void union(Set s1, Set s2)
    {
        s1.addAll(s2);//把s2集合中的元素加入s1中
        //让s2中的每个顶点指向s1集合
        Iterator it = s2.iterator();
        while (it.hasNext())
        {
            vertex v = (vertex)it.next();
            v.set = s1;
        }
    }

Kruska: http://massivealgorithms.blogspot.com/2014/07/greedy-algorithms-set-2-kruskals.html
Prim: http://massivealgorithms.blogspot.com/2014/07/greedy-algorithms-set-5-prims-minimum.html
Read full article from agri-net - codetrick