CODEWITHSUNDEEP
algorithmgraphgraph-algorithmminimum-spanning-tree
Daniel16
Daniel16

Reputation: 123

Checking if v is a leaf in MST

I have this question:

Given undirected graph G = (V,E), V ∋ v and non-negative weights W find if there is a minimum spanning tree (MST) where v is a leaf and if there is, return it.

I thought about finding the MST using prim algorithm and check if v is a leaf in it. If v isn't a leaf I will find the second MST and check on it. The problem is the time complexity will be too high. I am sure there is another way to solve this problem but I don't know how. Can you please give me some clue on how to approach this question?

Upvotes: 1

Views: 781

Answers (2)

Mohamad S.
Mohamad S.

Reputation: 209

I think that even if the algorithm that kaya3 suggested is true, it's very hard to write a formal proof for it if you're in course of Algorithms, so I'll suggest a more elegant solution that's very easy to prove. Also, I'll suggest an edit on kaya3 algorithm that makes the proof a little bit easier:

Alogrithm1:

  1. Run Prim algorithm from v with giving priority to all edges that aren't connected to v. (Giving priority may be implemented for example by adding a very small number to the edges that are connected to v).
  2. If v is a leaf in the MST that the algorithm found return true. Else, return false.

I'll give you a hint for the proof that it's true: Since you start Prim from v then it'll for sure pick the lightest edge that goes out of v and then it'll keep choosing other edges that aren't connected to v as long as these edges weight is lesser or equal to edges that goes out of v. If it chose an edge that goes out of v then the MST couldn't be completed without it or that it's weight is lesser than any other edge's weight.

Upvotes: 0

kaya3
kaya3

Reputation: 51142

The problem with "generate all MSTs and check if v is a leaf in any of them" is that the number of MSTs in a graph can be enormous: it could be as many as n ** (n-2) where n is the number of nodes.

A better way is to observe that all MSTs of a given graph have the same total weight. So a more efficient algorithm could work like this:

  • Apply a standard algorithm to find an MST of G. Let total_weight be its total weight.
  • Apply a standard algorithm to find an MST of G - v, i.e. the graph without the node v. Let mst_without_v be this MST, and let weight_without_v be its total weight.
  • If v has an edge of weight total_weight - weight_without_v, then add this edge to mst_without_v and return it. Otherwise, return null.

If the algorithm returns a graph, then it is an MST of G because it spans (G - v) + v = G, it is a tree (because it was formed from a tree with one leaf added), and it has the correct total weight.

If the algorithm returns null, then no MST of G exists where v is a leaf. Otherwise, deleting v from such an MST would give an MST of G - v with the wrong total weight.

Upvotes: 2

Related Questions