CODEWITHSUNDEEP
algorithmgraphminimum-spanning-tree
zeusm
zeusm

Reputation: 75

How can I find a Minimum spanning tree containing a given edge?

In a weighted undirected graph I need to find a minimum spanning tree containing a given edge 'e', if it's possible. How can I do it? Kruskal starting from 'e' ?

Upvotes: 4

Views: 4032

Answers (3)

eesiraed
eesiraed

Reputation: 4654

For a lazy solution, make the cost of that edge less than the cost of all other edges and run any MST algorithm on it.

Upvotes: 0

Micael Illos
Micael Illos

Reputation: 492

Here is a possible "lazy solution" that requires no modification of an MST algorithm

  1. Run any MST algorithm.
  • The MST algorithm will output an MST T = (V,E,w)

  1. If edge e is already in T then you're done

  2. If edge e is not in T then add edge e and you will have a cycle σ

  3. Iterate over cycle σ, if there is an edge with the same weight as e then remove that edge and your'e done

  4. If none of the edges have the same weight as e then a MST with e is not possible

Whats good about this approach is that is fairly easy to prove formally hence you have a proof for a MST algorithm and the other steps are based on known theorems.

Upvotes: 2

Sumeet
Sumeet

Reputation: 8292

I would not use Kruskal algorithm because if the edge e is part of cycle and e has maximum weight in that cycle, then the algorithm will not include 'e'. I believe with modification it could work. But with Prim's algorithm modification required is minimal.

Prim's algorithm is best suited for this problem, if we recall Prim algorithm goes like this:

STEP 1: Begin with set S containing a vertex picked randomly.

STEP 2: From all the edges with one vertex in set S and other vertex in set V - S,pick the one with minimum weight. Let it be (x,y), x belongs to S and y belongs to V - S.

STEP 3: Add y to set S.

STEP 4: Repeat step 2 and 3 till S contains all vertices.

Modification required:

For your problem just change step 1 to:

STEP 1: Begin with set S containing a vertex u and v where edge 'e' = (u,v).

Upvotes: 2

Related Questions