kruskal's algorithm

Work in Progress

Summary

Kruskal’s algorithm

greedy
constructive, join smaller trees

Time complexity

sort edges:
check all edges:
average case:

Invariant

at the kth iteration, there will be a minimum spanning forest of k edges

Concept

Algorithm

sort edges by weight
choose edges starting with lowest weight
use UFDS to track subtrees
avoid choosing edges that result in cycles

java

List<int[]> EL; // e = [ u, v, w ]

int kruskal() {
	Collections.sort(EL, Comparator.<int[]>comparingInt(x -> x[2]).thenComparingInt(x -> x[0]).thenComparingInt(x -> x[1])); // sort edges -> O(E log E) = O(E log V)
	
	int mst_cost = 0, num_taken = 0;
	UnionFind UF = new UnionFind(V); // V disjoint verticies
	for (int i = 0; i < E; ++i) { // E times -> O(E)
		int[] min = EL.get(i);
		
		if (UF.isSameSet(min[0], min[1])) continue; // check, O(1)
		UF.unionSet(min[0], min[1]); // link them in the UFDS, O(1)
		
		mst_cost += min[2]; // add w of this edge
		++num_taken;
		
		if (num_taken == V-1) break; // early termination, once we have a spanning tree, break
	}
	
	return mst_cost;
}

keep in mind that the UFDS operations are only for

6 vertex graph: kruskal()

Application

Leetcode: Min Cost to Connect All Points

kruskal’s method

java

int V = points.length, E = (V * (V - 1)) / 2;
List<int[]> EL = new ArrayList<>();

for (int i = 0; i < V - 1; i++)
	for (int j = i + 1; j < V; j++) {
		int w = Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1]);
		EL.add(new int[] { i, j, w });
			// EL.add(new int[] { j, i, w }); // don't do both ways
	}

Collections.sort(EL, Comparator.<int[]>comparingInt(x -> x[2]).thenComparingInt(x -> x[0]).thenComparingInt(x -> x[1]));

int mst_cost = 0, num_taken = 0;
UnionFind UF = new UnionFind(V);
for (int i = 0; i < E; ++i) {
	int[] min = EL.get(i);

	if (UF.isSameSet(min[0], min[1]))
		continue;
	UF.unionSet(min[0], min[1]);

	mst_cost += min[2];
	++num_taken;

	if (num_taken == V - 1)
		break;
}
return mst_cost;