Minimum spanning tree of a graph

19 views (last 30 days)
Hari
Hari on 25 May 2022
Answered: Paras Gupta on 28 Jun 2022
Does the minimum spanning treee algorithm in matlab provide all possible minimum spanning trees, if not unique?

Answers (2)

NN
NN on 27 Jun 2022
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:
Hope this helps.
Regards,
Narvik
  1 Comment
Steven Lord
Steven Lord on 27 Jun 2022
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)

Sign in to comment.


Paras Gupta
Paras Gupta on 28 Jun 2022
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!

Categories

Find more on Graphics Performance in Help Center and File Exchange

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!