Hey, I'm looking for an algorithm that would allow me to build a minimum spanning tree from a given set of weighted nodes (not connected in any, so, not a graph), and where each each node (including the root) as either 0 or a fixed number of children. I'll give an example. Lets say this is my set of nodes, where: - (0) is the root node; - Each node must have either 0 or 2 children

(0) (1) (3) (5) (7)

This would be the minimum spanning tree I would like to get: (tried to draw the tree here, but the identation got messed up when I posted... so, (X)->(A) (B), means node (X) has children (A) and (B)):

(0)->(1) (7)
(1)->(3) (5)

For a bigger set of nodes, however, I would need to start moving nodes around... I could implement this algorithm, I'm just wondering if some big math genius as an algorithm with his name that does something like this :) Thanks!!

Sorry if I missed something, but what are you trying to minimize - where do the weights of the nodes come into the picture?

Quote: Original post by all_names_taken
Sorry if I missed something, but what are you trying to minimize - where do the weights of the nodes come into the picture?

I'm sorry, I didn't explain myself very well. I want the sum of the costs in any path from root to leaf to be minimal.
In this case:

(0) to (7): cost 7
(0) to (3): cost 4
(0) to (5): cost 6


Thanks!