Minimum spanning tree of a graph

Does the minimum spanning treee algorithm in matlab provide all possible minimum spanning trees, if not unique?

Answer 1

[NN]

Hi,

The ‘minspantree’ function does not provide all possible minimum spanning trees for a particular graph. Please check the documentation for the function : https://in.mathworks.com/help/matlab/ref/graph.minspantree.html

As for the tree returned, the function always returns a unique minimum spanning tree.

If you would like to find all the spanning trees for a particular graph, please refer to the following MATLAB answer:

https://www.mathworks.com/matlabcentral/answers/570370-all-possible-spanning-tree

Hope this helps.

Regards,

Narvik

[Steven Lord]

Note that the number of possible minimal spanning trees can be very, very large. If you had a complete graph on n vertices with all edges having the same cost, you'd have n^(n-2) possible trees. This grows rapidly.

n = (3:15).';
format longg
numberOfTrees = n.^(n-2)

numberOfTrees = 13×1

1.0e+00 * 3 16 125 1296 16807 262144 4782969 100000000 2357947691 61917364224

for15 = numberOfTrees(end)

for15 = 
      1.94619506835938e+15

plot(n, numberOfTrees)

Answer 2

[Paras Gupta]

Hi,

The above answer is correct. The following complements the above answer and illustrates the working of the 'minspantree' function with code.

The MATLAB function ‘minspantree’ outputs only one minimum spanning tree out of the possible total, as produced by using the selected algorithm (Prim's Algorithm, by default). This is evident in the following peice of code.

s = {'A' 'A' 'A' 'B' 'B' 'D' 'E' 'E' 'C'};
t = {'D' 'B' 'E' 'D' 'E' 'E' 'F' 'C' 'F'};
weights = [4 1 3 4 2 4 7 4 5];
G = graph(s,t,weights);
p = plot(G,'EdgeLabel',G.Edges.Weight);

% The output minimum spannin tree is the on produced using the
% Prims's Algorithm (default behavior). Total Weight = 16
mst1 = minspantree(G);
highlight(p,mst1);

% However, the above graph also has another minimum spanning tree.
% Total weight = 16

%     A - 1 - B       C
%             |     / |
%             2   4   5 
%             | /     |
%     D - 4 - E       F

You can refer to minspantree and highlight documentation for more information on finding the minimum spanning tree (either given by Prim's or Kruskal's Algorithm), and to highlight nodes and edges in a plotted graph.

Hope it helps!