Minimal spanning tree problem

W = [1 4 3 3 9 7 5 10 5 8 6];

a=[1 2 4 2 1 1 1 6 3 5 2];

b=[2 4 6 5 5 4 3 3 4 4 3];

DG = sparse(a,b,W);

UG = tril(DG + DG');

h = view(biograph(UG,[],'ShowArrows','off','ShowWeights','on'));

[ST,pred] = graphminspantree(UG);

view(biograph(ST,[],'ShowArrows','off','ShowWeights','on'));

I want to find ALL of the optimal of the Minimal spanning tree problem. But the result just showed only 1 result instead of 2.

What should I change in the code?

Thank you in advance!

Answer 1

[Aditya]

Hi,

I don't think it is possible to get all the optimal solutions. The function returns one of the solutions. Also, the following functions used have been removed from MATLAB:

1. biograph
2. graphminspantree

An updated code would be:

W = [1 4 3 3 9 7 5 10 5 8 6]; 
a=[1 2 4 2 1 1 1 6 3 5 2];
b=[2 4 6 5 5 4 3 3 4 4 3];
G = graph(a,b,W);
p = plot(G,'EdgeLabel',G.Edges.Weight);
T = minspantree(G, 'Method','sparse', 'Type','forest');
highlight(p,T);

Here also, you will see that only one tree is returned. If there are multiple connected components, use Type as forest. Otherwise, use the Type tree for a given root node.