# 8.3. Kruskal’s Algorithm

Kruskal's algorithm finds a minimum spanning tree by finding the minimum edge among subtrees.

{% embed url="<https://www.slideshare.net/jchoi7s/kruskals-algorithm-238997335>" %}

Let us create the [`MSTKruskal`](https://github.com/emory-courses/dsa-java/blob/master/src/main/java/edu/emory/cs/graph/span/MSTKruskal.java) class inheriting the `MST` interface:

```java
public class MSTKruskal implements MST {
    @Override
    public SpanningTree getMinimumSpanningTree(Graph graph) {
        PriorityQueue<Edge> queue = new PriorityQueue<>(graph.getAllEdges());
        DisjointSet forest = new DisjointSet(graph.size());
        SpanningTree tree = new SpanningTree();

        while (!queue.isEmpty()) {
            Edge edge = queue.poll();

            if (!forest.inSameSet(edge.getTarget(), edge.getSource())) {
                tree.addEdge(edge);
                if (tree.size() + 1 == graph.size()) break;
                forest.union(edge.getTarget(), edge.getSource());
            }
        }

        return tree;
    }
}
```

* `L4`: adds all edges to the priority queue.
* `L5`: creates a forest where each vertex is considered a separate tree.
* `L8`: iterates through all edges:
  * `L11`: if the target and source vertices in the edge are not in the same tree.
  * `L13`: if the tree contains `v-1` number of edges, a spanning tree is found.
  * `L14`: merges the target and source vertices into the same tree.