Degree-Constrained Kruskal's

Pre-requisites: Kruskal's algorithm (see for description of standard Kruskal's. This will build upon that).

This Degree-Constrained Kruskal's algorithm is a greedy algorithm for the DCMST (Degree-Constrained Minimum Spanning Tree problem). It's a variation of Kruskal's algorithm with an extra constraint of node degree (number of outgoing edges from a node), and aims to find the cheapest possible spanning tree while adhering to this constraint. Given a node degree n, the algorithm tries to find the DCMST of the graph where each node has a degree <= n.

The logic is the same as Kruskal's algorithm, but at each step, not only is there a cycle check, but also a check if adding the edge will violate the degree constraint for the nodes of the edge. Due to it's greedy nature, it chases local optimums and may not always find a DCMST as it can get caught at dead ends. The termination conditions are the same as Kruskal's, i.e. when the number of edges in the DCMST = V - 1, where V is the number of nodes/vertices in the graph.

Degree-Constrained Kruskal's with degree constraint = 2:

The algorithm with a degree constraint of 2 failed to find a DCMST, as we can see above. However, we can have a different result by changing this degree constraint. Here is the same graph but with a degree constraint = 3:

As we can see, DC Kruskal's can find a DCMST, but due to its greedy nature, it sometimes cannot. We saw that changing the degree constraint parameter can lead to different results and edge-selection behaviour.

If you want to run DC Kruskal's with custom degree constraints on different/custom graphs, navigate to the Sandbox page in the navbar.