MST with modification

Question

Can anyone think of a way to modify the Kruskal algorithm for a minimal spanning tree so that it should include some edge (u, v)?

Answer 1

I could be confusing, but as far as I remember, kruskal can handle negative weights, so you can pass the weight of this edge to -infinity .

• Of course, in reality it will not be -infinity , but the number is low enough significant enough to not be ignored, for example, -1 * sigma(|weight(e)|) for each e in E.

Answer 2

If you can change the structure of the graph, you can remove the vertices u and v and replace them with a new vertex w, which uses the edges u and v. For repeated ribs, select the one with the smallest weight.

Answer 3

Provided that we know the edge weight (u, v), we can also just add it to the front of our sorted list of edge weights (since Kruskal sorts the edge weights in ascending order). In this case, the edge (u, v) will be the first edge included in our tree, and Kruskal will work fine by finding a spanning tree with a minimum weight with (u, v).