Minimum Spanning Tree

MST

1. MST
	1. Given a connected graph, MST is a subgraph with no cycles, that is both a tree and including all vertices (V-1 edges)
	2. Brute-force: try all possible MSTs to find minimum weighted tree
2. Greedy Algorithms
	1. Assumption: distinct edge weights and connected, MST exists and unique
	2. Cut: a partition of vertices into two nonempty sets
	3. Crossing edge: connect a vertex in one set with a vertex in the other
	4. Given any cut, the crossing edges of min weights is in the MST
	5. Algorithm
		1. Start with all edges colored grey
		2. Find cut with no black crossing edges: color its min-weight edge black
		3. repeat until V-1 edges colored black
	6. General algorithm
	7. Need Efficient implementations
	8. remove assumptions: if not distinct (multiple MSTs), if not connected (find MSTs in each components)
3. Kruskal’s algorithm
	1. Sort edge weight ascending order
	2. Add next edge to tree T unless it create a cycle
	3. Kruskal’s algorithm is a special case of the greedy MST algorithms
	4. Union-find structure (find cycle) logV
	5. Worst case O(ElogE)
	6. Build PriorityQueue (E), delete-min E(logE), unionV(logV), connected E(logV)
4. Prim’s Algorithm
	1. Start with vertex 0 and greedily grow tree T
	2. Add to T the min weight edge with exactly one endpoint in T 
	3. Repeat until V-1 edges
	4. A special case of the greedy MST algorithm
	5. min-weight edge logE (priority Queue)
	6. lazy solution: maintain a PQ of edges with one endpoint in T (add in PQ the edges incident to T)
		1. key= edge, priority = weight of edge
		2. delete next edge to add to T
		3. discard if both enpoints are in T
		4. otherwirse, add to PQ any edge incident to w and add w to T
		5. ElogE ad extra space E in worst case
	7. Eager solution: maintain a PQ of vertices connected by an edge to T (only add shortest weight edge to PQ)
		1. delete min vertex add its associated edge
		2. update PQ to add to PQ if not already on it, decrease priority of x if v->x becomes shortest edge connecting x to T 
		3. ElogV (binary heap) extra space V
		4. E+VlogV (Fibonacci heap)
5. Context
	1. No idea if linear-time MST algorithm exists
	2. Euclidean MST ~cNlogN
	3. k-Clustering
	4. single-link clustering