# Kruskal's Algorithm

{% hint style="warning" %}
Before reading, review [Minimum Spanning Trees](/algorithms/minimum-spanning-trees.md) and [Union Find (Disjoint Sets)](/abstract-data-types/union-find-disjoint-sets.md) as they both make Kruskal's algorithm possible!
{% endhint %}

## Conceptual Overview

Kruskal's algorithm is another optimal way to construct a **minimum spanning tree**. It's benefits are that it is conceptually very simple, and easy to implement. The idea is that first we sort all the edges of the graph in order of increasing weight. Then, add the smallest edge to the MST we are constructing unless this creates a cycle in the MST. Repeat until V - 1 edges total.

## Detailed Breakdown

In order to optimally check if adding an edge to our MST creates a cycle, we will use a **WeightedQuickUnion** object. (See [Union Find (Disjoint Sets)](/abstract-data-types/union-find-disjoint-sets.md) for a recap on what this is.) This is used because checking if a cycle exists using a WeightedUnionFind object boils down to one `isConnected()` call, which we know takes $$\Theta(\log(N))$$.

To run the algorithm, we start by adding all the edges into a [PriorityQueue](/abstract-data-types/collections/stacks-and-queues.md). This gives us our edges in sorted order. Now, we iterate through the PriorityQueue by removing the edge with highest priority, checking if adding it forms a cycle, and adding it to our MST if it doesn't form a cycle.

Let's see an example of Kruskal's Algorithm in action!

Here, we start with a simple graph and have sorted all of its edges into a priority queue.

![](/files/-M79xUYhsIOvTcz4gaKg)

Since the edge **DE** is the shortest, we'll add that to our UnionFind first. In the process, we'll **remove DE from the priority queue.**

![](/files/-M79yzDmu5WUGZW2GKBd)

We'll do the same thing with the next shortest path, **DC.**

![](/files/-M79z6J-E0X-Y64uZDpV)

Now, let's move on to **AB.** Notice that this time, connecting A and B creates another **disjoint set!** Unlike Prim's Algorithm, Kruskal's Algorithm does not guarantee that a solution will form a tree structure until the very end.

![](/files/-M79zKxaMAwkHco7x4e4)

Now, let's connect **BC.**

![](/files/-M79zTICYkpyWgRPj1mc)

Since **CE** and **BD** would both form cycles if connected, **we are done 😄** Here's the final tree:

![](/files/-M79zmVwUKXejnIrpTZO)

## PseudoCode

```java
public class Kruskals() {

    public Kruskals() {
        PQ edges = new PriorityQueue<>();
        ArrayList<Edge> mst = new ArrayList<>();
    }

    public void doKruskals(Graph G) {
        for (e : G.edges()) {
            PQ.add(e);
        }
        WeightedQU uf = new WeightedQU(G.V());
        Edge e = PQ.removeSmallest();
        int v = e.from();
        int w = e.to();
        if (!uf.isConnected(v, w)) {
            uf.union(v, w);
            mst.add(e);
        }

    }
}
```

## Runtime Analysis

Left as an exercise to the reader 😉

{% hint style="info" %}
Someone's been reading too much [LADR](https://www.springer.com/gp/book/9783319110790)...\
(The answer is $$\Theta(E\log(E))$$by the way. Try to convince yourself why!)
{% endhint %}


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://cs61b.bencuan.me/algorithms/minimum-spanning-trees/kruskals-algorithm.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.