1 of 6

Kruskal’s algorithm

Give the order in which Kruskal’s algorithm selects edges.

After considering the edge with weight 2, circle the connected components above.

2 of 6

Kruskal’s Code

DisjointSets<V> trees = new DSImpl<V>(graph.vertices());

List<Edge<V>> edges = graph.edges();

edges.sort(Double.comparingDouble(Edge::weight));

List<Edge<V>> result = new ArrayList<>();

int i = 0;

while (result.size() < graph.vertices().size() - 1) {

Edge<V> e = edges.get(i);

if (!trees.find(e.from).equals(trees.find(e.to))) {

trees.union(e.from, e.to);

result.add(e);

}

i += 1;

}

return result;

}

3 of 6

Find and Union

Kruskal’s algorithm relies on two disjoint set operations: find, which returns the set representative (e.g. smallest value in set), and union, which combines two sets.

If we know that Kruskal’s algorithm is in Θ(|E| log |E|) time overall, fill in the blanks with big-O bounds for the calls to find and union.

Merge sort the list of edges in the graph. Θ(|E| log |E|)
While the size of the MST < |V| - 1…

Check if find(e.from).equals(find(e.to)). ________________
If false, union(e.from, e.to) and add e to result. ________________

What is the runtime if we use a List<Set<Node>> to implement find and union?

Merge sort the list of edges in the graph. Θ(|E| log |E|)
While the size of the MST < |V| - 1…

Check if find(e.from).equals(find(e.to)). ________________
If false, union(e.from, e.to) and add e to result. ________________

4 of 6

Comparing runtimes

Prim’s algorithm is in Θ(|E| log |V|) time overall. To get Kruskal’s to match this, we need an approach that has O(log |V|) time for both find and union.

Quick Find. Optimizes for the find operation.

Quick Union. Optimizes for the union operation, but doesn’t really succeed.

Weighted Quick Union. Addresses the worst-case height problem in quick union.

5 of 6

Bottleneck analysis

Let’s speed up Kruskal’s algorithm! If our edge weights are restricted to int values bounded between 0 and 255, fill in the blanks with your best possible runtimes.

________________ sort the list of edges in the graph. ________________
While the size of the MST < |V| - 1…

Check if find(e.from).equals(find(e.to)). ________________
If false, union(e.from, e.to) and add e to result. ________________

What is the runtime if we have a faster disjoint sets implementation, weighted quick union with path compression, where find and union are in Θ(𝜶|V|)?

________________ sort the list of edges in the graph. ________________
While the size of the MST < |V| - 1…

Check if find(e.from).equals(find(e.to)). ________________
If false, union(e.from, e.to) and add e to result. ________________

6 of 6

Path compression

Path compression reassigns the parent of each node visited by find to the root.

Analogous to balancing a search tree by rotations or color flips. Θ(𝛂(N)) amortized.