How to find leaves in minimal spanning tree

Hello, I am trying to determine the leaves or terminal nodes (I think it is the same) of a MST. I use graphminspatree to find the minimal spanning tree and after that I want to find the leaves of it. How can I calculate this ? Any idea? Is there a built in function in matlab I could use? I've already used the matlab function "leaves" but it just can't calculate it...

thanks in advance!

Answer 1

[Steven Lord]

It has been a while since this question was asked, and this answer wouldn't have worked at the time it was first asked, but you can work with graphs in MATLAB using the graph and network algorithms functionality first introduced to MATLAB in release R2015b.

Let's make a sample graph from the buckyball data.

G = graph(bucky);
h = plot(G);

Generate a minimum spanning tree and plot it. I specify the X and Y coordinates (using the coordinates from the plot of the full graph) to ensure the layout of the plots is the same.

M = minspantree(G);
figure
h2 = plot(G, 'XData', h.XData, 'YData', h.YData);
highlight(h2, M, 'EdgeColor', 'r', 'LineWidth', 4*h2.LineWidth);

What are the leaves? The vertices of degree 1.

leaves = find(degree(M) == 1)

leaves = 13×1

26 30 37 42 47 52 53 54 56 57

Let's double check.

figure
h3 = plot(M, 'XData', h.XData, 'YData', h.YData);
highlight(h3, leaves)