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 containsv-1
number of edges, a spanning tree is found.L14
: merges the target and source vertices into the same tree.
Last updated
Was this helpful?