Degree-Constrained Prim's

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

This Degree-Constrained Prim's algorithm is a greedy algorithm for the DCMST (Degree-Constrained Minimum Spanning Tree problem). It's a variation of Prim'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 Prim'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 Prim'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 Prim's starting at node a with degree constraint = 2:

However, we can have a different result by changing parameters. Here is the same example with the
same degree constraint (2), but with a starting node of e:

As we can see, DC Prim's can find a DCMST, but due to its greedy nature, it sometimes cannot. We saw that changing the starting node can lead to different results. Changing the degree constaint also leads to different results and edge-selection behaviour.

If you want to run DC Prim's with custom starting nodes and degree constraints on different/custom graphs, navigate to the Sanbox page in the navbar.