CODEWITHSUNDEEP
algorithmminimum-spanning-tree
elias rizik
elias rizik

Reputation: 263

Is it right solution for minimum spanning tree question?

I have a question from an exam and I wanna know if my approach is right for this question.

Input: graph G(V,E),weight function f:E->R and edge e=(u,v).
output: algorithm that finds a minimum spanning tree with edge e in it.

My solution is to run kruskal's algorithm and then add edge e if it does not exist, it should make a circle because the tree is n-1 edges so we go through the circle and remove the biggest edge(not e) that exists in that circle.

is my solution right? how to prove it if it is and if not can u someone tell me why?

(P.S I have the solution for this question just want to know if my approach is right)

Upvotes: 4

Views: 144

Answers (1)

Sandipan Dey
Sandipan Dey

Reputation: 23109

Or may be the other way, use Prim or Kruskal's algorithm, but first add the edge e to the graph (because it must be there in the tree) and then continue adding edges in the increasing order of weight values by popping from the priority queue (e.g., fibonacci heap) with the regular algorithm steps, the algorithm itself will ensure that there is no cycle and the tree spans the graph (then you don't need the extra step to traverse the cycle and remove the max-weight edge different from e).

Upvotes: 4

Related Questions