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

Issue

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' ?

Solution

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).

Answered By - Sumeet

Answer Checked By - Katrina (PHPFixing Volunteer)