Minimum Spanning Trees problem with multiple roots

Hello. I want to know please is there any function that solve the minimum spanning trees problem with multiple roots. Thank you.

Answer 1

[Gourab]

Hi Mokhtari,

I understand that you want to solve minimum spanning tree problem with multiple roots.

The 'minspantree()' function in MATLAB is used to compute the minimum spanning tree of an undirected graph or a directed graph with non-negative weights.

However, the 'minspantree()' function does not directly support finding the minimum spanning tree with multiple roots

Please refer to the below code snippet to modify the 'minspantree()' function to find the minimum spanning tree with multiple roots.

% Define a directed graph matrix A with non-negative weights
A = [0 2 1 0 0;
     0 0 0 3 0;
     0 4 0 0 2;
     0 0 0 0 1;
     0 0 0 2 0];

% Define the set of multiple roots as a new node with zero weight and add edges to all nodes
A = [A; zeros(1,size(A,2))];
A(end, 1:size(A,2)-1) = 1;

% Compute the minimum spanning tree using the modified graph
[mst, pred] = minspantree(sparse(A));

% Remove all edges that are incident on the root node to leave only the minimum spanning tree
mst(:,size(A,1)) = [];
mst(size(A,1),:) = [];

Please refer to the below documentation link for more information on ‘minspantree()’ function

https://www.mathworks.com/help/matlab/ref/graph.minspantree.html

I hope this helps you resolve the query.