Minimum spanning tree of a graph

29 次查看（过去 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:
https://www.mathworks.com/matlabcentral/answers/570370-all-possible-spanning-tree
Hope this helps.
Regards,
Narvik
  1 个评论
Steven Lord
Steven Lord 2022-6-27
Ran in:
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
Ran in:
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!

类别

在 Help Center 和 File Exchange 中查找有关 2-D and 3-D Plots 的更多信息

标签

Community Treasure Hunt

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

Start Hunting!

Translated by