Kruskal's

Scan E by increasing weight. If the current edge is safe, add it to T

MakeSet, Union, Find

To combine the newly selected safe edge to the current tree, Kruskal’s Algorithm uses these 3 helper functions:

1. MakeSet(v: Vertex) Makes a new set containing the given vertex
2. Find(v: Vertex) Finds a set that contains the given vertex
3. Union(set1: Set<Vertex>, set2: Set<Vertex>) Merges 2 sets

In actual implementation the function arguments might be different (passing objects on the stack is expensive) but the behavior should be the same.

Pseudocode

function KruskalsMST(G=(V, E)) -> Array<Edges>:
	T = {}
	sorted_edges = sorted(E)

	for v in V:
		MakeSet(v)

	for uv in sorted_edges:
		if Find(u) != Find(v): // if safe
			T.add(uv)
			Union(u, v)

	return T

Runtime Analysis

Initialization + Sort + Find + Union:

V + E\log E + E\cdot O(\text{find}) + (V-1)\cdot O(\text{union}) = O(E\log E)

Usually O(E\log E). This can also be improved to O(E\log V)