Minimum spanning tree of a graph
7 visualizaciones (últimos 30 días)
Mostrar comentarios más antiguos
Does the minimum spanning treee algorithm in matlab provide all possible minimum spanning trees, if not unique?
0 comentarios
Respuestas (2)
NN
el 27 de Jun. de 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 comentario
Steven Lord
el 27 de Jun. de 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)
for15 = numberOfTrees(end)
plot(n, numberOfTrees)
Paras Gupta
el 28 de Jun. de 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!
0 comentarios
Ver también
Categorías
Más información sobre Graphics Performance en Help Center y File Exchange.
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!