CODEWITHSUNDEEP
algorithmgraphgraph-theorydiscrete-mathematicsminimum-spanning-tree
user1008537
user1008537

Reputation:

Proving optimality for a new algorithm that finds minimum spanning tree

Below is an algorithm that finds the minimum spanning tree:

MSTNew(G, w)
   Z ← empty array
   for each edge e in E, taken in random order do
       Z ← Z ∪ e
       if Z has a cycle c then
           let e be a maximum-weight edge on c
           Z ← Z − e
   return (Z)

Does this algorithm always return the optimal MST solution?

I would say yes. It sort of looks like Kruskals algorithm in disguise - sort-of.

Being fairly new to graph theory, I really don't have much of an idea other than that. Would someone have any ideas or advice?

Upvotes: 0

Views: 125

Answers (1)

Abhishek Bansal
Abhishek Bansal

Reputation: 12715

Yes, IMO the algorithm outputs a Minimum Spanning Tree.

Informal Proof:

At every iteration, we remove only that edge which is the most expensive edge on a cycle. Such an edge can never be included in a MST (by exchange argument). Thus we always exclude those edges which can never be a part of the MST.

Also, the output of the algorithm is always a spanning tree because we are deleting edges only when the new edge results in a cycle.

However, note that this algorithm will be highly inefficient since at each iteration you are not only checking for cycles (as in Kruskal's) but also searching for the maximum cost edge on the cycle.

Upvotes: 1

Related Questions