CODEWITHSUNDEEP
algorithmgraphtreedifferenceminimum-spanning-tree
Mehul Gupta
Mehul Gupta

Reputation: 1939

Difference between Spanning tree & Minimum spanning tree

I have been reading the concept of spanning trees & its types. This is what I have understood:

Spanning tree: a subset of Graph G with the minimum number of edges connecting all vertices

Minimum Spanning tree: It is a spanning tree where the summation of edge weights is minimum.

Now, does this mean, while retrieving an MST,

  1. if we come across a path in G which has more edges (as compared to some other path) but least weight on the summation of edge weights(as compared to all other paths possible), we won't be considering it as an MST?

  2. Does the concept of MST comes into play only if we have multiple Spanning trees for G? else Spanning tree=MST?

Thanks for the help!!

Upvotes: 0

Views: 1598

Answers (1)

ruakh
ruakh

Reputation: 183211

  1. if we come across a path in G which has more edges (as compared to some other path) but least weight on the summation of edge weights(as compared to all other paths possible), we won't be considering it as an MST?

I assume that by "path", you meant to write "tree"? (A "path" is a completely different concept: it has just two endpoints, with no branching structure.)

A tree is a connected graph with no cycles, so every tree with n vertices has exactly n−1 edges. So if a graph has n vertices, then every spanning tree of that graph must have exactly n−1 edges. So if you have a subgraph with more than n−1 edges, then it's not a tree, so it's not a spanning tree, so — as you've surmised — it's not a minimum spanning tree.

But note that if a subgraph connects all the vertices, that subgraph will necessarily contain at least one spanning tree; and unless there are negative-weight edges, those spanning trees will have a weight less than or equal to that of the subgraph. So although your example isn't a minimum spanning tree, it may well contain a minimum spanning tree.

  1. Does the concept of MST comes into play only if we have multiple Spanning trees for G? else Spanning tree=MST?

If a graph has only one spanning tree, then that spanning tree is a minimum spanning tree, yes. But note that this only happens if the graph itself is a tree (in which case it's its own minimum spanning tree); otherwise it will certainly have multiple spanning trees.

Of course, even if it has multiple spanning trees, it's possible that they all have the same weight anyway, in which case they'll all be minimum spanning trees.

Upvotes: 3

Related Questions