# spanning tree

This topic is 3679 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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!!

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

##### Share on other sites
Quote:
 Original post by all_names_takenSorry 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!

1. 1
2. 2
3. 3
Rutin
15
4. 4
5. 5

• 10
• 9
• 9
• 11
• 11
• ### Forum Statistics

• Total Topics
633686
• Total Posts
3013318
×