Suppose we have a complete graph, with say 100 nodes. We divide the nodes in the graph into groups, for example 10 nodes in each group, identified by color. We want to obtain a minimum spanning tree under the constraint that at least one node will be present from each group ("group spanning tree").
How to write an efficient algorithm for this, making sure it is a tree (no cycles), without iterating over the entire node set, on every pass checking presence of cycles, and also making sure that at least one node from each group is represented?