8.3. Kruskal’s Algorithm

This section discusses Kruskal's Algorithm that finds a minimum spanning tree in an undirected graph.

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

Let us create the MSTKruskal class inheriting the MST interface:

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.