Split an undirected graph by multiple minimum spanning trees

2
votes

I want to split an undirected graph by multiple minimum spanning trees. There are some special (root) nodes from which I want to start constructing a minimum spanning tree and I know every weight between nodes.

Is there any algorithm to solve this problem? If there are no strict methods, any approximate methods are fine for me.

I attach two output examples. I will be glad if you help me. Thank you.

First sampleSecond sample

1
algorithmminimum-spanning-tree
If I correctly understand your problem then you can add zero weight between special nodes and then search for minimum spanning tree in whole graph. - Setonix
Thank you for your comment. In your method, the number of spanning trees is only one ? I want to have the same number of minimum spanning tree as special nodes. - yutaroyamanaka

1 Answers

5
votes

The problem can be solved by creating another special node (lets call red node). Connect red node with every special node (black nodes in initial graph) with zero weight edge. Then search MST from red node. At the end remove red node and all corresponding edges from node, this will split graph into several graphs (same number of special nodes).