Minimum spanning tree of a graph

조회 수: 5(최근 30일)
Hari
Hari 2022년 5월 25일
답변: Paras Gupta 2022년 6월 28일
Does the minimum spanning treee algorithm in matlab provide all possible minimum spanning trees, if not unique?

답변(2개)

NN
NN 2022년 6월 27일
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
Steven Lord
Steven Lord 2022년 6월 27일
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)

댓글을 달려면 로그인하십시오.


Paras Gupta
Paras Gupta 2022년 6월 28일
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!

Community Treasure Hunt

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

Start Hunting!

Translated by