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