MST with modification

Question

Can anyone think of a way to modify Kruskal's algorithm for a minimum spanning tree so that it must include a certain edge (u,v)?

Answer 1

I might be confusing, but as far as I remember, kruskal can handle negative weights,so you can give this edge -infinity weight.

• Of course it won't actually be -infinity, but a number low enough to be significant enough that it cannot be ignored, something like -1 * sigma(|weight(e)|) for each e in E.

Answer 2

If you can modify the graph structure, you could remove vertices u and v, and replace them with a new vertex w that has the edges u and v used to have. In the case of duplicate edges, pick the one with the smallest weight.

Answer 3

Provided that we know the edge weight of (u,v), we can also simply add it to the front of our sorted list of edge weights (as Kruskal sorts the edge weights in increasing order). In this case, the edge (u,v) will be the first edge included in our tree and Kruskal will run normally, finding the spanning tree of minimum weight with (u,v).