CODEWITHSUNDEEP
algorithmtreeminimum-spanning-treespanning-tree
user1354784
user1354784

Reputation: 406

Minimum Spanning Tree with leaves only?

I am asked to write an algorithm that finds the Minimum Spanning Tree in a graph G, but with the condition that each vertex of G be a leave in the spanning Tree T. How can this be possible if the graph has more than 2 elements? Suppose G contains the vertices a,b and c, the Spanning tree will might something like a--b--c, so in this case b is not a leaf.

I am not looking for a solution to the algorithm, I only want to understand how a Spanning Tree can be composed exclusively of leaves.

Here is the exact wording of the question Question

Thanks for the help

Upvotes: 1

Views: 1514

Answers (1)

lex82
lex82

Reputation: 11317

The question states that S is a subset of the vertices V in the graph. There may be non-leaf nodes. However, you have to make sure that these internal nodes are not in S. If S would be equal to V you'd be right.

Upvotes: 4

Related Questions