Minimum Spanning Tree

For a weighted undirected graphtwo greedy algorithm
n: number of vertices in the given graph.
1.Prim's algorithm

先随便找一个点当root，从那个点开始找最短的edge到周围的点，这个图的扩展就是找最短的edge，如果不构成环，走之。
data structure: minHeap用来存node，order by 连接这个node的最短长度的边

1) Create a Min Heap of size n. Every node of min heap contains vertex number and key value of the vertex.
2) Initialize Min Heap with first vertex as root (the key value assigned to first vertex is 0). The key value assigned to all other vertices is INF (infinite).
3) While Min Heap is not empty, do following
…..a) Extract the min value node from Min Heap. Let the extracted vertex be u.(这一步保证了最短且不会成环)
…..b) For every adjacent vertex v of u, check if v is in Min Heap (not yet included in MST).indegree[v]--
         If v is in Min Heap and its key value is more than weight of u-v, then update the key value of v as weight of u-v and parent[v] = u;

用一个indegree[] 来count每个点的incoming edges 数目。可以方便的加入minHeap。不用loop through all vertex in heap，也不用在来一个一样的graph structure存income的点
可以用一个parent[] 来装parent of each vertex。在更新min heap 的时候同时更新parent即可。

O(n + nlogn + eloge)

2. Kruskal's algorithm

1. Sort all the edges in non-decreasing order of their weight. O(eloge)=O(elog(n^2))=O(elogn)

2. Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If cycle is not formed, include this edge. Else, discard it.
是否这个edge形成环？-> union-find 数据结构！ 几个 seperate subtree,  来一个edge看edge连的两个端点是不是在一个set里边，如果不在就union它们

3. Repeat step#2 until there are (V-1) edges in the spanning tree.

 class Edge implements Comparable<Edge>{  
   Node n1;  
   Node n2;  
   int length;  
   @Override  
   public int compareTo(Edge e){  
     reutrn Integer.compare(this.length,e.length);  
   }  
 }  
 public Edge[] minimumSpanningTree(HashMap<Node,List<Node>> adjList){  
   //build edges  
   List<Edge> edges = new ArrayList<>();  
   for(Node node: adjList.keySet()){  
     List<Node> list = adjList.get(node);  
     for(Node n2: list){  
       edges.add(new Edge(node,n2));  
     }  
   }  
   int n = adjList.size();  
   Edge result[] = new Edge[n];   
   int i = 0;  
   Collections.sort(edges);  
   int[] edgeIndices = new int[edges.length];  
   for(Edge e: edges){  
     if(connect(e.n1,e.n2,edgeIndices))  
       continue;  
     union(e.n1,e.n2,edgeIndices);  
     result[i++] = e;  
   }  
   return result  
 }